反向組合成陣列

Question

的至少數如果我們有，例如，這些9個組合，帶3個字符：

['ADG', 'ADH', 'BDG', 'BDH', 'CDG', 'CDH', 'AEG', 'AEH', 'AEI'] 

它們可以被壓縮成以下兩個數組：

[ ['A', 'B', 'C'], ['D'], ['G', 'H'] ] 

[ ['A'], ['E'], ['G', 'H', 'I'] ] 

其是能夠使用點積創建所有組合。

什麼是一種有效的算法，用於將任意長度的組合倒置爲最少數量的數組？

在此先感謝

Answer 1

下面是一種方法。瑣碎的分解只是每個字母一個。 （[['A'], ['D'], ['G']]爲'ADG'。）您從這些開始。如果它們只在一個位置上有所不同，則可以合併兩個。 （[['A'], ['D'], ['G']] + [['A'], ['E'], ['G']] = [['A'], ['D', 'E'], ['G']]）您嘗試合併所有內容以獲得有效的分解。

現在你有了所有有效的分解。但是選擇哪些？我只是嘗試所有的1元素選擇，然後是所有2元素選擇等。如果我們只通過幾次分解就找不到解決方案，那麼這將快速昂貴。但它對於這個例子來說工作得很好！

def matches(a, b): 
    return sum(1 if al == bl else 0 for (al, bl) in zip(a, b)) 

def subset(a, b): 
    return all(al.issubset(bl) for (al, bl) in zip(a, b)) 

def combinations(lists): 
    if len(lists) == 1: 
    for e in lists[0]: 
     yield [e] 
    else: 
    for e in lists[0]: 
     for c in combinations(lists[1:]): 
     yield [e] + c 

def decompose(words): 
    decomps = [[set(letter) for letter in word] for word in words] 
    queue = decomps[:] 
    while queue: 
    a = queue.pop() 
    for b in decomps: 
     if len(a) == len(b) and matches(a, b) == len(a) - 1 and not subset(a, b) and not subset(b, a): 
     merged = [al | bl for (al, bl) in zip(a, b)] 
     if merged not in decomps: 
      queue.append(merged) 
      decomps.append(merged) 
    decomps.reverse() # Put larger decomps at the start. 

    for n in range(1, len(words) + 1): 
    for ps in combinations([decomps] * n): 
     generated = set() 
     for p in ps: 
     generated.update(''.join(word) for word in combinations(p)) 
     if len(generated) == len(words): 
     return ps 

if __name__ == '__main__': 
    words = ['ADG', 'ADH', 'BDG', 'BDH', 'CDG', 'CDH', 'AEG', 'AEH', 'AEI'] 
    for p in decompose(words): 
    print p 

它打印：

[set(['A', 'C', 'B']), set(['D']), set(['H', 'G'])] 
[set(['A']), set(['E']), set(['I', 'H', 'G'])]