Подходящие подкомпонования

Question

Мне нужна функция, которая возвращает подсегменты для данного сегмента. Например, sub_combinations("ABCD") должен давать:

("A", "B", "C", "D") 
("A", "B", "CD") 
("A", "BC", "D") 
("A", "BCD") 
("AB", "C", "D") 
("AB", "CD") 
("ABC", "D") 
("ABCD") 
("ABD", "C") * 
("AC", "BD") * 
("AC", "B", "D") * 
("ACD", "B") * 
("AD", "BC") * 
("AD", "B", "C") * 

("A","C","B","D") не действует, так как он не в порядке последовательности. Другими словами, вместо ("A","B","C","D").

("AC", "B", "D") действителен, так как «C» следует «A» в последовательном порядке, а «B» следует за «AC».

Это, насколько я получил:

def sub_combinations(segment): 
     for i in range(1, len(segment)): 
       for j in sub_combinations(segment[i:]): 
         yield (segment[:i],) + j 
     yield (segment,) 

for i in sub_combinations("ABCD"): 
     print(i) 

('A', 'B', 'C', 'D') 
('A', 'B', 'CD') 
('A', 'BC', 'D') 
('A', 'BCD') 
('AB', 'C', 'D') 
('AB', 'CD') 
('ABC', 'D') 
('ABCD',) 

Однако это не хватает этих дополнительных комбинаций.

Любые предложения о том, как действовать?

Answer 1

Вы можете изменить свой код следующим образом:

def sub_combinations(segment): 
    if len(segment) == 1: 
    yield (segment,) 
    else: 
    for j in sub_combinations(segment[1:]): 
     yield (segment[0],)+j 
     for k in range(len(j)): 
     yield (segment[0]+j[k],)+j[:k]+j[k+1:] 

Если сегмент содержит только один символ результат вполне легко. В противном случае отделите первый символ и определите все разделы остальной части вашей строки. Впоследствии у вас есть следующие (отличные) решения: разделительный символ строит отдельный кортеж, или вы можете добавить его в любой из кортежей вашего предыдущего решения.

Из-за рекурсивных вызовов этот метод строит набор решений из одного символьного случая до полного аргумента.

Ваш пример случай дает следующий результат:

('A', 'B', 'C', 'D') 
('AB', 'C', 'D') 
('AC', 'B', 'D') 
('AD', 'B', 'C') 
('A', 'BC', 'D') 
('ABC', 'D') 
('AD', 'BC') 
('A', 'BD', 'C') 
('ABD', 'C') 
('AC', 'BD') 
('A', 'B', 'CD') 
('AB', 'CD') 
('ACD', 'B') 
('A', 'BCD') 
('ABCD',) 

Answer 2

Ну, используя itertools library, я придумал это:

from itertools import permutations 
def sub_combinations(iterable, r): 
    pool = tuple(iterable) 
    n = len(pool) 
    for indices in permutations(range(n), r): 
     if sorted(indices) == list(indices): 
      yield tuple(pool[i] for i in indices) 

def combinations(s): 
    l = len(s) 
    for i in range(1, l+1): 
     for item in sub_combinations(s, i): 
      yield item 

Answer 3

Вы должны сделать первый элемент («А») + все разделы, что осталось, так что получить:
«А», «AB» , «AC», «AD», «ABC», «ABD», «ACD», «ABCD», затем для каждого из этих наборов вам необходимо рассмотреть, что осталось и применить ту же процедуру (выберите первый элемент и продолжите все разделы того, что остается) и т. д.

Таким образом, вы получите нужный список без повторений.

Answer 4

1. Генерация всех разбиений множества {'A', 'B', 'C', 'D'}
2. Для каждого раздела, сцепить внутренние наборы и сортирует внешний набор.

Поиск заданного раздела дает this, так и с небольшой модификацией и преобразования кода для Python 3 мы можем получить

def sub_combinations(set_): 
    if not set_: 
     yield [] 
     return 
    for i in range(1<<(len(set_)-1)): 
     parts = [[], []] 
     for item in set_: 
      parts[i&1].append(item) 
      i >>= 1 
     for b in sub_combinations(parts[1]): 
      yield sorted(''.join(x) for x in [parts[0]]+b) 

for p in sub_combinations("abcd"): 
    print(p) 

который печатает

['abcd'] 
['a', 'bcd'] 
['acd', 'b'] 
['ab', 'cd'] 
['a', 'b', 'cd'] 
['abd', 'c'] 
['ac', 'bd'] 
['a', 'bd', 'c'] 
['ad', 'bc'] 
['ad', 'b', 'c'] 
['abc', 'd'] 
['a', 'bc', 'd'] 
['ac', 'b', 'd'] 
['ab', 'c', 'd'] 
['a', 'b', 'c', 'd']