給定兩個整數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 中實作它？提前感謝您的建議。
uj5u.com熱心網友回復：
這是python中的一個天真的解決方案：
{1, 2, ...,n}從與自身時間的笛卡爾積生成所有組合r；- 每個等效等級只保留一個有代表性的組合；洗掉與此代表性組合等效的所有其他組合。
這意味著我們必須有一些方法來比較組合，例如，只保留每個等價類的最小組合。
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? .
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/471204.html
上一篇：一個序列的總和
下一篇：分治演算法的sumlist