Следующий код генерирует все разделы длины 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.
Привет,
Мохаммад
