Python: поиск случайного раздела k-подмножества для данного списка
Следующий код генерирует все разделы длины k (k-подмножества разделов) для данного списка.
алгоритм можно найти в этой теме.
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)
мы знаем, что число k-подмножеств данного списка равно Stirling number, и оно может быть очень большим для некоторых больших списков.
приведенный выше код возвращает генератор Python, который может генерировать все возможные k-подмножества разделов для данного списка с вызовом его следующего метода. соответственно, если я хочу получить только один из этих разделов случайным образом, мне нужно либо вызвать следующий метод для некоторых случайных времен (что делает его очень медленным, если число Стирлинга велико), либо использовать метод itertools.islice для получения фрагмента размер один, который действительно медленный, как раньше.
Я стараюсь избегать перечисления всех разделов, потому что это будет пустая трата времени и скорости и даже памяти (потому что вычислений много, а память важна в моем случае).
Вопрос в том, как я могу сгенерировать только один из k-подмножеств без генерации остального? или, по крайней мере, сделать процедуру очень быстрой, чем описанная выше. Мне нужна производительность, потому что мне нужно получать только один из них каждый раз, и я запускаю приложение, возможно, более десяти миллионов раз.
Буду признателен за любую помощь.
РЕДАКТИРОВАТЬ: ПРИМЕР
список: { 1, 2, 3 }
при k = 3:
{ {1}, {2}, {3} }
при k = 2:
{ {1, 2}, {3} }
{ {1, 3}, {2} }
{ {1}, {2, 3} }
и для k = 1:
{ {1, 2, 3} }
Рассмотрим k = 2, есть ли способ, каким образом я могу генерировать только один из этих 3 разделов случайным образом, не генерируя другие 2? обратите внимание, что я хочу создать случайное разбиение для любого заданного k не только случайного разбиения любого k, что означает, что если я поставил k в 2, я хотел бы сгенерировать только один из этих 3 не один из всех 5.
Привет,
Мохаммад
Ответы
Ответ 1
Вы можете рассчитывать числа Стирлинга эффективно с помощью рекурсивного алгоритма, сохраняя ранее вычисленные значения:
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
Как только вы знаете, сколько вариантов есть, вы можете адаптировать этот рекурсивный код для создания определенного раздела:
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)
В качестве примера я написал тестовую программу, которая создает разные разделы из 4 чисел:
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])
Этот код печатает:
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]]
В качестве другого примера, 10 миллионов разделов 1,2,3,.. 14 на 4 части.
Этот код может генерировать все разделы за 44 секунды с помощью pypy.
Есть 50,369,882,873,307,917,364,901 перегородки 1,2,3,..., 40 на 4 части. Этот код может генерировать 10 миллионов из них за 120 секунд, когда pypy работает на одном процессоре.
Чтобы связать вещи, вы можете использовать этот код для создания единого случайного разбиения списка A на k непустых подмножеств:
import random
def random_ksubset(A,k):
i = random.randrange(0,count_part(len(A),k))
return gen_part(A,k,i)
Ответ 2
Как насчет чего-то вроде этого:
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])]
Это приводит к случайным разбиениям на k-подмножество следующим образом:
>>> 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])]
Этот метод удовлетворяет требованию OP для получения одного беспорядочно сгенерированного раздела без перечисления всех возможных разделов. Сложность памяти здесь линейна. Сложность выполнения - O (N log N) из-за сортировки. Полагаю, что это может быть возможно для линейного, если это важно, используя более сложный метод построения возвращаемого значения.
Как указывает @Leon, это удовлетворяет требованиям его варианта 2 при попытке определить проблему. То, что это не сделает, детерминистически генерирует раздел #N (это вариант Leon 1, который позволит вам случайным образом выбрать целое число N, а затем получить соответствующий раздел). Леон разъяснение важно, потому что, чтобы удовлетворить дух вопроса, каждое возможное разбиение коллекции должно генерироваться с равной вероятностью. В нашей игрушечной проблеме это так:
>>> 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})
Однако. В общем, этот метод не генерирует каждый раздел с равной вероятностью. Рассмотрим:
>>> 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)]
Мы видим здесь, что мы с большей вероятностью создадим "более сбалансированные" разделы (потому что есть больше способов их создания). Разделы, содержащие одиночные множества, производятся реже.
Похоже, что эффективный метод равномерной выборки над k-разбиениями наборов является нерассмотренным вопросом исследования (также см. mathoverflow). Nijenhuis и Wilf дают код для выборки из всех разделов (глава 12), который может работать с тестированием отклонения, а @PeterdeRivaz answer также может равномерно отображать k-раздел. Недостатком обоих этих методов является то, что они требуют вычисления чисел Стирлинга, которые экспоненциально растут по n, а алгоритмы рекурсивны, что, я думаю, заставит их замедлить работу на больших входах. Поскольку вы упоминаете "миллионы" разделов в своем комментарии, я думаю, что эти подходы будут доступны только до определенного размера ввода.
а. Ниенхейс и Х. Вильф. Комбинаторные алгоритмы для компьютеров и Калькуляторы. Academic Press, Orlando FL, второе издание, 1978 г.
Изучение варианта Леона 1 может быть интересным. Здесь грубая процедура для детерминированного создания определенного раздела коллекции с использованием предложения @Amadan для принятия целочисленного значения, интерпретируемого как k-мерное число. Обратите внимание, что не каждое целочисленное значение создает допустимый раздел подмножества k (потому что мы запрещаем пустые подмножества):
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]))
Мы можем подтвердить, что это правильно генерирует номера Стирлинга:
>>> 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
Это может также обеспечить возможность создания каждого возможного раздела с равной вероятностью; Я не совсем уверен. Здесь тестовый пример, где он работает:
>>> 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})
Другой рабочий пример:
>>> 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})
Итак, чтобы обернуть это в функцию:
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
И тогда мы можем сделать:
>>> 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})})
Ответ 3
tl; dr:
Разделы k-подмножества для заданных n и k можно разделить на типы, основанные на том, какие элементы первыми входят в пустые части. Каждый из этих типов представлен битовой схемой с n-1 битами, из которых установлены k-1. Хотя количество разделов огромно (задано вторым числом Стирлинга), количество типов намного меньше, например:
n = 21, k = 8
количество разделов: S (21,8) = 132,511,015,347,084
количество типов: (n-1 выберите k-1) = 77,520
Вычисление того, сколько разделов существует для каждого типа, прост, основываясь на позиции нулей в битовой схеме. Если вы создадите список всех типов (путем итерации по всем n-разрядным шаблонам n: k) и сохраните общее количество количества разделов, вы можете затем использовать двоичный поиск в этом списке, чтобы найти тип раздела с (в разделе Log 2 (n-1 выберите k-1) шаги 17 для примера выше), а затем перевести бит-шаблон в раздел и вычислить, в какую часть проходит каждый элемент (в n шагов). Каждая часть этого метода может быть выполнена итеративно, не требуя рекурсии.
Здесь нерекурсивное решение. Я пытался опрокинуться, но может (частично) накладываться на ответ Питера или существующие методы.
Если у вас есть набор из n элементов, например. с n = 8:
{a, b, c, d, e, f, g, h}
то k-подмножество разделов примет эту форму, например. с k = 5:
{a, e} {b, c, h} {d} {f} {g}
Этот раздел также может быть записан как:
1,2,2,3,1,4,5,2
в котором перечислены части, в которые входит каждый из элементов. Таким образом, эта последовательность из n цифр со значениями от 1 до k представляет собой k-подмножество из n элементов.
Однако не все такие последовательности являются допустимыми разделами; каждая цифра от 1 до k должна присутствовать, в противном случае будут пустые части:
1,2,2,3,1,3,5,2 → {a, e} {b, c, h} {d, f} {} {g}
Кроме того, чтобы избежать дублирования, цифру x можно использовать только после использования цифры x-1. Таким образом, первая цифра всегда 1, вторая может быть не более 2 и так далее. Если в примере мы используем цифры 4 и 5 до 3, мы получаем дубликаты разделов:
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}
Когда вы группируете разделы на основе того, когда каждая часть сначала используется, вы получаете следующие типы:
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
На приведенной выше диаграмме разбиение типа:
1,2,12,3,123,4,1234,5
означает, что:
a переходит в часть 1
b входит в часть 2
c входит в часть 1 или 2
d входит в часть 3
e переходит в часть 1, 2 или 3
f входит в часть 4
г входит в часть 1, 2, 3 или 4
ч переходит в часть 5
Таким образом, разделы этого типа имеют цифру, которая может иметь 2 значения, цифру, которая может иметь 3 значения, и цифру, которая может иметь 4 значения (это указано в третьем столбце на диаграмме выше). Таким образом, существует в общей сложности 2 раза; 3 раза; 4 раздела этого типа (как указано в колонках 4 и 5). Сумма их, конечно, является числом Стирлинга: S (8,5) = 1050.
Второй столбец на диаграмме - это еще один способ обозначения типа раздела: после начала с 1 каждая цифра представляет собой либо цифру, которая использовалась ранее, либо шаг вверх (т.е. самая высокая цифра, используемая до сих пор + 1). Если мы представим эти два параметра на 0 и 1, получим, например:
1,2,12,3,123,4,1234,5 → 1010101
где 1010101 означает:
Начните с 1
1 → шаг до 2
0 → повторить 1 или 2
1 → шаг до 3
0 → повторить 1, 2 или 3
1 → шаг до 4
0 → повторить 1, 2, 3 или 4
1 → шаг до 5
Таким образом, каждая двоичная последовательность с n-1 цифрами и k-1 представляет собой тип раздела. Мы можем рассчитать количество разделов типа, итерируя по цифрам слева направо, увеличивая коэффициент, когда находим один, и умножаем его с коэффициентом, когда находим нуль, например:
1,2,12,3,123,4,1234,5 → 1010101
Начните с продукта = 1, factor = 1
1 → коэффициент приращения: 2
0 → продукт & раз; factor = 2
1 → коэффициент приращения: 3
0 → продукт & раз; factor = 6
1 → коэффициент приращения: 4
0 → продукт & раз; factor = 24
1 → коэффициент приращения: 5
И снова для этого примера мы обнаруживаем, что существует 24 раздела этого типа. Таким образом, подсчет разделов каждого типа может быть выполнен путем итерации по всем n-1-разрядным целым с наборами k-1, используя любой метод (например, Gosper Hack):
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
Поиск случайного раздела означает выбор числа от 1 до S (n, k), переходящего количество отсчетов на тип раздела при сохранении общего числа (столбец 3 выше) и выбор соответствующего типа раздела, а затем вычисление значение повторяющихся цифр, например:
S (8,5) = 1050 - случайный выбор: например. 333
тип: 1011010 → 1,2,12,3,4,1234,5,12345
диапазон: 301 - 340
вариация: 333 - 301 = 32
цифры: 2, 4, 5
значные значения: 20, 5, 1
вариация: 32 = 1 & times; 20 + 2 & times; 5 + 2 & times; 1
цифры: 1, 2, 2 (0-based) → 2, 3, 3 (на основе 1)
раздел: 1,2,2,3,4,3,5,3
и 333-й раздел из 8 элементов в 5 частях:
1,2,2,3,4,3,5,3 → {a} {b, c} {d, f, h} {e} {g}
Существует несколько вариантов превращения этого кода в код; если вы сохраняете n-1-разрядные числа в качестве общего итога, вы можете выполнять последующий поиск, используя двоичный поиск по списку, длина которого C (n-1, k-1), чтобы уменьшить сложность по времени от O (C (n-1, k-1)) до O (Log 2 (C (n-1, k-1))).
Я сделал первый тест на JavaScript (извините, я не говорю на Python); это не очень, но он демонстрирует метод и довольно быстро. Примером является случай n = 21 и k = 8; он создает таблицу счетчиков для 77 520 типов разделов, возвращает общее количество разделов 132,511,015,347,084, а затем извлекает 10 случайно выбранных разделов в этом диапазоне. На моем компьютере этот код возвращает миллион случайно выбранных разделов за 3,7 секунды. (примечание: код основан на нуле, в отличие от приведенного выше объяснения)
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 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 → " +
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}) + " → " + ksp.partition(rnd) + "<br>");
}
