from collections import Counter
from math import factorial
from functools import reduce
from operator import mul
[docs]def flatten_list( this_list ):
return [ item for sublist in this_list for item in sublist ]
[docs]def number_of_unique_permutations( seq ):
"""Calculate the number of unique permutations of a sequence seq.
Args:
seq (list): list of items.
Returns:
int: The number of unique permutations of seq
"""
times_included = list( Counter( seq ).values() )
factorials = list( map( factorial, times_included ) )
return int( factorial( len( seq ) ) / reduce( mul, factorials ) )
[docs]def unique_permutations( seq ):
"""
Yield only unique permutations of seq in an efficient way.
A python implementation of Knuth's "Algorithm L", also known from the
std::next_permutation function of C++, and as the permutation algorithm
of Narayana Pandita.
see http://stackoverflow.com/questions/12836385/how-can-i-interleave-or-create-unique-permutations-of-two-stings-without-recurs/12837695
"""
# Precalculate the indices we'll be iterating over for speed
i_indices = range(len(seq) - 1, -1, -1)
k_indices = i_indices[1:]
# The algorithm specifies to start with a sorted version
seq = sorted(seq)
while True:
#yield list( seq )
yield list( seq )
# Working backwards from the last-but-one index, k
# we find the index of the first decrease in value. 0 0 1 0 1 1 1 0
for k in k_indices:
if seq[k] < seq[k + 1]:
break
else:
# Introducing the slightly unknown python for-else syntax:
# else is executed only if the break statement was never reached.
# If this is the case, seq is weakly decreasing, and we're done.
return
# Get item from sequence only once, for speed
k_val = seq[k]
# Working backwards starting with the last item, k i
# find the first one greater than the one at k 0 0 1 0 1 1 1 0
for i in i_indices:
if k_val < seq[i]:
break
# Swap them in the most efficient way
(seq[k], seq[i]) = (seq[i], seq[k]) # k i
# 0 0 1 1 1 1 0 0
# Reverse the part after but not k
# including k, also efficiently. 0 0 1 1 0 0 1 1
seq[k + 1:] = seq[-1:k:-1]