屈服子組合

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

你應該採取的第一個元素（ 「A」）+中剩下的所有分區，因此讓：
「A」， 「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']