笛卡尔积，但删除重复项直至循环排列

Question

给定两个整数 n 和 r，我想根据以下规则生成所有可能的组合：

有 n 个不同的号码可供选择，1, 2, ..., n；
每个组合应该有r个元素；
一个组合可以包含多个元素，例如(1,2,2)有效；
订单问题，即 (1,2,3) 和 (1,3,2) 被认为是不同的；
但是，如果一个是另一个的循环排列，则两个组合被认为是等价的；例如，(1,2,3) 和 (2,3,1) 被认为是重复的。

示例：

n=3, r=2
11 distinct combinations
(1,1,1), (1,1,2), (1,1,3), (1,2,2), (1,2,3), (1,3,2), (1,3,3), (2,2,2), (2,2,3), (2,3,3) and (3,3,3)

n=2, r=4
6 distinct combinations
(1,1,1,1), (1,1,1,2), (1,1,2,2), (1,2,1,2), (1,2,2,2), (2,2,2,2)

它的算法是什么？以及如何在 C++ 中实现它？预先感谢您的建议。

Answer 1

python 中有一个天真的解决方案：

根据 {1, 2, ...,n} 的笛卡尔积与其自身 r 次生成所有组合；
每个等价物只保留一个代表组合class；删除与此代表组合等效的所有其他组合。

这意味着我们必须有一些方法来比较组合，例如，只保留每个等价的最小组合 class。

from itertools import product

def is_representative(comb):
    return all(comb[i:] + comb[:i] >= comb
               for i in range(1, len(comb)))

def cartesian_product_up_to_cyclic_permutations(n, r):
    return filter(is_representative,
                  product(range(n), repeat=r))

print(list(cartesian_product_up_to_cyclic_permutations(3, 3)))
# [(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 1, 1), (0, 1, 2), (0, 2, 1), (0, 2, 2), (1, 1, 1), (1, 1, 2), (1, 2, 2), (2, 2, 2)]

print(list(cartesian_product_up_to_cyclic_permutations(2, 4)))
# [(0, 0, 0, 0), (0, 0, 0, 1), (0, 0, 1, 1), (0, 1, 0, 1), (0, 1, 1, 1), (1, 1, 1, 1)]

你提到你想用 C++ 实现算法。 python 代码中的 product 函数的行为就像一个大的 for 循环，它生成笛卡尔积中的所有组合。请参阅此相关问题以在 C++ 中实现笛卡尔积：Is it possible to execute n number of nested "loops(any)" where n is given?。

笛卡尔积，但删除重复项直至循环排列

Cartesian product but remove duplicates up to cyclic permutations

algorithm

combinations

cartesian-product

circular-permutations