Python:从范围(n)生成k元组，仅按顺序包含元组

Question

示例:给定 k=3 和 n=3，很容易生成条目为 0 或 1 或 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)]

但是，在我的上下文中，元组 (0,1,2),(0,2,1),(1,2,0),(1,0,2),(2,0,1) ,(2,1,0) 都是“相同的”(不同顺序的相同条目)，所以我只想保留其中一个。在这六个中，(0,1,2) 的条目是“有序的”，所以我只想保留那个。

同样，元组 (0,1,1)(1,0,1),(1,1,0) 都是相同的，所以我只想保留 (0,1,1)。

目标:某些函数 generate_my_tuples(n,k) 将生成所有长度为 k 的元组列表，其条目在范围 (n) 内，但是 如上所述，只有每个可能元组的“有序”版本。

对于上面的例子，我希望输出是:

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

作为一个额外的目标，如果该函数还创建了已删除元组的列表，那就太好了。

评论:当 k=2 时，我可以看到如何做到这一点，因此每个元组只有一个“正确”和一个“错误”顺序。但是，我不知道如何将其推广到任意 k(元组的“不正确”版本的数量甚至取决于元组中的条目)。在我的上下文中，我真的需要这个函数来涵盖所有可能的 n 和 k。

Answer 1

您可以使用 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))

输出:

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

如果您还想要省略的元组，您可以使用 product 生成所有可能的输出，并删除有效的:

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)

输出:

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

---

编辑:

正如您在评论中所问，您可以将此输出转换为您需要的格式(递归嵌套元组)，如下所示:

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), ...]