遍历列表，在一行中没有两个重复项

Question

我想以类似的方式遍历整数列表:

itertools.product(range(n), repeat=5)

如果n = 3，则得到:

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

然而，我只想要那些在一行中不具有相同数字的元组。所以(0,0,1,0,0)会被排除，其他的也会被排除。

你怎么能这么做?

Answer 1

自己生成没有连续重复的序列可能更有效，而不是用itertools.product生成所有序列并过滤它们。我将使用这样的递归生成器:

def gen(seq, n, prefix=()):
if n == 0:
yield prefix
return
for x in seq:
if not prefix or x != prefix[-1]:
yield from gen(seq, n-1, prefix+(x,))

示例输出:

>>> list(gen(range(3), 5))
[(0, 1, 0, 1, 0),
(0, 1, 0, 1, 2),
(0, 1, 0, 2, 0),
(0, 1, 0, 2, 1),
(0, 1, 2, 0, 1),
(0, 1, 2, 0, 2),
(0, 1, 2, 1, 0),
(0, 1, 2, 1, 2),
(0, 2, 0, 1, 0),
(0, 2, 0, 1, 2),
(0, 2, 0, 2, 0),
(0, 2, 0, 2, 1),
(0, 2, 1, 0, 1),
(0, 2, 1, 0, 2),
(0, 2, 1, 2, 0),
(0, 2, 1, 2, 1),
(1, 0, 1, 0, 1),
(1, 0, 1, 0, 2),
(1, 0, 1, 2, 0),
(1, 0, 1, 2, 1),
(1, 0, 2, 0, 1),
(1, 0, 2, 0, 2),
(1, 0, 2, 1, 0),
(1, 0, 2, 1, 2),
(1, 2, 0, 1, 0),
(1, 2, 0, 1, 2),
(1, 2, 0, 2, 0),
(1, 2, 0, 2, 1),
(1, 2, 1, 0, 1),
(1, 2, 1, 0, 2),
(1, 2, 1, 2, 0),
(1, 2, 1, 2, 1),
(2, 0, 1, 0, 1),
(2, 0, 1, 0, 2),
(2, 0, 1, 2, 0),
(2, 0, 1, 2, 1),
(2, 0, 2, 0, 1),
(2, 0, 2, 0, 2),
(2, 0, 2, 1, 0),
(2, 0, 2, 1, 2),
(2, 1, 0, 1, 0),
(2, 1, 0, 1, 2),
(2, 1, 0, 2, 0),
(2, 1, 0, 2, 1),
(2, 1, 2, 0, 1),
(2, 1, 2, 0, 2),
(2, 1, 2, 1, 0),
(2, 1, 2, 1, 2)]

Answer 2

下面是另一种递归生成器方法，它基于从调用递归中排除值，而不是传递整个结果:

def comb(A,n,x=None):
return ([v]+r for v in A if v!=x for r in comb(A,n-1,v)) if n else [[]]

输出:

for p in comb(range(3),5):print(p)
[0, 1, 0, 1, 0]
[0, 1, 0, 1, 2]
[0, 1, 0, 2, 0]
[0, 1, 0, 2, 1]
[0, 1, 2, 0, 1]
[0, 1, 2, 0, 2]
[0, 1, 2, 1, 0]
[0, 1, 2, 1, 2]
[0, 2, 0, 1, 0]
[0, 2, 0, 1, 2]
[0, 2, 0, 2, 0]
[0, 2, 0, 2, 1]
[0, 2, 1, 0, 1]
[0, 2, 1, 0, 2]
[0, 2, 1, 2, 0]
[0, 2, 1, 2, 1]
[1, 0, 1, 0, 1]
[1, 0, 1, 0, 2]
[1, 0, 1, 2, 0]
[1, 0, 1, 2, 1]
[1, 0, 2, 0, 1]
[1, 0, 2, 0, 2]
[1, 0, 2, 1, 0]
[1, 0, 2, 1, 2]
[1, 2, 0, 1, 0]
[1, 2, 0, 1, 2]
[1, 2, 0, 2, 0]
[1, 2, 0, 2, 1]
[1, 2, 1, 0, 1]
[1, 2, 1, 0, 2]
[1, 2, 1, 2, 0]
[1, 2, 1, 2, 1]
[2, 0, 1, 0, 1]
[2, 0, 1, 0, 2]
[2, 0, 1, 2, 0]
[2, 0, 1, 2, 1]
[2, 0, 2, 0, 1]
[2, 0, 2, 0, 2]
[2, 0, 2, 1, 0]
[2, 0, 2, 1, 2]
[2, 1, 0, 1, 0]
[2, 1, 0, 1, 2]
[2, 1, 0, 2, 0]
[2, 1, 0, 2, 1]
[2, 1, 2, 0, 1]
[2, 1, 2, 0, 2]
[2, 1, 2, 1, 0]
[2, 1, 2, 1, 2]

[EDIT]返回列表的列表的替代版本

def comb(A,n,x=None):
return [[v]+r for v in A if v!=x for r in comb(A,n-1,v)] if n else [[]]

Answer 3

您可以使用带有保护符的综合列表:

n = 3
repeat = 5
[l for l in itertools.product(range(n), repeat=repeat) if not any(l[n-1] == l[n] for n in range(1, repeat))]

这将过滤掉任何至少有一个值与前一个相同的行。

Answer 4

如果您想使用更高级的函数，您可以检查groupby中的组数是否与repeat相同。

n = 3
r = 5
out_gen = filter(
lambda x: len(tuple(itertools.groupby(x)))==r, 
itertools.product(range(n), repeat=r)
)

Answer 5

尝试:

output = [
lst for lst in itertools.product(range(3), repeat=3) 
if not any(i==j for i, j in zip(lst[:-1],lst[1:]))
]