我需要一个函数，该函数通过两个连续元素必须不同的子句的重复生成所有置换。例如
f([0,1],3).sort()==[(0,1,0),(1,0,1)]
#or
f([0,1],3).sort()==[[0,1,0],[1,0,1]]
#I don't need the elements in the list to be sorted.
#the elements of the return can be tuples or lists, it doesn't change anything
不幸的是，itertools.permutation无法满足我的需要（可迭代对象中的每个元素在返回中都出现一次或不出现）
我已经尝试了很多定义；首先，从itertools.product（iterable，repeat = r）输入中过滤元素，但是对于我所需要的来说太慢了。
from itertools import product
def crp0(iterable,r):
l=[]
for f in product(iterable,repeat=r):
#print(f)
b=True
last=None #supposing no element of the iterable is None, which is fine for me
for element in f:
if element==last:
b=False
break
last=element
if b: l.append(f)
return l
[其次，我尝试为循环建立r，一个在另一个内部（其中r是置换的类，在数学上表示为k）。
def crp2(iterable,r):
a=list(range(0,r))
s="\n"
tab=" " #4 spaces
l=[]
for i in a:
s+=(2*i*tab+"for a["+str(i)+"] in iterable:\n"+
(2*i+1)*tab+"if "+str(i)+"==0 or a["+str(i)+"]!=a["+str(i-1)+"]:\n")
s+=(2*i+2)*tab+"l.append(a.copy())"
exec(s)
return l
我知道，您无需记住我：exec丑陋，exec可能很危险，exec难以理解...我知道。为了更好地理解该功能，我建议您将exec替换为print。
我给你一个示例，其中crp（[0,1]，2）的exec包含什么字符串：
for a[0] in iterable:
if 0==0 or a[0]!=a[-1]:
for a[1] in iterable:
if 1==0 or a[1]!=a[0]:
l.append(a.copy())
但是，除了使用exec之外，我还需要更好的功能，因为crp2仍然太慢（即使比crp0还要快）；有没有不用exec就可以用r重新创建代码的方法？还有其他方法可以满足我的需求吗？
您可以将序列分成两半准备，然后预处理第二半以找到兼容的选择。
def crp2(I,r):
r0=r//2
r1=r-r0
A=crp0(I,r0) # Prepare first half sequences
B=crp0(I,r1) # Prepare second half sequences
D = {} # Dictionary showing compatible second half sequences for each token
for i in I:
D[i] = [b for b in B if b[0]!=i]
return [a+b for a in A for b in D[a[-1]]]
在具有iterable = [0,1,2]和r = 15的测试中，我发现此方法比仅使用crp0快一百倍。
您可以尝试返回一个生成器而不是列表。如果r的值较大，则您的方法将需要很长的时间来处理product(iterable,repeat=r)，并且会返回庞大的列表。
使用此变体，您应该非常快地获得第一个元素：
from itertools import product
def crp0(iterable, r):
for f in product(iterable, repeat=r):
last = f[0]
b = True
for element in f[1:]:
if element == last:
b = False
break
last = element
if b:
yield f
for no_repetition in crp0([0, 1, 2], 12):
print(no_repetition)
# (0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1)
# (1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0)
除了过滤元素外，您还可以仅使用正确的元素直接生成列表。此方法使用递归来创建笛卡尔积：
def product_no_repetition(iterable, r, last_element=None):
if r == 0:
return [[]]
else:
return [p + [x] for x in iterable
for p in product_no_repetition(iterable, r - 1, x)
if x != last_element]
for no_repetition in product_no_repetition([0, 1], 12):
print(no_repetition)
我同意@EricDuminil的评论，即您不希望“重复排列”。您需要多次迭代的乘积本身。我不知道什么名字最好：我只会称呼它们为产品。
这里是一种构建每个产品系列而无需构建所有产品，然后过滤出所需产品的方法。我的方法主要是使用可迭代的indices而不是可迭代本身-而不是所有索引，而忽略最后一个。因此，我不是直接使用[2, 3, 5, 7]，而是使用[0, 1, 2]。然后，我使用这些指数的产品。通过将每个索引与上一个索引进行比较，我可以将诸如[1, 2, 2]的产品转换为r=3。如果索引大于或等于前一个索引，则将当前索引加1。这样可以防止两个索引相等，并且还可以重新使用所有索引。因此，[1, 2, 2]转换为[1, 2, 3]，其中最终的2更改为3。现在，我使用这些索引从可迭代的对象中选择适当的项目，因此可迭代的[2, 3, 5, 7]与r=3会获得行[3, 5, 7]。第一个索引的处理方式有所不同，因为它没有先前的索引。我的代码是：
from itertools import product
def crp3(iterable, r):
L = []
for k in range(len(iterable)):
for f in product(range(len(iterable)-1), repeat=r-1):
ndx = k
a = [iterable[ndx]]
for j in range(r-1):
ndx = f[j] if f[j] < ndx else f[j] + 1
a.append(iterable[ndx])
L.append(a)
return L
在%timeit上的Spyder / IPython配置中使用crp3([0,1], 3)会显示8.54 µs per loop，而crp2([0,1], 3)会显示133 µs per loop。这表明速度有了很大的提高！我的例程在iterable短而r大的情况下效果最佳-您的例程找到len ** r行（其中len是可迭代的长度）并过滤它们，而我的例程发现len * (len-1) ** (r-1)行而不进行过滤。
顺便说一下，您的crp2()确实进行了过滤，如代码中if的exec行所示。我的代码中唯一的if不过滤行，而是修改行中的项目。如果iterable中的项目不是唯一的，我的代码确实会返回令人惊讶的结果：如果这是一个问题，只需将iterable更改为set即可删除重复项。请注意，我用l替换了您的L名称：我认为l太容易与1或I混淆，应该避免使用。我的代码很容易更改为生成器：将L.append(a)替换为yield a，然后删除行L = []和return L。
怎么样：
from itertools import product
result = [ x for x in product(iterable,repeat=r) if all(x[i-1] != x[i] for i in range(1,len(x))) ]
详细阐述@ peter-de-rivaz的想法（分而治之。当您将序列划分为两个子序列时，这些子序列相同或非常接近。如果r = 2*k是偶数，则将crp(k)的结果存储在列表中并将其与自身合并。如果为r=2*k+1，则将crp(k)的结果存储在列表中，并将其与自身以及与L合并。
def large(L, r):
if r <= 4: # do not end the divide: too slow
return small(L, r)
n = r//2
M = large(L, r//2)
if r%2 == 0:
return [x + y for x in M for y in M if x[-1] != y[0]]
else:
return [x + y + (e,) for x in M for y in M for e in L if x[-1] != y[0] and y[-1] != e]
[small是使用Python的著名for...else循环：
from itertools import product
def small(iterable, r):
for seq in product(iterable, repeat=r):
prev, *tail = seq
for e in tail:
if e == prev:
break
prev = e
else:
yield seq
一个小基准：
print(timeit.timeit(lambda: crp2( [0, 1, 2], 10), number=1000))
#0.16290732200013736
print(timeit.timeit(lambda: crp2( [0, 1, 2, 3], 15), number=10))
#24.798989593000442
print(timeit.timeit(lambda: large( [0, 1, 2], 10), number=1000))
#0.0071403849997295765
print(timeit.timeit(lambda: large( [0, 1, 2, 3], 15), number=10))
#0.03471425700081454