Permutations with repetition in python without two consecutive equal elements
I need a function that generates all permutations with repetitive iteration with the suggestion that two consecutive elements must be different; eg
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
Unfortunately itertools.permutation does not work for what I need (every element in the iterable is present one or more times in reverse)
I've tried a bunch of definitions; filter items from itertools.product (iterable, repeat = r) first, but 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 plot r for a loop, one inside the other (where r is the permutation class, represented as k in mathematics).
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 you don't need to remember me: exec is ugly, exec can be dangerous, exec is not easy to read ... I know. To understand the function better, I suggest you replace exec (s) with print (s).
I'll give an example of what line is inside 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 other than using exec, I need better features because crp2 is still too slow (even if faster than crp0); is there a way to recreate the code with r without using exec? Is there any other way to do what I need?
source to share
You can prepare the strings in two halves, then preprocess the other half to find compatible variations.
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]]]
In a test with iterable = [0,1,2] and r = 15, I found this method more than a hundred times faster than just using crp0.
source to share
You can try to return a generator instead of a list. For large values, r
your method will take a very long time to process product(iterable,repeat=r)
and will return a huge list.
In this case, you should get the first element very quickly:
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)
source to share
Instead of filtering the items, you can generate the list directly with only the correct items. This method uses recursion to create a Cartesian product:
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)
source to share
I agree with @EricDuminil's comment that you don't want "Permutations with repetition". You want many subsets of a product to be iterable with itself multiple times. I don't know which name is better: I'll just call them.
Here's an approach that builds each product line without creating all of the products, and then filters out the ones you want. My approach is to work primarily with iterative indices, not iterative ones - and not all indices, but ignoring the latter. So instead of directly interacting with, [2, 3, 5, 7]
I work with [0, 1, 2]
. Then I work with the products of these indexes. I can convert a product like [1, 2, 2]
where r=3
, comparing each index to the previous one. If the index is greater than or equal to the previous one, I increment the current index by one. This prevents the two indexes from being equal, and this also falls back to using all indexes. So, [1, 2, 2]
converted to [1, 2, 3]
where the final 2
was changed to a3
... Now I am using these indices to select matching items from the iteration, so the iterative [2, 3, 5, 7]
with r=3
gets the row [3, 5, 7]
. The first index is handled differently as it does not have a previous index. My code:
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
Using %timeit
Spyder / IPython in my config on crp3([0,1], 3)
shows 8.54 Β΅s per loop
, while yours crp2([0,1], 3)
shows 133 Β΅s per loop
. This shows a significant improvement in speed! My routine works best where it iterable
is short and r
large - your program finds lines len ** r
(where len
is the length of the iterable) and filters them, while mine finds len * (len-1) ** (r-1)
lines without filtering.
By the way, yours crp2()
does the filtering as shown in the lines if
in your exec
ed code . The only one if
in my code does not filter the string, it changes the item in the string. My code returns unexpected results if the elements in the iterable are not unique: if that's the problem, just change the iterable to a set to remove duplicates. Note that I have replaced your name l
with l
: I think it is l
too easy to confuse with 1
or I
and should be avoided. My code can be easily replaced with a generator: replace L.append(a)
with yield a
and remove the lines L = []
and return L
.
source to share