Geek asks and answers

Sorted Tuples from Cartesian Product Lists

I have a list dictionary, for example:

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

I want to use the keys 3 at a time (I use itertools.permutations), and then count all the ways in which I can take one item from each list and sort the result.

For the three keys shown above, I would get 2:

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

Clearly, I can do the Cartesian product of the dictionary values, and then count the sorted ones:

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)
+3
3

- , . , , , .

, :

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, M1, M2 M3. M3[key][number] , number ( 1). M2[key][number] , number ( M3), M1[key][number] number . M1 M2. M1. M1, M2 M3.

, M1[key][number], , downkeys - , key. downkey M2[downkey] M2[downkey][num2], num2 , number. downkey M1[key][number]. , , M1 M2.

, - , , , , . Cartesian - 3 n, , . . , .

+1

, , , , 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
0

Recursive solution:

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

Input:

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]]

Conclusion:

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)])
0
source

More articles:


All Articles