Эффективный способ расчета конкретной длины комбинации соседних данных? - PullRequest
Новая
       38

Эффективный способ расчета конкретной длины комбинации соседних данных?

1 голос
/ 07 июля 2019

У меня есть список элементов, из которых я хотел бы определить все возможные комбинации, которые можно упорядочить - сохраняя их порядок - чтобы получить 'n' групп

Так, например, если яЕсли у вас есть упорядоченный список A, B, C, D, E и требуется только две группы, четыре решения будут такими: 

ABCD, E
ABC, DE
AB, CDE
A, BCDE

Теперь, с некоторой помощью из другого сообщения StackOverflow Я придумал работоспособное решение для перебора, которое вычисляет все возможные комбинации всех возможных группировок, из которых я просто извлекаю те случаи, которые соответствуют моему целевому числу группировок.

Для разумного количества элементов этоэто нормально, но по мере того, как я увеличиваю количество элементов, количество комбинаций увеличивается очень очень быстро, и мне стало интересно, может ли быть разумный способ ограничить решения, рассчитанные только теми, которые соответствуют числу целевых групп?

Код пока выглядит следующим образом: 

import itertools
import string
import collections

def generate_combination(source, comb):
    res = []
    for x, action in zip(source,comb + (0,)):
        res.append(x)
        if action == 0:
            yield "".join(res)
            res = []

#Create a list of first 20 letters of the alphabet
seq = list(string.ascii_uppercase[0:20])
seq

['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H ',' I ',' J ',' K ',' L ',' M ',' N ',«O», «P», «Q», «R», «S», «T»] 

#Generate all possible combinations
combinations = [list(generate_combination(seq,c)) for c in itertools.product((0,1), repeat=len(seq)-1)]
len(combinations)

524288 

#Create a list that counts the number of groups in each solution, 
#and counter to allow easy query
group_counts = [len(i) for i in combinations]
count_dic = collections.Counter(group_counts)
count_dic[1], count_dic[2], count_dic[3], count_dic[4], count_dic[5], count_dic[6]

(1, 19, 171,969, 3876, 11628)

Итак, как вы можете видеть, в то время как более полумиллиона комбинаций были рассчитаны, если бы я только хотел иметь комбинации длиной = 5, вычислилось только 3876

Есть предложения?

1 Ответ

1 голос
/ 07 июля 2019

Разделение seq на 5 частей эквивалентно выбору из 4 мест в range(1, len(seq)), для которых необходимо вырезать seq. Таким образом, вы можете использовать itertools.combinations(range(1, len(seq)), 4) для генерации всех разделов seq на 5 частей: 

import itertools as IT
import string

def partition_into_n(iterable, n, chain=IT.chain, map=map):
    """
    Return a generator of all partitions of iterable into n parts.
    Based on http://code.activestate.com/recipes/576795/ (Raymond Hettinger)
    which generates all partitions.
    """
    s = iterable if hasattr(iterable, '__getitem__') else tuple(iterable)
    size = len(s)
    first, middle, last = [0], range(1, size), [size]
    getitem = s.__getitem__
    return (map(getitem, map(slice, chain(first, div), chain(div, last)))
            for div in IT.combinations(middle, n-1))

seq = list(string.ascii_uppercase[0:20])
ngroups = 5
for partition in partition_into_n(seq, ngroups):
    print(' '.join([''.join(grp) for grp in partition]))

print(len(list(partition_into_n(seq, ngroups))))

выходы 

A B C D EFGHIJKLMNOPQRST
A B C DE FGHIJKLMNOPQRST
A B C DEF GHIJKLMNOPQRST
A B C DEFG HIJKLMNOPQRST
...
ABCDEFGHIJKLMNO P Q RS T
ABCDEFGHIJKLMNO P QR S T
ABCDEFGHIJKLMNO PQ R S T
ABCDEFGHIJKLMNOP Q R S T
3876
...