67 lines
1.7 KiB
Python
67 lines
1.7 KiB
Python
"""
|
|
Brute force solution for the Perfect Shuffle problem.
|
|
See http://oeis.org/A002326 for possible improvements
|
|
"""
|
|
from functools import partial
|
|
from itertools import chain
|
|
from operator import eq
|
|
from typing import (Callable,
|
|
Iterable,
|
|
Iterator,
|
|
List,
|
|
TypeVar)
|
|
|
|
T = TypeVar('T')
|
|
|
|
|
|
def main():
|
|
print("Deck length | Shuffles ")
|
|
for length in (8, 24, 52, 100, 1020, 1024, 10000):
|
|
deck = list(range(length))
|
|
shuffles_needed = spin_number(deck, shuffle)
|
|
print(f"{length:<11} | {shuffles_needed}")
|
|
|
|
|
|
def shuffle(deck: List[T]) -> List[T]:
|
|
"""[1, 2, 3, 4] -> [1, 3, 2, 4]"""
|
|
half = len(deck) // 2
|
|
return list(chain.from_iterable(zip(deck[:half], deck[half:])))
|
|
|
|
|
|
def spin_number(source: T,
|
|
function: Callable[[T], T]) -> int:
|
|
"""
|
|
Applies given function to the source
|
|
until the result becomes equal to it,
|
|
returns the number of calls
|
|
"""
|
|
is_equal_source = partial(eq, source)
|
|
spins = repeat_call(function, source)
|
|
return next_index(is_equal_source,
|
|
spins,
|
|
start=1)
|
|
|
|
|
|
def repeat_call(function: Callable[[T], T],
|
|
value: T) -> Iterator[T]:
|
|
"""(f, x) -> f(x), f(f(x)), f(f(f(x))), ..."""
|
|
while True:
|
|
value = function(value)
|
|
yield value
|
|
|
|
|
|
def next_index(predicate: Callable[[T], bool],
|
|
iterable: Iterable[T],
|
|
start: int = 0) -> int:
|
|
"""
|
|
Returns index of the first element of the iterable
|
|
satisfying given condition
|
|
"""
|
|
for index, item in enumerate(iterable, start=start):
|
|
if predicate(item):
|
|
return index
|
|
|
|
|
|
if __name__ == "__main__":
|
|
main()
|