Найти все K-подмножество разделов


Следующий код генерирует все \$к\$-подмножеств данного массива. А \$к\$-подмножество множества \х $\$ - это раздел всех элементов в \Х $\$ и \$к\$ непустые подмножества.

Таким образом, для {1,2,3,4} в 3-подмножество {{1,2},{3},{4}}.

Я ищу улучшения в алгоритм или код. В частности, есть лучший способ, чем с помощью копирования.deepcopy? Есть некоторые модуле itertools магия, которая делает это уже?

import copy
arr = [1,2,3,4]

def t(k,accum,index):
    print accum,k
    if index == len(arr):
        if(k==0):
            return accum;
        else:
            return [];

    element = arr[index];
    result = []

    for set_i in range(len(accum)):
        if k>0:
            clone_new = copy.deepcopy(accum);
            clone_new[set_i].append([element]);
            result.extend( t(k-1,clone_new,index+1) );

        for elem_i in range(len(accum[set_i])):
            clone_new = copy.deepcopy(accum);
            clone_new[set_i][elem_i].append(element)
            result.extend( t(k,clone_new,index+1) );

    return result

print t(3,[[]],0);


Комментарии
3 ответа

Очень эффективный алгоритм (алгоритм у) описывается в Кнут Искусство программирования, Том 4, выпуск 3Б найти все набор секций с заданным числом блоков. Ваш алгоритм, несмотря на простоту в экспресс, по сути является перебором дерево, которое не является эффективным.

Поскольку алгоритм кнута не очень лаконичен, его осуществление является длительным, а также. Отметим, что реализация ниже перемещение элемента между блоками по одному за раз и не нужно поддерживать аккумулятор, содержащий все промежуточные результаты. По этой причине, никакое копирование не требуется.

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)

Примеры:

def pretty_print(parts):
print '; '.join('|'.join(''.join(str(e) for e in loe) for loe in part) for part in parts)

>>> pretty_print(algorithm_u([1, 2, 3, 4], 3))
12|3|4; 1|23|4; 13|2|4; 1|2|34; 1|24|3; 14|2|3

>>> pretty_print(algorithm_u([1, 2, 3, 4, 5], 3))
123|4|5; 12|34|5; 1|234|5; 13|24|5; 134|2|5; 14|23|5; 124|3|5; 12|3|45; 1|23|45; 13|2|45; 1|2|345; 1|24|35; 14|2|35; 14|25|3; 1|245|3; 1|25|34; 13|25|4; 1|235|4; 12|35|4; 125|3|4; 15|23|4; 135|2|4; 15|2|34; 15|24|3; 145|2|3

Результаты измерений:

$ python -m timeit "import test" "test.t(3, [[]], 0, [1, 2, 3, 4])"
100 loops, best of 3: 2.09 msec per loop

$ python -m timeit "import test" "test.t(3, [[]], 0, [1, 2, 3, 4, 5])"
100 loops, best of 3: 7.88 msec per loop

$ python -m timeit "import test" "test.t(3, [[]], 0, [1, 2, 3, 4, 5, 6])"
10 loops, best of 3: 23.6 msec per loop

$ python -m timeit "import test" "test.algorithm_u([1, 2, 3, 4], 3)"
10000 loops, best of 3: 26.1 usec per loop

$ python -m timeit "import test" "test.algorithm_u([1, 2, 3, 4, 5, 6, 7, 8], 3)"
10000 loops, best of 3: 28.1 usec per loop

$ python -m timeit "import test" "test.algorithm_u([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16], 3)"
10000 loops, best of 3: 29.4 usec per loop

Обратите внимание, что Т работает намного медленнее, чем algorithm_u для тех же входных данных. Кроме того, Т , работает медленнее геометрической прогрессии с каждой дополнительной входной сигнал, в то время как algorithm_u работает почти так же быстро, для двух-и четырехместные входной размер.

19
ответ дан 18 апреля 2011 в 08:04 Источник Поделиться

Вот обязательные рекурсивный вариант:

def k_subset(s, k):
if k == len(s):
return (tuple([(x,) for x in s]),)
k_subs = []
for i in range(len(s)):
partials = k_subset(s[:i] + s[i + 1:], k)
for partial in partials:
for p in range(len(partial)):
k_subs.append(partial[:p] + (partial[p] + (s[i],),) + partial[p + 1:])
return k_subs

Это возвращает кучу копий, которые могут быть удалены с помощью

def uniq_subsets(s):
u = set()
for x in s:
t = []
for y in x:
y = list(y)
y.sort()
t.append(tuple(y))
t.sort()
u.add(tuple(t))
return u

Поэтому конечный продукт можно было с

print uniq_subsets(k_subset([1, 2, 3, 4], 3))

set([
((1,), (2,), (3, 4)),
((1,), (2, 4), (3,)),
((1, 3), (2,), (4,)),
((1, 4), (2,), (3,)),
((1,), (2, 3), (4,)),
((1, 2), (3,), (4,))
])

Вау, это очень плохо и очень unpythonic. :(

Редактировать: Да, я понимаю, что повторно проблемы не помочь с рассмотрения оригинальное решение. Я надеялся получить некоторое представление о вашем решении, делая так. Если это совершенно бесполезно, завалю и я удалю ответ.

Правка 2: я удалил ненужные второго рекурсивного вызова. Это короче, но все равно не очень элегантно.

3
ответ дан 30 марта 2011 в 07:03 Источник Поделиться

Не смог найти никаких супер быстрых побед в itertools.

(Может быть, я не выглядел достаточно трудно.)
Однако я пришел с этой
он работает довольно медленно, но довольно лаконично:

from itertools import chain, combinations

def subsets(arr):
""" Note this only returns non empty subsets of arr"""
return chain(*[combinations(arr,i + 1) for i,a in enumerate(arr)])

def k_subset(arr, k):
s_arr = sorted(arr)
return set([frozenset(i) for i in combinations(subsets(arr),k)
if sorted(chain(*i)) == s_arr])

print k_subset([1,2,3,4],3)

Некоторые незначительные выигрывает по скорости, но менее сжатым, можно было бы сделать только в установленных//frozenset дела в конце, если не уникальных элементов в массиве, или использовать пользовательские расплющить функция или сумма(a_list, []), а не цепь(*a_list).

Если вам нужна скорость, вы, возможно, захотите подумать о другом языке или, может быть:
www.cython.org это довольно опрятно.
Вполне очевидно, что алгоритмы намного лучше, скорость-мудры для начинающих.

Кроме того, что может быть стоит посмотреть на это www.sagemath.org...
Это математическое окружение, построенное на Python, и например такие функции, как, подмножеств() , расплющить и т. д. И много комбинаторных вещей, которые там живут.

Ура,

Мэтт

3
ответ дан 13 апреля 2011 в 06:04 Источник Поделиться