from collections import Counter
from math import factorial
from functools import reduce
from operator import mul
from typing import Sequence, Generator, TypeVar, Protocol, Any
[docs]
class SupportsRichComparison(Protocol):
def __lt__(self, other: Any) -> bool: ...
def __le__(self, other: Any) -> bool: ...
def __gt__(self, other: Any) -> bool: ...
def __ge__(self, other: Any) -> bool: ...
T = TypeVar('T', bound=SupportsRichComparison)
[docs]
def flatten_list(this_list: list[list]) -> list:
return [item for sublist in this_list for item in sublist]
[docs]
def number_of_unique_permutations(seq: list) -> int:
"""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: Sequence[T]) -> Generator[tuple[T, ...], None, None]:
"""
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 tuple(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]