Python：从range(n)生成k-tuples，仅按顺序包含元组

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)都是"the same"（相同条目不同顺序），所以我只想保留其中一个。在这六个中，(0,1,2) 是条目为 "in order" 的那个，所以我只想保留那个。

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

目标： 一些函数 generate_my_tuples(n,k) 将生成所有长度为 k 的元组的列表，其条目在范围 (n) 内，但仅 每个可能的元组 的 "in order" 版本，如上所述。

对于上面的示例，我希望输出为：

[(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 时如何做到这一点，所以每个元组只有一个 "correct" 和一个 "incorrect" 顺序。但是，我看不出如何将其概括为任意 k（元组的 "incorrect" 版本的数量甚至取决于元组中的条目）。在我的上下文中，我真的需要这个函数来涵盖所有可能的 n 和 k。

Answer 1

我建议你使用 itertools.product 和字典（用于存储 删除的元组 ）：

from itertools import product

n, k = 3, 3
data = list(product(range(n), repeat=k))

result = {}
for t in data:
    key = tuple(sorted(t))
    result.setdefault(key, []).append(t)

print(list(result.keys()))

输出

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

注意字典的值是移除的元组，例如

for key, value in result.items():
    print(key, value)

输出

(0, 0, 0) [(0, 0, 0)]
(0, 0, 1) [(0, 0, 1), (0, 1, 0), (1, 0, 0)]
(0, 0, 2) [(0, 0, 2), (0, 2, 0), (2, 0, 0)]
(0, 1, 1) [(0, 1, 1), (1, 0, 1), (1, 1, 0)]
(0, 1, 2) [(0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0)]
(0, 2, 2) [(0, 2, 2), (2, 0, 2), (2, 2, 0)]
(1, 1, 1) [(1, 1, 1)]
(1, 1, 2) [(1, 1, 2), (1, 2, 1), (2, 1, 1)]
(1, 2, 2) [(1, 2, 2), (2, 1, 2), (2, 2, 1)]
(2, 2, 2) [(2, 2, 2)]

Answer 2

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

Answer 3

我会追求额外的目标，一个返回所选列表的函数，以及剩余的（作为一个集合，而不是一个列表）。

from itertools import combinations_with_replacement, product

k=3 
n=3

def extra_goal(k, n):
    selected = list(combinations_with_replacement(range(n), k))
    removed = set(product(range(n), repeat=k)) - set(selected)
    return selected, removed

print(extra_goal(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)], 
{(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)})

Python：从range(n)生成k-tuples，仅按顺序包含元组

Python: generate k-tuples from range(n), include only tuples in order

python

sorting

tuples

lexicographic