python - リストのデカルト積からソートされたタプル

Question

私は次のようなリストの辞書を持っています：

D = {'x': [15, 20],
     'y': [11, 12, 14, 16, 19],
     'z': [7, 9, 17, 18]}

一度に3つのキーを取得し（使用しますitertools.permutations）、各リストから1つの要素を取得して、結果を並べ替えることができるすべての方法を数えます。

上記の3つのキーの場合、2を取得します。

(15, 16, 17)
(15, 16, 18)

明らかに、ディクショナリ値のデカルト積を実行してから、ソートされた値を数えることができます。

answer = 0
for v_x, v_y, v_z in product(D['x'], D['y'], D['z']):
    if v_x < v_y < v_z:
        answer += 1

しかし、私はもっとうまくやることができますか？このソリューションは、キーの数と値であるリストの長さに比例しません。実りのない問い合わせを数行試しましたが、キーがリスト値にマップされる方法を利用する必要があるのではないかと思います。ただし、プログラムの残りの部分をやり直さなくても使用できる解決策があるかどうかを確認することは価値があると思いました。

ETA：これはより大きな例です。

D = {'a': [15, 20],
     'b': [8],
     'c': [11, 12, 14, 16, 19],
     'd': [7, 9, 17, 18],
     'e': [3, 4, 5, 6, 10, 13],
     'f': [2],
     'g': [1]}

14の有効な答えがあります：

(8, 9, 10)  (8, 9, 13) (8, 11, 13) (8, 12, 13) (8, 11, 17) (8, 11, 18) (8, 12, 17) (8, 12, 18) (8, 14, 17) (8, 14, 18) (8, 16, 17) (8, 16, 18) (15, 16, 17) (15, 16, 18)

Answer 1

これは賢明な方法で行うことができます。既存のリストごとに、その中の各数値を、それより大きい数値の次のリストのカウントにマップします。これらのカウントが得られたら、製品を慎重に合計すると、必要なカウントが得られます。

カウントを取得する方法の例を次に示します。

D = {'x': [15, 20],
     'y': [11, 12, 14, 16, 19],
     'z': [7, 9, 17, 18]}

order = ['x', 'y', 'z']
pairs = zip(order[:-1], order[1:])

counts = dict()
for pair in pairs:
    counts[pair[0]] = dict()
    for num in D[pair[0]]:
        counts[pair[0]][num] = len([el for el in D[pair[1]] if el >= num])

より明確な問題のために、OPの編集に続いて質問を編集します。

この問題に対する動的プログラミング ソリューションを構築する必要があります ( DP アルゴリズムのバックグラウンドがあると想定しています。そうでない場合は、いくつか見てください)。元の辞書にnキーがあるとします。次に、nそれぞれの長さの 3 つの辞書が必要です。キーと数値ごとに、タプルの 3 番目の要素にできるウェイの数を格納します(これは同じように 1 になります)。は、タプルの 2 番目の要素にできるウェイの数(これは から逆方向に動的に構築する必要があります) であり、タプルの最初の要素にできるウェイの数です。から構築する必要がありますM1M2M3M3[key][number]numberM2[key][number]numberM3M1[key][number]numberM1M2. 最終的な解は の要素の合計になりますM1。M1、 、 の更新規則と初期化はあなたM2に任せM3ます。

たとえば、 のエントリに入力するのM1[key][number]はdownkeys、 の後に続くキーのセットですkey。それぞれについてdownkey、 のエントリを見て、 whereが より大きいM2[downkey]値を合計します。すべての s にそのような数をすべて追加すると、 のエントリが得られます。したがって、これにより、およびの行を更新する必要がある順序に関するヒントが得られます。M2[downkey][num2]num2numberdownkeyM1[key][number]M1M2

これは大変な作業だと思われている場合は、確かにそうですが、それでも多項式であり、デカルト積のように指数関数的ではありません。デカルト積の方法でも、最初に 3 つのリストの可能な組み合わせをすべて見つけてからn、積を取り、それらをフィルタリングする必要があります。それは非常に高価です。動的計画法のソリューションは、毎回再計算するのではなく、各ステップからの情報を再利用します。

Answer 2

再帰的な解決策:

In [9]: f??
Definition: f(lists, triple)
Source:
def f(lists, triple):
    out = set()
    for i in range(len(lists)):
        for x in lists[i]:
            if len(triple) == 2 and triple[1] < x:
                out.add(triple + (x,))
            elif len(triple) == 0 or triple[0] < x:
                for j in range(i+1, len(lists)):
                    out.update(f(lists[j:], triple + (x,)))
    return out

入力：

In [10]: lists
Out[10]: 
[[15, 20],
 [8],
 [11, 12, 14, 16, 19],
 [7, 9, 17, 18],
 [3, 4, 5, 6, 10, 13],
 [2],
 [1]]

出力：

In [11]: out = f(lists, ())

In [12]: len(out)
Out[12]: 14

In [13]: out
Out[13]: 
set([(8, 9, 10),
     (8, 12, 18),
     (8, 11, 13),
     (8, 16, 17),
     (15, 16, 17),
     (8, 12, 17),
     (8, 14, 18),
     (15, 16, 18),
     (8, 11, 17),
     (8, 9, 13),
     (8, 14, 17),
     (8, 11, 18),
     (8, 12, 13),
     (8, 16, 18)])

Answer 3

与えた例では、すべての辞書リストが事前に並べ替えられているため、列挙の数を減らすために itertools.product を呼び出す前に、自分で並べ替えを行うことができます。

def count_sorted(x,y,z):
    from itertools import ifilter, product, imap

    _x = ifilter(lambda k: k<z[-1],x)
    _y = ifilter(lambda k: x[0]<k<z[-1],y)
    _z = ifilter(lambda k: k > x[0],z)

    return sum(imap(lambda t: t[0]<t[1]<t[2], product(_x,_y,_z)))


D = {'a': [15, 20],
     'b': [8],
     'c': [11, 12, 14, 16, 19],
     'd': [7, 9, 17, 18],
     'e': [3, 4, 5, 6, 10, 13],
     'f': [2],
     'g': [1]}

for key1,key2,key3 in itertools.permutations(D.keys(),3):
    print '[%s, %s, %s] has %i sorted combinations'%(key1,key2,key3,count_sorted(D[key1],D[key2],D[key3]))

結果：

[a, c, b] has 0 sorted combinations
[a, c, e] has 0 sorted combinations
[a, c, d] has 2 sorted combinations
[a, c, g] has 0 sorted combinations
[a, c, f] has 0 sorted combinations
[a, b, c] has 0 sorted combinations
[a, b, e] has 0 sorted combinations
[a, b, d] has 0 sorted combinations
[a, b, g] has 0 sorted combinations
[a, b, f] has 0 sorted combinations
[a, e, c] has 0 sorted combinations
[a, e, b] has 0 sorted combinations
[a, e, d] has 0 sorted combinations
[a, e, g] has 0 sorted combinations
[a, e, f] has 0 sorted combinations
[a, d, c] has 2 sorted combinations
[a, d, b] has 0 sorted combinations
[a, d, e] has 0 sorted combinations
[a, d, g] has 0 sorted combinations
[a, d, f] has 0 sorted combinations
[a, g, c] has 0 sorted combinations
[a, g, b] has 0 sorted combinations
[a, g, e] has 0 sorted combinations
[a, g, d] has 0 sorted combinations
[a, g, f] has 0 sorted combinations
[a, f, c] has 0 sorted combinations
[a, f, b] has 0 sorted combinations
[a, f, e] has 0 sorted combinations
[a, f, d] has 0 sorted combinations
[a, f, g] has 0 sorted combinations
[c, a, b] has 0 sorted combinations
[c, a, e] has 0 sorted combinations
[c, a, d] has 6 sorted combinations
[c, a, g] has 0 sorted combinations
[c, a, f] has 0 sorted combinations
[c, b, a] has 0 sorted combinations
[c, b, e] has 0 sorted combinations
[c, b, d] has 0 sorted combinations
[c, b, g] has 0 sorted combinations
[c, b, f] has 0 sorted combinations
[c, e, a] has 4 sorted combinations
[c, e, b] has 0 sorted combinations
[c, e, d] has 4 sorted combinations
[c, e, g] has 0 sorted combinations
[c, e, f] has 0 sorted combinations
[c, d, a] has 8 sorted combinations
[c, d, b] has 0 sorted combinations
[c, d, e] has 0 sorted combinations
[c, d, g] has 0 sorted combinations
[c, d, f] has 0 sorted combinations
[c, g, a] has 0 sorted combinations
[c, g, b] has 0 sorted combinations
[c, g, e] has 0 sorted combinations
[c, g, d] has 0 sorted combinations
[c, g, f] has 0 sorted combinations
[c, f, a] has 0 sorted combinations
[c, f, b] has 0 sorted combinations
[c, f, e] has 0 sorted combinations
[c, f, d] has 0 sorted combinations
[c, f, g] has 0 sorted combinations
[b, a, c] has 2 sorted combinations
[b, a, e] has 0 sorted combinations
[b, a, d] has 2 sorted combinations
[b, a, g] has 0 sorted combinations
[b, a, f] has 0 sorted combinations
[b, c, a] has 8 sorted combinations
[b, c, e] has 2 sorted combinations
[b, c, d] has 8 sorted combinations
[b, c, g] has 0 sorted combinations
[b, c, f] has 0 sorted combinations
[b, e, a] has 4 sorted combinations
[b, e, c] has 8 sorted combinations
[b, e, d] has 4 sorted combinations
[b, e, g] has 0 sorted combinations
[b, e, f] has 0 sorted combinations
[b, d, a] has 4 sorted combinations
[b, d, c] has 7 sorted combinations
[b, d, e] has 2 sorted combinations
[b, d, g] has 0 sorted combinations
[b, d, f] has 0 sorted combinations
[b, g, a] has 0 sorted combinations
[b, g, c] has 0 sorted combinations
[b, g, e] has 0 sorted combinations
[b, g, d] has 0 sorted combinations
[b, g, f] has 0 sorted combinations
[b, f, a] has 0 sorted combinations
[b, f, c] has 0 sorted combinations
[b, f, e] has 0 sorted combinations
[b, f, d] has 0 sorted combinations
[b, f, g] has 0 sorted combinations
[e, a, c] has 12 sorted combinations
[e, a, b] has 0 sorted combinations
[e, a, d] has 12 sorted combinations
[e, a, g] has 0 sorted combinations
[e, a, f] has 0 sorted combinations
[e, c, a] has 44 sorted combinations
[e, c, b] has 0 sorted combinations
[e, c, d] has 44 sorted combinations
[e, c, g] has 0 sorted combinations
[e, c, f] has 0 sorted combinations
[e, b, a] has 8 sorted combinations
[e, b, c] has 20 sorted combinations
[e, b, d] has 12 sorted combinations
[e, b, g] has 0 sorted combinations
[e, b, f] has 0 sorted combinations
[e, d, a] has 28 sorted combinations
[e, d, c] has 52 sorted combinations
[e, d, b] has 4 sorted combinations
[e, d, g] has 0 sorted combinations
[e, d, f] has 0 sorted combinations
[e, g, a] has 0 sorted combinations
[e, g, c] has 0 sorted combinations
[e, g, b] has 0 sorted combinations
[e, g, d] has 0 sorted combinations
[e, g, f] has 0 sorted combinations
[e, f, a] has 0 sorted combinations
[e, f, c] has 0 sorted combinations
[e, f, b] has 0 sorted combinations
[e, f, d] has 0 sorted combinations
[e, f, g] has 0 sorted combinations
[d, a, c] has 4 sorted combinations
[d, a, b] has 0 sorted combinations
[d, a, e] has 0 sorted combinations
[d, a, g] has 0 sorted combinations
[d, a, f] has 0 sorted combinations
[d, c, a] has 18 sorted combinations
[d, c, b] has 0 sorted combinations
[d, c, e] has 4 sorted combinations
[d, c, g] has 0 sorted combinations
[d, c, f] has 0 sorted combinations
[d, b, a] has 2 sorted combinations
[d, b, c] has 5 sorted combinations
[d, b, e] has 2 sorted combinations
[d, b, g] has 0 sorted combinations
[d, b, f] has 0 sorted combinations
[d, e, a] has 8 sorted combinations
[d, e, c] has 16 sorted combinations
[d, e, b] has 0 sorted combinations
[d, e, g] has 0 sorted combinations
[d, e, f] has 0 sorted combinations
[d, g, a] has 0 sorted combinations
[d, g, c] has 0 sorted combinations
[d, g, b] has 0 sorted combinations
[d, g, e] has 0 sorted combinations
[d, g, f] has 0 sorted combinations
[d, f, a] has 0 sorted combinations
[d, f, c] has 0 sorted combinations
[d, f, b] has 0 sorted combinations
[d, f, e] has 0 sorted combinations
[d, f, g] has 0 sorted combinations
[g, a, c] has 2 sorted combinations
[g, a, b] has 0 sorted combinations
[g, a, e] has 0 sorted combinations
[g, a, d] has 2 sorted combinations
[g, a, f] has 0 sorted combinations
[g, c, a] has 8 sorted combinations
[g, c, b] has 0 sorted combinations
[g, c, e] has 2 sorted combinations
[g, c, d] has 8 sorted combinations
[g, c, f] has 0 sorted combinations
[g, b, a] has 2 sorted combinations
[g, b, c] has 5 sorted combinations
[g, b, e] has 2 sorted combinations
[g, b, d] has 3 sorted combinations
[g, b, f] has 0 sorted combinations
[g, e, a] has 12 sorted combinations
[g, e, c] has 28 sorted combinations
[g, e, b] has 4 sorted combinations
[g, e, d] has 20 sorted combinations
[g, e, f] has 0 sorted combinations
[g, d, a] has 6 sorted combinations
[g, d, c] has 12 sorted combinations
[g, d, b] has 1 sorted combinations
[g, d, e] has 4 sorted combinations
[g, d, f] has 0 sorted combinations
[g, f, a] has 2 sorted combinations
[g, f, c] has 5 sorted combinations
[g, f, b] has 1 sorted combinations
[g, f, e] has 6 sorted combinations
[g, f, d] has 4 sorted combinations
[f, a, c] has 2 sorted combinations
[f, a, b] has 0 sorted combinations
[f, a, e] has 0 sorted combinations
[f, a, d] has 2 sorted combinations
[f, a, g] has 0 sorted combinations
[f, c, a] has 8 sorted combinations
[f, c, b] has 0 sorted combinations
[f, c, e] has 2 sorted combinations
[f, c, d] has 8 sorted combinations
[f, c, g] has 0 sorted combinations
[f, b, a] has 2 sorted combinations
[f, b, c] has 5 sorted combinations
[f, b, e] has 2 sorted combinations
[f, b, d] has 3 sorted combinations
[f, b, g] has 0 sorted combinations
[f, e, a] has 12 sorted combinations
[f, e, c] has 28 sorted combinations
[f, e, b] has 4 sorted combinations
[f, e, d] has 20 sorted combinations
[f, e, g] has 0 sorted combinations
[f, d, a] has 6 sorted combinations
[f, d, c] has 12 sorted combinations
[f, d, b] has 1 sorted combinations
[f, d, e] has 4 sorted combinations
[f, d, g] has 0 sorted combinations
[f, g, a] has 0 sorted combinations
[f, g, c] has 0 sorted combinations
[f, g, b] has 0 sorted combinations
[f, g, e] has 0 sorted combinations
[f, g, d] has 0 sorted combinations