#!/usr/bin/env python
# -*- coding: utf-8 -*-
'''
Compare two methods of printing all distinct permutations.
(of a list which may contain duplicates)
For instance, the distinct permutations of [1, 1, 2] are [1, 1, 2], [1, 2, 1] and [2, 1, 1].
'''
import itertools
def next_permutationS(l):
'''Changes a list to its next permutation, in place.
Returns true unless wrapped around so result is lexicographically smaller. '''
n = len(l)
#Step 1: Find tail
last = n-1 #tail is from `last` to end
while last>0:
if l[last-1] < l[last]: break
last -= 1
#Step 2: Increase the number just before tail
if last>0:
small = l[last-1]
big = n-1
while l[big] <= small: big -= 1
l[last-1], l[big] = l[big], small
#Step 3: Reverse tail
i = last
j = n-1
while i < j:
l[i], l[j] = l[j], l[i]
i += 1
j -= 1
return last>0
def next_permutationB(seq, pred=cmp):
"""
This function is taken from this blog post:
http://blog.bjrn.se/2008/04/lexicographic-permutations-using.html
Like C++ std::next_permutation() but implemented as
generator. Yields copies of seq."""
def reverse(seq, start, end):
# seq = seq[:start] + reversed(seq[start:end]) + \
# seq[end:]
end -= 1
if end <= start:
return
while True:
seq[start], seq[end] = seq[end], seq[start]
if start == end or start+1 == end:
return
start += 1
end -= 1
if not seq:
raise StopIteration
try:
seq[0]
except TypeError:
raise TypeError("seq must allow random access.")
first = 0
last = len(seq)
seq = seq[:]
# Yield input sequence as the STL version is often
# used inside do {} while.
yield seq
if last == 1:
raise StopIteration
while True:
next = last - 1
while True:
# Step 1.
next1 = next
next -= 1
if pred(seq[next], seq[next1]) < 0:
# Step 2.
mid = last - 1
while not (pred(seq[next], seq[mid]) < 0):
mid -= 1
seq[next], seq[mid] = seq[mid], seq[next]
# Step 3.
reverse(seq, next1, last)
# Change to yield references to get rid of
# (at worst) |seq|! copy operations.
yield seq[:]
break
if next == first:
raise StopIteration
raise StopIteration
def unique(iterable):
seen = set()
for x in iterable:
if x in seen: continue
seen.add(x)
yield x
def m_itertoolsp(s):
for p in unique(itertools.permutations(s)):
pass
def m_nextperm_s(s):
pass
while next_permutationS(s):
pass
def m_nextperm_b(s):
for p in next_permutationB(s):
pass
'''
In the Python shell, try
l = [1, 2, 2, 2, 2, 3, 3, 3, 3, 3]
%timeit m_itertoolsp(l)
%timeit m_nextperm_b(l)
%timeit m_nextperm_s(l)
etc., and repeat for different lists l.
Some results ("us" means microseconds):
l m_itertoolsp m_nextperm_b m_nextperm_s
[1, 1, 2] 5.98 us 12.3 us 7.54 us
[1, 2, 3, 4, 5, 6] 0.63 ms 2.69 ms 1.77 ms
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 6.93 s 13.68 s 8.75 s
[1, 2, 3, 4, 6, 6, 6] 3.12 ms 3.34 ms 2.19 ms
[1, 2, 2, 2, 2, 3, 3, 3, 3, 3] 2400 ms 5.87 ms 3.63 ms
[1, 1, 1, 1, 1, 1, 1, 1, 1, 2] 2320000 us 89.9 us 51.5 us
[1, 1, 2, 2, 3, 3, 4, 4, 4, 4, 4, 4] 429000 ms 361 ms 228 ms
'''