CODEWITHSUNDEEP
pythonalgorithmtuplespermutationcombinatorics
PRT
PRT

Reputation: 11

tuples of integers with fixed sums up to permutations

I'm stuck with the following problem which I need to speed up a piece of code I have written in the past. I am programming in python, but this question is more about the algorithm than about the python code.

I need an iterator for all the sets of different k tuples of integers with length a and sum d up to permutation of the elements of the tuples.

As an example, if k=2, a=2 and d=3, these are all the sets of different k tuples of integers with length a and sum d:

{(3,0), (0,3)}, {(3,0), (2,1)}, {(3,0), (1,2)}, {(1,2), (2,1)}, {(0,3), (2,1)}, {(0,3), (1,2)}

However I want to consider equal the sets {(3,0), (1,2)} and {(0,3), (2,1)}, since by exchanging the two numbers in the tuple I get the same result. In the end, all the sets of 2 different tuples of integers with length 2 and sum 3 are:

{(3, 0), (2, 1)}: 2,
{(3, 0), (1, 2)}: 2,
{(3, 0), (0, 3)}: 1,
{(2, 1), (1, 2)}: 1}

The difference with the first list is that now I have attached also a label to the sets, counting how many sets are there up to permutations. So, again {(3, 0), (2, 1)} is labelled with a 2 since it is counting also {(0, 3), (1, 2)}, while {(3, 0), (0, 3)} is labelled with a 1 since the permutations just give back the same set {(0, 3), (3, 0)}.

Just to give another example, here is the case with k=2, a=3, d=3 (so sets of pairs of tuples of length 3 with sum 3).

{(2, 1, 0), (3, 0, 0)}: 6, {(1, 2, 0), (3, 0, 0)}: 6, {(0, 3, 0), (3, 0, 0)}: 3, {(1, 1, 1), (3, 0, 0)}: 3, {(0, 2, 1), (3, 0, 0)}: 6, {(1, 2, 0), (2, 1, 0)}: 3, {(2, 0, 1), (2, 1, 0)}: 3, {(1, 1, 1), (2, 1, 0)}: 6, {(0, 2, 1), (2, 1, 0)}: 6, {(0, 1, 2), (2, 1, 0)}: 3

I need a python iterator which produces this result, given k (The number of tuples), a (the length of each tuple) and d (the sum of the elements in each tuple).

My question (the one I hope has positive answer) is: has this been already done somewhere?

The closest answer I was able to find is this library, which solves a more general problem, but with k=1 (it just list tuples, not sets of lenght k of tuples).

In the unlucky case this has never been done before, here are my attempts at producing a solution.

Note that I am not adding to the question an explicit code. This is because both of the approaches I tried are just wrong: the first works, but it is not an iterator. The second just don't work, but not because of the programming, but because of the algorithm what is wrong. For your convenience / curiosity, I add some sample code written in python3 (If I'll be able to produce a working code, I'll be happy to share it of course!)

My first - useless - approach, was just to construct the result, by iterating over all the sets, and then apply permutations to reduce the list. This is too slow and memory consuming. (A sample code, again this works but it is not an iterator)

My second - unfinished - approach was hopefully a bit clever: (A sample code, this does not work, see the explaination below)

  1. Digits (3,0,0) twice. The first tuple is just (3,0,0) (Since I am working up to permutation). For the second tuple, I have to remember that the first has two zeroes, so I can exchange the second and the third digits, and I create the set {(3,0,0), (0,3,0)}
  2. Digits (3,0,0) and (2,1,0). As before, the fist tuple is (3,0,0), and I can exchange the second and the third digits, so for the choice of the second tuple I have {(3,0,0), (2,1,0)}, {(3,0,0), (1,2,0)}, {(3,0,0), (0,2,1)}
  3. Digits (2,1,0) and (2,1,0). As before, the fist tuple is (2,1,0), and now, since all the digits are different, I can put all the permutation for the second tuple: {(2,1,0), (2,0,1)}, {(2,1,0), (1,2,0)}, {(2,1,0), (1,0,2)}, {(2,1,0), (0,2,1)}, {(2,1,0), (0,1,2)}. THIS CONTAINS A PROBLEM! It is wrong because there I am listing some tuples twice: {(2,1,0), (1,0,2)} is the same as {(2,1,0), (0,2,1)} by putting the third digit at the first place, the first digit at the second place, and the second digit at the third place.

Summing up:

First problem with this approach: I need to remove these last duplicates. However, the way I know is just to check them against each other, and this needs the complete list (so... not an iterator).

Second problem with this approach: I need also to attach a label to the pairs, describing how many of them are there up to permutation ({(2, 1, 0), (3, 0, 0)}: 6, means there are 6 possible pairs of tuples which can be obtained by permuting this one). However, the way I know to compute this is basically equivalent to the first approach, by listing all the permutations of this single pair, so, again - too slow :-( .

Upvotes: 0

Views: 103

Answers (1)

Raymond Hettinger
Raymond Hettinger

Reputation: 226516

There are two ways to eliminate the duplicates up to permutations.

  1. Sort the tuples to give them a canonical ordering:
>>> p = (0, 2, 1)
>>> q = (2, 1, 0)
>>> tuple(sorted(p)) == tuple(sorted(q))
True
  1. Run the algorithms with sets or frozensets and convert to tuples afterwards:
>>> p = (0, 2, 1)
>>> q = (2, 1, 0)
>>> frozenset(p) == frozenset(q)
True

Upvotes: 0

Related Questions