最小限の組み合わせを見つける方法[Python> itertools> product]：コードレビュー

Question

itertools.product関数が返す可能性のあるすべての組み合わせを計算せずに、このコードを改善する方法を教えてください。 効率的に行うための他の解決方法はありますか？

これは私が試したものです：

import itertools 

mylist = [[1,2,3],[1,3,4],[1,2,3]] 

k = [set(i) for i in list(itertools.product(*mylist))] 
k = sorted(k) 
D_all = list(k for k, _ in itertools.groupby(k)) 
D_all.sort(key=len) 


# Finding and displaying the minimum order-split combination 
l = len(D_all[0]) 
print("Minimum number of Distributor Combination found is: {}".format(l)) 
print("The Possible combinations of {} are: ".format(l)) 
D_best = [] 
c = 0 
for n,i in enumerate(D_all): 

    if len(i)<=l: 
     c +=1 
     print("{}:{}".format(c,i)) 
     D_best.append(i) 
     if len(i)>l+1: break 

出力：

Minimum number of Distributor Combination found is: 1 
The Possible combinations of 1 are: 
1:{'1'} 
2:{'3'} 

Answer 1

私はそれを持っていると信じています。あなたはitertools.productyieldsそのtuplesのの決定的なの方法を利用することができます。 シングルトンがすべて生成されるときは、事前にわかっています。あなたはそれがいつ起こるかを計算しなければなりません。 3最初list（iはコードでpivotその呼）の最後の位置に表示されるので、この場合

from itertools import islice, product 
from functools import reduce 

mylist = [[1, 2, 3], [1, 3, 4], [1, 2, 3]] 

stop_cond = (len(mylist[0]) - 1) * reduce(lambda x, y: len(x) * len(y), mylist[1:]) 
pivot = mylist[0][-1] 
stop_cond += reduce(lambda x, y: (x.index(pivot) + 1) * (y.index(pivot) + 1), mylist[1:]) 

k = [set(item) for item in islice(product(*mylist), stop_cond)] 
print(k) #[{1}, {1, 2}, {1, 3}, {1, 3}, {1, 2, 3}, {1, 3}, {1, 4}, {1, 2, 4}, {1, 3, 4}, {1, 2}, {1, 2}, {1, 2, 3}, {1, 2, 3}, {2, 3}, {2, 3}, {1, 2, 4}, {2, 4}, {2, 3, 4}, {1, 3}, {1, 2, 3}, {1, 3}, {1, 3}, {2, 3}, {3}] 

、最後シングルトンは{3}であろう。そのシングルトンを得るためには、他のすべてのものを最初に取得しなければならず、それぞれに3 * 3の収率が必要です。これは9 + 9 = 18です。今度は、残りのリスト（1つのインデックスベースのシステム内）でそのインデックスを見つけ、それらを一緒に掛け合わせるだけです。