Determine list of all possible products from a list of integers in Python
<p>In Python 2.7 I need a method that returns all possible products of a <code>list or tuple of int</code>. Ie. if input is <code>(2, 2, 3, 4)</code>, then I'd want a output like</p>

<ul>
<li><code>(3, 4, 4)</code>, 2 * 2 = 4</li>
<li><code>(2, 4, 6)</code>, 2 * 3 = 6</li>
<li><code>(2, 3, 8)</code>, 2 * 4 = 8</li>
<li><code>(3, 4, 4)</code>, 2 * 2 = 4</li>
<li><code>(2, 2, 12)</code>, 3 * 4 = 12</li>
<li><code>(2, 24)</code>, 2 * 3 * 4 = 24</li>
<li><code>(3, 16)</code>, 2 * 2 * 4 = 16</li>
<li><code>(4, 12)</code>, 2 * 2 * 3 = 12</li>
<li><code>(48)</code>, 2 * 2 * 3 * 4 = 48</li>
</ul>

<p>wrapped up in a <code>list or tuple</code>. I figure that a nice implementation is probably possible using <a href="https://docs.python.org/2/library/itertools.html#itertools.combinations" rel="nofollow">combinations</a> from <code>itertools</code>, but I'd appreciate any help. Note that I am only interested in distinct lists, where order of <code>int</code> plays no role.</p>

<p>EDIT</p>

<p>Some futher explanation for some clarification. Take the first output list. Input is <code>(2, 2, 3, 4)</code> (always). Then I take 2 and 2 <em>out</em> of the list and multiply them, so now I am left with a list <code>(3, 4, 4)</code>. 3 and 4 from the input and the last 4 from the product. </p>

<p>I haven't tried anything yet since I just can't spin my head around that kind of loop. But I can't stop thinking about the problem, so I'll add some code if I do get a suggestion.</p>

<p>You can break this down into three steps:</p>

<ul>
<li>get all the permutations of the list of numbers</li>
<li>for each of those permutations, create all the possible partitions</li>
<li>for each sublist in the partitions, calculate the product</li>
</ul>

<p>For the permutations, you can use <code>itertools.permutations</code>, but as far as I know, there is no builtin function for partitions, but that's not too difficult to write (or to find):</p>

<pre><code>def partitions(lst):
    if lst:
        for i in range(1, len(lst) + 1):
            for p in partitions(lst[i:]):
                yield [lst[:i]] + p
    else:
        yield []
</code></pre>

<p>For a list like <code>(1,2,3,4)</code>, this will generate <code>[(1),(2),(3),(4)]</code>, <code>[(1),(2),(3,4)]</code>, <code>[(1),(2,3),(4)]</code>, <code>[(1),(2,3,4)]</code>, and so on, but not, e.g. <code>[(1,3),(2),(4)]</code>; that's why we also need the permutations. However, for all the permutations, this will create many partitions that are effectively duplicates, like <code>[(1,2),(3,4)]</code> and <code>[(4,3),(1,2)]</code> (182 for your <code>data</code>), but unless your lists are particularly long, this should not be too much of a problem.</p>

<p>We can combine the second and third step; this way we can weed out all the duplicates as soon as they arise:</p>

<pre><code>data = (2, 2, 3, 4)
res = {tuple(sorted(reduce(operator.mul, lst) for lst in partition))
       for permutation in itertools.permutations(data)
       for partition in partitions(permutation)}
</code></pre>

<p>Afterwards, <code>res</code> is <code>{(6, 8), (2, 4, 6), (2, 2, 3, 4), (2, 2, 12), (48,), (3, 4, 4), (4, 12), (3, 16), (2, 24), (2, 3, 8)}</code></p>

<hr>

<p>Alternatively, you can combine it all in one, slightly more complex algorithm. This still generates <em>some</em> duplicates, due to the two <code>2</code> in your data set, that can again be removed by sorting and collecting in a set. The result is the same as above.</p>

<pre><code>def all_partitions(lst):
    if lst:
        x = lst[0]
        for partition in all_partitions(lst[1:]):
            # x can either be a partition itself...
            yield [x] + partition
            # ... or part of any of the other partitions
            for i, _ in enumerate(partition):
                partition[i] *= x
                yield partition
                partition[i] //= x
    else:
        yield []

res = set(tuple(sorted(x)) for x in all_partitions(list(data)))
</code></pre>

python algorithm combinations combinatorics