Example: given k=3 and n=3, it is easy to generate a list of all 3-tuples whose entries are 0 or 1 or 2:
[(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 1, 0), (0, 1, 1), (0, 1, 2), (0, 2, 0), (0, 2, 1), (0, 2, 2), (1, 0, 0), (1, 0, 1), (1, 0, 2), (1, 1, 0), (1, 1, 1), (1, 1, 2), (1, 2, 0), (1, 2, 1), (1, 2, 2), (2, 0, 0), (2, 0, 1), (2, 0, 2), (2, 1, 0), (2, 1, 1), (2, 1, 2), (2, 2, 0), (2, 2, 1), (2, 2, 2)]
However, in my context, the tuples (0,1,2),(0,2,1),(1,2,0),(1,0,2),(2,0,1),(2,1,0) are all "the same" (same entries in different orderings), so I only want to keep one of them. Of those six, (0,1,2) is the one whose entries are "in order", so I'd only like to keep that one.
Likewise, the tuples (0,1,1)(1,0,1),(1,1,0) are all the same, so I'd like to only keep (0,1,1).
Goal: some function generate_my_tuples(n,k) that will produce a list of all length k tuples whose entries are in range(n), but only the "in order" version of each possible tuple, as described above.
For that example above, I want the output to be:
[(0,0,0),(0,0,1),(0,0,2),(0,1,1),(0,1,2),(0,2,2),(1,1,1),(1,1,2),(1,2,2),(2,2,2)]
As an extra goal, it would be nice if the function also created the list of removed tuples.
Comments: I can see how to do this when k=2, so there's only one "correct" and one "incorrect" order of each tuple. But, I don't see how to generalize this to arbitrary k (where the number of "incorrect" versions of a tuple even depends on the entries in the tuple). In my context, I really need this one function to cover all possible n and k.
You can use itertools.combinations_with_replacement
Return r length subsequences of elements from the input iterable allowing individual elements to be repeated more than once.
Combinations are emitted in lexicographic sort order. So, if the input iterable is sorted, the combination tuples will be produced in sorted order. from itertools import combinations_with_replacement
k = 3
n = 3
list(combinations_with_replacement(range(n), k))
Output:
[(0, 0, 0),
(0, 0, 1),
(0, 0, 2),
(0, 1, 1),
(0, 1, 2),
(0, 2, 2),
(1, 1, 1),
(1, 1, 2),
(1, 2, 2),
(2, 2, 2)]
If you also want the omitted tuples, you can generate all possible outputs with product, and remove the valid ones:
from itertools import combinations_with_replacement, product
k = 3
n = 3
valid = list(combinations_with_replacement(range(n), k))
omitted = set(product(range(n), repeat=k)) - set(valid)
print(omitted)
Output:
{(0, 2, 0), (1, 2, 1), (1, 1, 0), (1, 2, 0), (2, 1, 0), (0, 1, 0),
(1, 0, 0), (2, 2, 1), (2, 0, 2), (2, 1, 1), (1, 0, 1), (2, 2, 0),
(2, 0, 1), (2, 1, 2), (0, 2, 1), (2, 0, 0), (1, 0, 2)}
Edit:
as you asked in your comment, you can transform this output into the format you need (recursively nested tuples) like this:
from itertools import combinations_with_replacement, product
def recursively_nested(t):
if len(t) <= 2:
return t
else:
return recursively_nested(t[:-1]), t[-1]
k = 4
n = 3
valid = list(combinations_with_replacement(range(n), k))
out = [recursively_nested(t) for t in valid]
print(out)
# [(((0, 0), 0), 0), (((0, 0), 0), 1), (((0, 0), 0), 2), (((0, 0), 1), 1), (((0, 0), 1), 2), ...]