找到可能的唯一固定長度排列數的最有效方法？

Question

我有這個詞典：

num_dict = { 
    (2, 3): [(2, 2), (4, 4), (4, 5)], 
    (2, 2): [(2, 3), (4, 4), (4, 5)], 
    (4, 5): [(4, 4)], 
    (1, 0): [(1, 1), (2, 2), (2, 3), (4, 4), (4, 5)], 
    (4, 4): [(4, 5)], 
    (1, 1): [(1, 0), (2, 2), (2, 3), (4, 4), (4, 5)], 
    } 

我需要找到的3個長每個元組的第一個值的組合的最大數量，只有每個鍵的值可以繼續說關鍵。

我現在尋找所有獨特的（3長）的組合代碼是這樣的：

ans_set = set() 
for x in num_dict: 
    for y in num_dict[x]: 
     for z in num_dict[y]: 
      ans_set.add((x[0], y[0], z[0])) 
return len(ans_set) 

這將返回10和ans_set結束是：

{ 
(2, 2, 2), (1, 2, 2), (1, 4, 4), 
(2, 2, 4), (1, 1, 2), (4, 4, 4), 
(1, 2, 4), (1, 1, 4), (1, 1, 1), 
(2, 4, 4) 
} 

但我不實際上關心的是套件，只是它們的數量

這種方法不是特別有效，因爲它實際上會生成所有可能的組合並將其放入一組中。

我不需要知道每個獨特的組合，我只需要知道有多少。

我有一種感覺，這可以做到，也許使用值列表的長度？但我無法繞過它。

澄清關於我需要什麼的問題，因爲我意識到我可能沒有以最清楚的方式解釋它。

最後編輯

我發現通過重新評估什麼，我需要它做的事找三倍數量的最佳途徑。這個方法實際上並沒有找到三元組，它只是對它們進行計數。

def foo(l): 
    llen = len(l) 
    total = 0 
    cache = {} 
    for i in range(llen): 
     cache[i] = 0 
    for x in range(llen): 
     for y in range(x + 1, llen): 
      if l[y] % l[x] == 0: 
       cache[y] += 1 
       total += cache[x] 
    return total 

而且這裏有一個版本的功能解釋，因爲它去思考過程（對於龐大的名單，因爲垃圾郵件打印雖然不是很好）：

def bar(l): 
    list_length = len(l) 
    total_triples = 0 
    cache = {} 
    for i in range(list_length): 
     cache[i] = 0 
    for x in range(list_length): 
     print("\n\nfor index[{}]: {}".format(x, l[x])) 
     for y in range(x + 1, list_length): 
      print("\n\ttry index[{}]: {}".format(y, l[y])) 
      if l[y] % l[x] == 0: 
       print("\n\t\t{} can be evenly diveded by {}".format(l[y], l[x])) 
       cache[y] += 1 
       total_triples += cache[x] 
       print("\t\tcache[{0}] is now {1}".format(y, cache[y])) 
       print("\t\tcount is now {}".format(total_triples)) 
       print("\t\t(+{} from cache[{}])".format(cache[x], x)) 
      else: 
       print("\n\t\tfalse") 
    print("\ntotal number of triples:", total_triples) 

Answer 1

，如果我得到你的權利：

from itertools import combinations 

num_dict = { 
    (2, 3): [(2, 2), (4, 4), (4, 5)], 
    (2, 2): [(2, 3), (4, 4), (4, 5)], 
    (4, 5): [(4, 4)], 
    (1, 0): [(1, 1), (2, 2), (2, 3), (4, 4), (4, 5)], 
    (4, 4): [(4, 5)], 
    (1, 1): [(1, 0), (2, 2), (2, 3), (4, 4), (4, 5)] 
    } 
set(combinations([k[0] for k in num_dict.keys()], 3)) 

輸出：

{(1, 4, 1), 
(2, 1, 1), 
(2, 1, 4), 
(2, 2, 1), 
(2, 2, 4), 
(2, 4, 1), 
(2, 4, 4), 
(4, 1, 1), 
(4, 1, 4), 
(4, 4, 1)} 

而且len()是10

所以基本上你會怎麼做，用itertools.combinations讓所有組合，從一個長3字典鍵的第一要素，然後讓set消除重複元素的東西。

UPDATE

既然你期望的輸出數據

你可以做以下

from itertools import combinations_with_replacement 
list(combinations_with_replacement(set([k[0] for k in num_dict.keys()]), 3)) 

輸出更新的問題：

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

UPD2

所以關於時間消耗我已經跑了

num_dict = { 
    (2, 3): [(2, 2), (4, 4), (4, 5)], 
    (2, 2): [(2, 3), (4, 4), (4, 5)], 
    (4, 5): [(4, 4)], 
    (1, 0): [(1, 1), (2, 2), (2, 3), (4, 4), (4, 5)], 
    (4, 4): [(4, 5)], 
    (1, 1): [(1, 0), (2, 2), (2, 3), (4, 4), (4, 5)] 
    } 
def a(num_dict): 
    ans_set = set() 
    for x in num_dict: 
     for y in num_dict[x]: 
      for z in num_dict[y]: 
       ans_set.add((x[0], y[0], z[0])) 
    return len(ans_set) 
def b(num_dict): 
    from itertools import combinations_with_replacement 
    return len(list(combinations_with_replacement(set([k[0] for k in num_dict.keys()]), 3))) 
%timeit a(num_dict) 
%timeit b(num_dict) 

而且結果是：

The slowest run took 4.90 times longer than the fastest. This could mean that an intermediate result is being cached. 
100000 loops, best of 3: 12.1 µs per loop 

The slowest run took 5.37 times longer than the fastest. This could mean that an intermediate result is being cached. 
100000 loops, best of 3: 4.77 µs per loop 

這樣的解決方案，我在這裏介紹的是快2倍倍。