Most efficient way to find the number of possible unique fixed length permutations?
<p>I've got this dictionary:</p>

<pre><code>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)],
    }
</code></pre>

<p>I need to find the max number of 3 long combinations of the first values of each of these tuples, where only the values of each key can proceed said key.</p>

<p>My current code for finding all unique (3 long) combinations is this:</p>

<pre><code>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)
</code></pre>

<p><em>This returns</em> <code>10</code> and <code>ans_set</code> ends up being:</p>

<pre><code>{
 (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)
}
</code></pre>

<p><em>But I don't actually care about what the sets are, just the number of them</em></p>

<p>This method is not particularly efficient as it actually generates every possible combination and puts it in a set.</p>

<p>I don't need to know each unique combination, I just need to know how many there are.</p>

<p>I have a feeling this can be done, maybe using the lengths of the value lists? but I am having trouble wrapping my head around it.</p>

<p>Clarifying questions about what I need are welcome as I realize I might not have explained it in the most clear fashion.</p>

<h1>Final Edit</h1>

<p>I've found the best way to find the number of triples by reevaluating what i needed it to do. This method doesn't actually find the triples, it just counts them.</p>

<pre><code>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
</code></pre>

<p>And here's a version of the function that explains the thought process as it goes (not good for huge lists though because of spam prints):</p>

<pre><code>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)
</code></pre>

<p>If i get you right:</p>

<pre><code>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))
</code></pre>

<p>Output:</p>

<pre><code>{(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)}
</code></pre>

<p>And <code>len()</code> is <code>10</code></p>

<p>So basically what you're would do, make all combinations with <a href="https://docs.python.org/3/library/itertools.html#itertools.combinations" rel="nofollow"><code>itertools.combinations</code></a>, from first elements of dict keys with a length 3 and then get <code>set</code> to eliminate repeating elements.</p>

<p><strong>UPDATE</strong></p>

<p>Since you updated the question with desired output data</p>

<p>You can do the following</p>

<pre><code>from itertools import combinations_with_replacement
list(combinations_with_replacement(set([k[0] for k in num_dict.keys()]), 3))
</code></pre>

<p>Output:</p>

<pre><code>[(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)]
</code></pre>

<p><strong>UPD2</strong></p>

<p>So about time consumption i've ran it</p>

<pre><code>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)
</code></pre>

<p>And the the results are:</p>

<pre><code>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
</code></pre>

<p>So solution that i've presented here is 2x times faster.</p>

python algorithm