una rango numero muestra matriz lista generar elemento datos buscar aleatorios aleatorio aleatoria python algorithm performance

rango - muestra aleatoria en python



Python: Encontrar una partición de subconjunto k aleatoria para una lista dada (3)

El siguiente código genera todas las particiones de longitud k (particiones k-subconjunto) para una lista dada. El algoritmo se puede encontrar en this tema.

def algorithm_u(ns, m): def visit(n, a): ps = [[] for i in xrange(m)] for j in xrange(n): ps[a[j + 1]].append(ns[j]) return ps def f(mu, nu, sigma, n, a): if mu == 2: yield visit(n, a) else: for v in f(mu - 1, nu - 1, (mu + sigma) % 2, n, a): yield v if nu == mu + 1: a[mu] = mu - 1 yield visit(n, a) while a[nu] > 0: a[nu] = a[nu] - 1 yield visit(n, a) elif nu > mu + 1: if (mu + sigma) % 2 == 1: a[nu - 1] = mu - 1 else: a[mu] = mu - 1 if (a[nu] + sigma) % 2 == 1: for v in b(mu, nu - 1, 0, n, a): yield v else: for v in f(mu, nu - 1, 0, n, a): yield v while a[nu] > 0: a[nu] = a[nu] - 1 if (a[nu] + sigma) % 2 == 1: for v in b(mu, nu - 1, 0, n, a): yield v else: for v in f(mu, nu - 1, 0, n, a): yield v def b(mu, nu, sigma, n, a): if nu == mu + 1: while a[nu] < mu - 1: yield visit(n, a) a[nu] = a[nu] + 1 yield visit(n, a) a[mu] = 0 elif nu > mu + 1: if (a[nu] + sigma) % 2 == 1: for v in f(mu, nu - 1, 0, n, a): yield v else: for v in b(mu, nu - 1, 0, n, a): yield v while a[nu] < mu - 1: a[nu] = a[nu] + 1 if (a[nu] + sigma) % 2 == 1: for v in f(mu, nu - 1, 0, n, a): yield v else: for v in b(mu, nu - 1, 0, n, a): yield v if (mu + sigma) % 2 == 1: a[nu - 1] = 0 else: a[mu] = 0 if mu == 2: yield visit(n, a) else: for v in b(mu - 1, nu - 1, (mu + sigma) % 2, n, a): yield v n = len(ns) a = [0] * (n + 1) for j in xrange(1, m + 1): a[n - m + j] = j - 1 return f(m, n, 0, n, a)

sabemos que el número de k-subconjuntos de una lista dada es igual al Stirling number y podría ser muy grande para algunas listas grandes.

el código anterior devuelve un generador de Python que podría generar todas las particiones de subconjuntos k posibles para la lista dada llamando su próximo método. en consecuencia, si quiero obtener solo una de estas particiones al azar, tengo que llamar al siguiente método para algunos tiempos aleatorios (lo que hace que sea muy lento si el número de Stirling es grande) o usar el método itertools.islice para obtener una porción de tamaño uno que es muy lento como antes.

Estoy tratando de evitar enumerar todas las particiones porque sería una pérdida de tiempo y velocidad e incluso de memoria (porque los cálculos son muchos y la memoria es importante en mi caso).

la pregunta es ¿cómo puedo generar solo una de las particiones k-subconjunto sin generar el resto? o al menos hacer el procedimiento más rápido que lo explicado anteriormente. Necesito el rendimiento porque necesito obtener solo uno de ellos cada vez y ejecuto la aplicación tal vez más de diez millones de veces.

Apreciaría cualquier ayuda.

EDITAR: EJEMPLO

lista: { 1, 2, 3 }

para k = 3:

{ {1}, {2}, {3} }

para k = 2:

{ {1, 2}, {3} } { {1, 3}, {2} } { {1}, {2, 3} }

y para k = 1:

{ {1, 2, 3} }

considere k = 2, ¿hay alguna manera de que pueda generar solo una de estas 3 particiones al azar, sin generar las otras 2? tenga en cuenta que quiero generar una partición aleatoria para cualquier k dada, no solo una partición aleatoria de cualquier k, lo que significa que si configuro la k en 2, me gustaría generar solo una de estas 3 no una de las 5.

Saludos,

Mohammad

Puede contar los números de Stirling de manera eficiente con un algoritmo recursivo almacenando valores calculados previamente:

fact=[1] def nCr(n,k): """Return number of ways of choosing k elements from n""" while len(fact)<=n: fact.append(fact[-1]*len(fact)) return fact[n]/(fact[k]*fact[n-k]) cache = {} def count_part(n,k): """Return number of ways of partitioning n items into k non-empty subsets""" if k==1: return 1 key = n,k if key in cache: return cache[key] # The first element goes into the next partition # We can have up to y additional elements from the n-1 remaining # There will be n-1-y left over to partition into k-1 non-empty subsets # so n-1-y>=k-1 # y<=n-k t = 0 for y in range(0,n-k+1): t += count_part(n-1-y,k-1) * nCr(n-1,y) cache[key] = t return t

Una vez que sepa cuántas opciones hay, puede adaptar este código recursivo para generar una partición particular:

def ith_subset(A,k,i): """Return ith k-subset of A""" # Choose first element x n = len(A) if n==k: return A if k==0: return [] for x in range(n): # Find how many cases are possible with the first element being x # There will be n-x-1 left over, from which we choose k-1 extra = nCr(n-x-1,k-1) if i<extra: break i -= extra return [A[x]] + ith_subset(A[x+1:],k-1,i) def gen_part(A,k,i): """Return i^th k-partition of elements in A (zero-indexed) as list of lists""" if k==1: return [A] n=len(A) # First find appropriate value for y - the extra amount in this subset for y in range(0,n-k+1): extra = count_part(n-1-y,k-1) * nCr(n-1,y) if i<extra: break i -= extra # We count through the subsets, and for each subset we count through the partitions # Split i into a count for subsets and a count for the remaining partitions count_partition,count_subset = divmod(i,nCr(n-1,y)) # Now find the i^th appropriate subset subset = [A[0]] + ith_subset(A[1:],y,count_subset) S=set(subset) return [subset] + gen_part([a for a in A if a not in S],k-1,count_partition)

Como ejemplo, he escrito un programa de prueba que produce diferentes particiones de 4 números:

def test(A): n=len(A) for k in [1,2,3,4]: t = count_part(n,k) print k,t for i in range(t): print " ",i,gen_part(A,k,i) test([1,2,3,4])

Este código imprime:

1 1 0 [[1, 2, 3, 4]] 2 7 0 [[1], [2, 3, 4]] 1 [[1, 2], [3, 4]] 2 [[1, 3], [2, 4]] 3 [[1, 4], [2, 3]] 4 [[1, 2, 3], [4]] 5 [[1, 2, 4], [3]] 6 [[1, 3, 4], [2]] 3 6 0 [[1], [2], [3, 4]] 1 [[1], [2, 3], [4]] 2 [[1], [2, 4], [3]] 3 [[1, 2], [3], [4]] 4 [[1, 3], [2], [4]] 5 [[1, 4], [2], [3]] 4 1 0 [[1], [2], [3], [4]]

Como otro ejemplo, hay 10 millones de particiones de 1,2,3, .. 14 en 4 partes. Este código puede generar todas las particiones en 44 segundos con pypy.

Hay 50,369,882,873,307,917,364,901 particiones de 1,2,3, ..., 40 en 4 partes. Este código puede generar 10 millones de estos en 120 segundos con pypy ejecutándose en un solo procesador.

Para unir cosas, puede usar este código para generar una sola partición aleatoria de una lista A en k subconjuntos no vacíos:

import random def random_ksubset(A,k): i = random.randrange(0,count_part(len(A),k)) return gen_part(A,k,i)

Qué tal algo como esto:

import itertools import random def random_ksubset(ls, k): # we need to know the length of ls, so convert it into a list ls = list(ls) # sanity check if k < 1 or k > len(ls): return [] # Create a list of length ls, where each element is the index of # the subset that the corresponding member of ls will be assigned # to. # # We require that this list contains k different values, so we # start by adding each possible different value. indices = list(range(k)) # now we add random values from range(k) to indices to fill it up # to the length of ls indices.extend([random.choice(list(range(k))) for _ in range(len(ls) - k)]) # shuffle the indices into a random order random.shuffle(indices) # construct and return the random subset: sort the elements by # which subset they will be assigned to, and group them into sets return [{x[1] for x in xs} for (_, xs) in itertools.groupby(sorted(zip(indices, ls)), lambda x: x[0])]

Esto produce particiones aleatorias de k-subconjuntos de esta manera

>>> ls = {1,2,3} >>> print(random_ksubset(ls, 2)) [set([1, 2]), set([3])] >>> print(random_ksubset(ls, 2)) [set([1, 3]), set([2])] >>> print(random_ksubset(ls, 2)) [set([1]), set([2, 3])] >>> print(random_ksubset(ls, 2)) [set([1]), set([2, 3])]

Este método satisface el requisito de OP de obtener una partición generada aleatoriamente, sin enumerar todas las particiones posibles. La complejidad de la memoria aquí es lineal. La complejidad en tiempo de ejecución es O (N log N) debido a la clasificación. Supongo que podría ser posible convertir esto en lineal, si eso fuera importante, usando un método más complicado para construir el valor de retorno.

Como señala @Leon, esto satisface los requisitos de su opción 2 al tratar de definir el problema. Lo que esto no hará es generar de manera determinista la partición #N (esta es la opción 1 de Leon, que le permitiría elegir aleatoriamente un entero N y luego recuperar la partición correspondiente). La aclaración de León es importante porque, para satisfacer el espíritu de la pregunta, cada posible partición de la colección debe generarse con la misma probabilidad. En nuestro problema de juguetes, este es el caso:

>>> from collections import Counter >>> Counter(frozenset(map(frozenset, random_ksubset(ls, 2))) for _ in range(10000)) Counter({frozenset({frozenset({2, 3}), frozenset({1})}): 3392, frozenset({frozenset({1, 3}), frozenset({2})}): 3212, frozenset({frozenset({1, 2}), frozenset({3})}): 3396})

Sin embargo. En general, este método no genera cada partición con igual probabilidad. Considerar:

>>> Counter(frozenset(map(frozenset, random_ksubset(range(4), 2))) ... for _ in range(10000)).most_common() [(frozenset({frozenset({1, 3}), frozenset({0, 2})}), 1671), (frozenset({frozenset({1, 2}), frozenset({0, 3})}), 1667), (frozenset({frozenset({2, 3}), frozenset({0, 1})}), 1642), (frozenset({frozenset({0, 2, 3}), frozenset({1})}), 1285), (frozenset({frozenset({2}), frozenset({0, 1, 3})}), 1254), (frozenset({frozenset({0, 1, 2}), frozenset({3})}), 1245), (frozenset({frozenset({1, 2, 3}), frozenset({0})}), 1236)]

Podemos ver aquí que es más probable que generemos particiones "más equilibradas" (porque hay más formas de construirlas). Las particiones que contienen conjuntos singleton se producen con menos frecuencia.

Parece que un método de muestreo uniforme y eficiente sobre k-particiones de conjuntos es una especie de pregunta de investigación sin resolver (también vea mathoverflow ). Nijenhuis y Wilf dan código para el muestreo de todas las particiones (Capítulo 12), que podría funcionar con las pruebas de rechazo, y la answer de @PeterdeRivaz también puede muestrear de manera uniforme una partición k. El inconveniente de estos dos métodos es que requieren el cálculo de los números de Stirling, que crecen exponencialmente en n, y los algoritmos son recursivos, lo que creo que los hará lentos en grandes entradas. Cuando menciona "millones" de particiones en su comentario, creo que estos enfoques solo serán manejables hasta cierto tamaño de entrada.

A. Nijenhuis y H. Wilf. Algoritmos combinatorios para computadoras y calculadoras. Academic Press, Orlando FL, segunda edición, 1978.

Explorar la opción 1 de León podría ser interesante. Este es un procedimiento aproximado para producir determinísticamente una partición particular de una colección usando la sugerencia de @ Amadan de tomar un valor entero interpretado como un número k-ario. Tenga en cuenta que no todos los valores enteros producen una partición de k-subconjunto válida (porque no permitimos subconjuntos vacíos):

def amadan(ls, N, k): """ Given a collection `ls` with length `b`, a value `k`, and a "partition number" `N` with 0 <= `N` < `k**b`, produce the Nth k-subset paritition of `ls`. """ ls = list(ls) b = len(ls) if not 0 <= N < k**b: return None # produce the k-ary index vector from the number N index = [] # iterate through each of the subsets for _ in range(b): index.append(N % k) N //= k # subsets cannot be empty if len(set(index)) != k: return None return frozenset(frozenset(x[1] for x in xs) for (_, xs) in itertools.groupby(sorted(zip(index, ls)), lambda x:x[0]))

Podemos confirmar que esto genera los números de Stirling correctamente:

>>> for i in [(4,1), (4,2), (4,3), (4,4), (5,1), (5,2), (5,3), (5,4), (5,5)]: ... b,k = i ... r = [amadan(range(b), N, k) for N in range(k**b)] ... r = [x for x in r if x is not None] ... print(i, len(set(r))) (4, 1) 1 (4, 2) 7 (4, 3) 6 (4, 4) 1 (5, 1) 1 (5, 2) 15 (5, 3) 25 (5, 4) 10 (5, 5) 1

Esto también puede ser capaz de producir cada partición posible con la misma probabilidad; No estoy muy seguro. Aquí hay un caso de prueba, donde funciona:

>>> b,k = 4,3 >>> r = [amadan(range(b), N, k) for N in range(k**b)] >>> r = [x for x in r if x is not None] >>> print(Counter(['' ''.join(sorted(''''.join(map(str, x)) for x in p)) for p in r])) Counter({''0 13 2'': 6, ''01 2 3'': 6, ''0 12 3'': 6, ''03 1 2'': 6, ''02 1 3'': 6, ''0 1 23'': 6})

Otro caso de trabajo:

>>> b,k = 5,4 >>> r = [amadan(range(b), N, k) for N in range(k**b)] >>> r = [x for x in r if x is not None] >>> print(Counter(['' ''.join(sorted(''''.join(map(str, x)) for x in p)) for p in r])) Counter({''0 12 3 4'': 24, ''04 1 2 3'': 24, ''0 1 23 4'': 24, ''01 2 3 4'': 24, ''03 1 2 4'': 24, ''0 13 2 4'': 24, ''0 1 24 3'': 24, ''02 1 3 4'': 24, ''0 1 2 34'': 24, ''0 14 2 3'': 24})

Entonces, para envolver esto en una función:

def random_ksubset(ls, k): ls = list(ls) maxn = k**len(ls)-1 rv = None while rv is None: rv = amadan(ls, random.randint(0, maxn), k) return rv

Y luego podemos hacer:

>>> random_ksubset(range(3), 2) frozenset({frozenset({2}), frozenset({0, 1})}) >>> random_ksubset(range(3), 2) frozenset({frozenset({1, 2}), frozenset({0})}) >>> random_ksubset(range(3), 2) frozenset({frozenset({1, 2}), frozenset({0})}) >>> random_ksubset(range(3), 2) frozenset({frozenset({2}), frozenset({0, 1})})

tl; dr:

Las particiones de k-subconjuntos para un n y k dado se pueden dividir en tipos, en función de qué elementos son los primeros en entrar en partes aún vacías. Cada uno de estos tipos está representado por un patrón de bits con n-1 bits de los cuales se establece k-1. Mientras que el número de particiones es enorme (dado por el segundo número de Stirling), el número de tipos es mucho menor, por ejemplo:

n = 21, k = 8
número de particiones: S (21,8) = 132,511,015,347,084
número de tipos: (n-1 elige k-1) = 77,520

Calcular la cantidad de particiones que hay de cada tipo es simple, según la posición de los ceros en el patrón de bits. Si realiza una lista de todos los tipos (mediante la iteración de todos los patrones de bits n: k) y mantiene un total acumulado del número de particiones, puede utilizar una búsqueda binaria en esta lista para encontrar el tipo de partición con una rango dado (en el registro 2 (n-1 elija k-1) pasos; 17 para el ejemplo anterior), luego traduzca el patrón de bits a una partición y calcule en qué parte va cada elemento (en n pasos). Cada parte de este método se puede hacer de forma iterativa, sin necesidad de recursión.

Aquí hay una solución no recursiva. He intentado rodar la mía, pero puede (parcialmente) superponerse con la respuesta de Peter o los métodos existentes.

Si tiene un conjunto de n elementos, por ejemplo, con n = 8:

{a, b, c, d, e, f, g, h}

entonces las particiones de k-subconjuntos tomarán esta forma, por ejemplo, con k = 5:

{a, e} {b, c, h} {d} {f} {g}

Esta partición también se puede escribir como:

1,2,2,3,1,4,5,2

que enumera en qué parte entra cada uno de los elementos. Así que esta secuencia de n dígitos con valores de 1 a k representa una partición de k-subconjunto de n elementos.

Sin embargo, no todas estas secuencias son particiones válidas; cada dígito de 1 a k debe estar presente, de lo contrario habría partes vacías:

1,2,2,3,1,3,5,2 → {a, e} {b, c, h} {d, f} {} {g}

Además, para evitar duplicados, el dígito x solo se puede utilizar después de que se haya utilizado el dígito x-1. Así que el primer dígito siempre es 1, el segundo puede ser como máximo 2, y así sucesivamente. Si en el ejemplo usamos los dígitos 4 y 5 antes de 3, obtenemos particiones duplicadas:

1,2,2,3,1,4,5,2 → {a, e} {b, c, h} {d} {f} {g}
1,2,2,4,1,5,3,2 → {a, e} {b, c, h} {g} {d} {f}

Cuando agrupa las particiones en función de cuándo se utiliza cada parte por primera vez, obtiene estos tipos:

1,1,1,1,2,3,4,5 0001111 11111111 1 1 1,1,1,2,12,3,4,5 0010111 11112111 2 2 1,1,1,2,3,123,4,5 0011011 11111311 3 3 1,1,1,2,3,4,1234,5 0011101 11111141 4 4 1,1,1,2,3,4,5,12345 0011110 11111115 5 5 1,1,2,12,12,3,4,5 0100111 11122111 2*2 4 1,1,2,12,3,123,4,5 0101011 11121311 2*3 6 1,1,2,12,3,4,1234,5 0101101 11121141 2*4 8 1,1,2,12,3,4,5,12345 0101110 11121115 2*5 10 1,1,2,3,123,123,4,5 0110011 11113311 3*3 9 1,1,2,3,123,4,1234,5 0110101 11113141 3*4 12 1,1,2,3,123,4,5,12345 0110110 11113115 3*5 15 1,1,2,3,4,1234,1234,5 0111001 11111441 4*4 16 1,1,2,3,4,1234,5,12345 0111010 11111415 4*5 20 1,1,2,3,4,5,12345,12345 0111100 11111155 5*5 25 1,2,12,12,12,3,4,5 1000111 11222111 2*2*2 8 1,2,12,12,3,123,4,5 1001011 11221311 2*2*3 12 1,2,12,12,3,4,1234,5 1001101 11221141 2*2*4 16 1,2,12,12,3,4,5,12345 1001110 11221115 2*2*5 20 1,2,12,3,123,123,4,5 1010011 11213311 2*3*3 18 1,2,12,3,123,4,1234,5 1010101 11213141 2*3*4 24 1,2,12,3,123,4,5,12345 1010110 11213115 2*3*5 30 1,2,12,3,4,1234,1234,5 1011001 11211441 2*4*4 32 1,2,12,3,4,1234,5,12345 1011010 11211415 2*4*5 40 1,2,12,3,4,5,12345,12345 1011100 11211155 2*5*5 50 1,2,3,123,123,123,4,5 1100011 11133311 3*3*3 27 1,2,3,123,123,4,1234,5 1100101 11133141 3*3*4 36 1,2,3,123,123,4,5,12345 1100110 11133115 3*3*5 45 1,2,3,123,4,1234,1234,5 1101001 11131441 3*4*4 48 1,2,3,123,4,1234,5,12345 1101010 11131415 3*4*5 60 1,2,3,123,4,5,12345,12345 1101100 11131155 3*5*5 75 1,2,3,4,1234,1234,1234,5 1110001 11114441 4*4*4 64 1,2,3,4,1234,1234,5,12345 1110010 11114415 4*4*5 80 1,2,3,4,1234,5,12345,12345 1110100 11114155 4*5*5 100 1,2,3,4,5,12345,12345,12345 1111000 11111555 5*5*5 125 SUM = 1050

En el diagrama anterior, una partición del tipo:

1,2,12,3,123,4,1234,5

significa que:

a entra en la parte 1
b entra en la parte 2
c entra en la parte 1 o 2
d entra en la parte 3
e entra en la parte 1, 2 o 3
f entra en la parte 4
g entra en la parte 1, 2, 3 o 4
h entra en la parte 5

Por lo tanto, las particiones de este tipo tienen un dígito que puede tener 2 valores, un dígito que puede tener 3 valores y un dígito que puede tener 4 valores (esto se indica en la tercera columna en el diagrama de arriba). Así que hay un total de 2 × 3 × 4 particiones de este tipo (como se indica en las columnas 4 y 5). La suma de estos es, por supuesto, el número de Stirling: S (8,5) = 1050.

La segunda columna en el diagrama es otra forma de anotar el tipo de partición: después de comenzar con 1, cada dígito es un dígito que se usó anteriormente o un paso adelante (es decir, el dígito más alto usado hasta ahora + 1). Si representamos estas dos opciones por 0 y 1, obtenemos por ejemplo:

1,2,12,3,123,4,1234,5 → 1010101

donde 1010101 significa:

Comenzar con 1
1 → paso hasta 2
0 → repetir 1 o 2
1 → paso hasta 3
0 → repetir 1, 2 o 3
1 → paso hasta 4
0 → repetir 1, 2, 3 o 4
1 → paso hasta 5

Entonces, cada secuencia binaria con n-1 dígitos y k-1 representa un tipo de partición. Podemos calcular el número de particiones de un tipo iterando sobre los dígitos de izquierda a derecha, incrementando un factor cuando encontramos uno y multiplicando con el factor cuando encontramos un cero, por ejemplo:

1,2,12,3,123,4,1234,5 → 1010101
Comience con producto = 1, factor = 1
1 → factor de incremento: 2
0 → producto × factor = 2
1 → factor de incremento: 3
0 → producto × factor = 6
1 → factor de incremento: 4
0 → producto × factor = 24
1 → factor de incremento: 5

Y nuevamente para este ejemplo, encontramos que hay 24 particiones de este tipo. Entonces, el conteo de las particiones de cada tipo se puede hacer iterando sobre todos los enteros de n-1 dígito con los dígitos de k-1 establecidos, utilizando cualquier método (por ejemplo, el hackeo de Gosper):

0001111 1 1 0010111 2 3 0011011 3 6 0011101 4 10 0011110 5 15 0100111 4 19 0101011 6 25 0101101 8 33 0101110 10 43 0110011 9 52 0110101 12 64 0110110 15 79 0111001 16 95 0111010 20 115 0111100 25 140 1000111 8 148 1001011 12 160 1001101 16 176 1001110 20 196 1010011 18 214 1010101 24 238 1010110 30 268 1011001 32 300 1011010 40 340 1011100 50 390 1100011 27 417 1100101 36 453 1100110 45 498 1101001 48 546 1101010 60 606 1101100 75 681 1110001 64 745 1110010 80 825 1110100 100 925 1111000 125 1050

Encontrar una partición aleatoria significa, entonces, elegir un número de 1 a S (n, k), revisar los conteos por tipo de partición mientras se mantiene un total acumulado (columna 3 arriba) y seleccionar el tipo de partición correspondiente, y luego calcular el valor de los dígitos repetidos, por ejemplo:

S (8,5) = 1050
selección aleatoria: por ejemplo, 333
tipo: 1011010 → 1,2,12,3,4,1234,5,12345
rango: 301 - 340
variación: 333 - 301 = 32
Opciones de dígitos: 2, 4, 5
valores de dígitos: 20, 5, 1
variación: 32 = 1 × 20 + 2 × 5 + 2 × 1
dígitos: 1, 2, 2 (basado en 0) → 2, 3, 3 (basado en 1)
partición: 1,2,2,3,4,3,5,3

y la 333ª partición de 8 elementos en 5 partes es:

1,2,2,3,4,3,5,3 → {a} {b, c} {d, f, h} {e} {g}

Hay una serie de opciones para convertir esto en código; Si almacena los números de n-1 dígito como un total acumulado, puede hacer búsquedas subsiguientes usando una búsqueda binaria sobre la lista, cuya longitud es C (n-1, k-1), para reducir la complejidad de tiempo de O (C (n-1, k-1)) a O (Log 2 (C (n-1, k-1))).

Hice una primera prueba en JavaScript (lo siento, no hablo Python); No es bonito pero demuestra el método y es bastante rápido. El ejemplo es para el caso n = 21 y k = 8; crea la tabla de conteo para 77,520 tipos de particiones, devuelve el número total de particiones 132,511,015,347,084 y luego recupera 10 particiones elegidas al azar dentro de ese rango. En mi computadora, este código devuelve un millón de particiones seleccionadas al azar en 3.7 segundos. (nota: el código está basado en cero, a diferencia de la explicación anterior)

function kSubsetPartitions(n, k) { // Constructor this.types = []; this.count = []; this.total = 0; this.elems = n; var bits = (1 << k - 1) - 1, done = 1 << n - 1; do { this.total += variations(bits); this.types.push(bits); this.count.push(this.total); } while (!((bits = next(bits)) & done)); function variations(bits) { var product = 1, factor = 1, mask = 1 << n - 2; while (mask) { if (bits & mask) ++factor; else product *= factor; mask >>= 1; } return product; } function next(a) { // Gosper''s Hack var c = (a & -a), r = a + c; return (((r ^ a) >> 2) / c) | r; } } kSubsetPartitions.prototype.partition = function(rank) { var range = 1, type = binarySearch(this.count, rank); if (type) { rank -= this.count[type - 1]; range = this.count[type] - this.count[type - 1]; } return translate(this.types[type], this.elems, range, rank); // This translates the bit pattern format and creates the correct partition // for the given rank, using a letter format for demonstration purposes function translate(bits, len, range, rank) { var partition = [["A"]], part, max = 0, mask = 1 << len - 2; for (var i = 1; i < len; i++, mask >>= 1) { if (!(bits & mask)) { range /= (max + 1); part = Math.floor(rank / range); rank %= range; } else part = ++max; if (!partition[part]) partition[part] = ""; partition[part] += String.fromCharCode(65 + i); } return partition.join(" / "); } function binarySearch(array, value) { var low = 0, mid, high = array.length - 1; while (high - low > 1) { mid = Math.ceil((high + low) / 2); if (value < array[mid]) high = mid; else low = mid; } return value < array[low] ? low : high; } } var ksp = new kSubsetPartitions(21, 8); document.write("Number of k-subset partitions for n,k = 21,8 &rarr; " + ksp.total.toLocaleString("en-US") + "<br>"); for (var tests = 10; tests; tests--) { var rnd = Math.floor(Math.random() * ksp.total); document.write("Partition " + rnd.toLocaleString("en-US", {minimumIntegerDigits: 15}) + " &rarr; " + ksp.partition(rnd) + "<br>"); }

No es realmente necesario almacenar los patrones de bits para cada tipo de partición, ya que se pueden recrear a partir de su índice (ver, por ejemplo, el segundo algoritmo en esta respuesta ). Si solo almacena el total acumulado del número de variaciones por tipo de partición, eso reduce a la mitad el requisito de memoria.

Este segundo ejemplo de código en C ++ almacena solo los conteos y devuelve la partición como una matriz de n longitud que contiene el número de pieza para cada elemento. Ejemplo de uso al final del código. En mi computadora, crea la lista de recuento para n = 40 yk = 32 en 12 segundos y luego devuelve 10 millones de particiones en 24 segundos.

Los valores de n pueden ir hasta 65 y k hasta 64, pero para algunas combinaciones el número de particiones será mayor que 2 64 , lo que, obviamente, este código no puede manejar. Si lo traduces a Python, no debería haber tales restricciones. (Nota: habilite la verificación de cero en la función del coeficiente binomial si k = 1).

class kSubsetPartitions { std::vector <uint64_t> count; uint64_t total; uint8_t n; uint8_t k; public: kSubsetPartitions(uint8_t n, uint8_t k) { this->total = 0; this->n = n; this->k = k; uint64_t bits = ((uint64_t) 1 << k - 1) - 1; uint64_t types = choose(n - 1, k - 1); this->count.reserve(types); while (types--) { this->total += variations(bits); this->count.push_back(this->total); bits = next(bits); } } uint64_t range() { return this->total; } void partition(uint64_t rank, uint8_t *buffer) { uint64_t range = 1; uint64_t type = binarySearch(rank); if (type) { rank -= this->count[type - 1]; range = this->count[type] - this->count[type - 1]; } format(pattern(type), range, rank, buffer); } private: uint64_t pattern(uint64_t type) { uint64_t steps, bits = 0, mask = (uint64_t) 1 << this->n - 2; uint8_t ones = this->k - 1; for (uint8_t i = this->n - 1; i; i--, mask >>= 1) { if (i > ones) { steps = choose(i - 1, ones); if (type >= steps) { type -= steps; bits |= mask; --ones; } } else bits |= mask; } return bits; } uint64_t choose(uint8_t x, uint8_t y) { // C(x,y) using Pascal''s Triangle static std::vector <std::vector <uint64_t> > triangle; if (triangle.empty()) { triangle.resize(this->n); triangle[0].push_back(1); for (uint8_t i = 1; i < this->n; i++) { triangle[i].push_back(1); for (uint8_t j = 1; j < i; j++) { triangle[i].push_back(triangle[i - 1][j - 1] + triangle[i - 1][j]); } triangle[i].push_back(1); } } return triangle[x][y]; } void format(uint64_t bits, uint64_t range, uint64_t rank, uint8_t *buffer) { uint64_t mask = (uint64_t) 1 << this->n - 2; uint8_t max = 0, part; *buffer = 0; while (mask) { if (!(bits & mask)) { range /= (max + 1); part = rank / range; rank %= range; } else part = ++max; *(++buffer) = part; mask >>= 1; } } uint64_t binarySearch(uint64_t rank) { uint64_t low = 0, mid, high = this->count.size() - 1; while (high - low > 1) { mid = (high + low + 1) / 2; if (rank < this->count[mid]) high = mid; else low = mid; } return rank < this->count[low] ? low : high; } uint64_t variations(uint64_t bits) { uint64_t product = 1; uint64_t mask = (uint64_t) 1 << this->n - 2; uint8_t factor = 1; while (mask) { if (bits & mask) ++factor; else product *= factor; mask >>= 1; } return product; } uint64_t next(uint64_t a) { // Gosper''s Hack // if (!a) return a; // k=1 => a=0 => c=0 => division by zero! uint64_t c = (a & -a), r = a + c; return (((r ^ a) >> 2) / c) | r; } }; // USAGE EXAMPLE: // uint8_t buffer[40]; // kSubsetPartitions* ksp = new kSubsetPartitions(40, 32); // uint64_t range = ksp->range(); // ksp->partition(any_integer_below_range, buffer);

A continuación se muestra una descripción general de los valores de n y k que dan como resultado más de 2 64 particiones y causan desbordamiento en el código anterior. Hasta n = 26, todos los valores de k dan resultados válidos.

25: - 26: - 27: 8-13 28: 7-15 29: 6-17 30: 6-18 31: 5-20 32: 5-21 33: 5-22 34: 4-23 35: 4-25 36: 4-26 37: 4-27 38: 4-28 39: 4-29 40: 4-31 41: 4-32 42: 4-33 43: 3-34 44: 3-35 45: 3-36 46: 3-37 47: 3-38 48: 3-39 49: 3-40 50: 3-42 51: 3-43 52: 3-44 53: 3-45 54: 3-46 55: 3-47 56: 3-48 57: 3-49 58: 3-50 59: 3-51 60: 3-52 61: 3-53 62: 3-54 63: 3-55 64: 3-56 65: 3-57

Una versión que no almacena el número de particiones por tipo es posible y casi no requiere memoria. La búsqueda de las particiones que corresponden a enteros seleccionados al azar sería más lenta, pero si la selección de los enteros se ordenara, podría ser incluso más rápida que la versión que requiere una clasificación binaria para cada búsqueda.

Comenzaría con el primer patrón de bits, calcularía el número de particiones de este tipo, vería si los primeros enteros entran en este rango, calcule sus particiones y luego continúe con el siguiente patrón de bits.