（不确定这是否是正确的 SX 站点？我不需要实际代码，所以……）
我正在寻找一种算法，它可以为一组列表生成所有笛卡尔积，但会以一种智能的方式跳过只是先前发布的元组的旋转的元组。
这里，是一个旋转当且当.
例如，对于输出应该是 ，即没有因为它是一个轮换.
生成所有笛卡尔积的算法，无需旋转
计算科学
算法
组合学
2021-12-05 22:35:49
1个回答
这是蛮力的方式（在 Python 中），也许对某人来说很有趣：
def rotate_product(*xs):
# map integer to tuple
def from_int(i):
tup = []
for x in xs:
tup.append(x[i % len(x)])
i /= len(x)
return tuple(tup)
# map tuple to integer, or -1 if impossible.
def to_int(tup):
i = 0
mul = 1
for t, x in zip(tup, xs):
if t not in x:
return -1
i += mul * x.index(t)
mul *= len(x)
return i
# map integer to tuple, if no rotation of smaller tuple
def make_tuple(i):
tup = from_int(i)
for k in range(1, len(xs)):
if 0 <= to_int(tup[k:] + tup[:k]) < i:
return None
return tup
# total number of possible tuples
n = 1
for x in xs:
n *= len(x)
# brute force through all possibilities
for i in range(n):
t = make_tuple(i)
if t:
yield t