Permutations with repetitions: Difference between revisions
→{{header|Python}}: Added a strict evaluation variant (using replicateM)
(→{{header|Python}}: Added a strict evaluation variant (using replicateM)) |
|||
Line 1,571:
=={{header|Python}}==
===Strict evaluation of the whole set===
===Applying itertools.product===▼
To evaluate the whole set of permutations, without the option to make complete evaluation conditional, we can reach for a generic replicateM function for lists:
<lang python>from functools import (reduce)
# MAIN IO ()
def main():
print(
replicateM(2)([1, 2, 3])
)
# GENERIC FUNCTIONS ---------------------------------------
# replicateM :: Int -> [a] -> [[a]]
def replicateM(n):
def loop(f):
def go(x):
return [[]] if 0 >= x else (
liftA2List(lambda a, b: [a] + b)(f)(go(x - 1))
)
return go(n)
return lambda f: loop(f)
# liftA2List :: (a -> b -> c) -> [a] -> [b] -> [c]
def liftA2List(f):
return lambda xs: lambda ys: concatMap(
lambda x: concatMap(lambda y: [f(x, y)])(ys)
)(xs)
# concatMap :: (a -> [b]) -> [a] -> [b]
def concatMap(f):
return lambda xs: (
reduce(lambda a, b: a + b, map(f, xs), [])
)
# MAIN ---
main()</lang>
{{Out}}
<pre>[[1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3], [3, 1], [3, 2], [3, 3]]</pre>
===Lazy evaluation with a generator===
▲====Applying itertools.product====
<lang python>from itertools import product
Line 1,581 ⟶ 1,629:
if w.lower() == 'crack': break</lang>
====Writing a generator====
Or, composing our own generator, by wrapping a function '''from''' an index in the range ''0 .. (distinct items to the power of groupSize)'' '''to''' a unique permutation. (Each permutation is equivalent to a 'number' in the base of the size of the set of distinct items, in which each distinct item functions as a 'digit'):
| |||