rango - muestra aleatoria en python

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

Question

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

Answer 1

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)

Answer 2

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})})

Answer 3

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 ₂ (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 ₂ (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 ⁶⁴ , 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 ⁶⁴ 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.