Permutations with repetition without two consecutive equal elements

user_8225026 0
Viewed 1308

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

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

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

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

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

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

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?

combinations permutation algorithm python
6 Answers

Elaborating on @peter-de-rivaz's idea (divide and conquer). When you divide the sequence to create into two subsequences, those subsequences are the same or very close. If r = 2*k is even, store the result of crp(k) in a list and merge it with itself. If r=2*k+1, store the result of crp(k) in a list and merge it with itself and with 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 is an adaptation from @eric-duminil's answer using the famous for...else loop of Python:

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

A small benchmark:

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
user_69144410
Related