没有两个连续相等元素的具有重复的置换 [英] Permutations with repetition without two consecutive equal elements

问题描述

我需要一个函数，该函数通过重复两个子元素必须不同的子句来生成所有置换.例如

I need a function that generates all the permutation with repetition of an iterable with the clause that two consecutive elements must be different; for example

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不能满足我的需要(迭代中的每个元素在返回中只出现一次或不出现)

Unfortunatly itertools.permutation doesn't work for what I need (each element in the iterable is present once or no times in the return)

我尝试了很多定义；首先，从itertools.product(iterable，repeat = r)输入中过滤元素，但是对于我所需要的来说太慢了.

I've tried a bunch of definitions; first, filterting elements from itertools.product(iterable,repeat=r) input, but is too slow for what I need.

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).

Second, I tried to build r for cycle, one inside the other (where r is the class of the permutation, represented as k in math).

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.

I know, there's no need you remember me: exec is ugly, exec can be dangerous, exec isn't easy-readable... I know. To understand better the function I suggest you to replace exec(s) with print(s).

我举一个例子说明crp([0,1]，2)的exec内是什么字符串:

I give you an example of what string is inside the exec for crp([0,1],2):

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重新创建代码?还有其他方法可以满足我的需求吗?

But, apart from using exec, I need a better functions because crp2 is still too slow (even if faster than crp0); there's any way to recreate the code with r for without using exec? There's any other way to do what I need?

推荐答案

您可以将序列分成两半准备，然后预处理第二半以找到兼容的选择.

You could prepare the sequences in two halves, then preprocess the second halves to find the compatible choices.

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快一百倍.

In a test with iterable=[0,1,2] and r=15, I found this method to be over a hundred times faster than just using crp0.

这篇关于没有两个连续相等元素的具有重复的置换的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！