Permutations with repetitions: Difference between revisions
→Python - Strict evaluation of the whole set: Pylinted for Python 3. updated primitives and output.
(→Python - Strict evaluation of the whole set: Pylinted for Python 3. updated primitives and output.) |
|||
Line 1,723:
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:
{{Works with|Python|3.7}}
<lang python>'''Permutations of n elements drawn from k values'''
def replicateM(n):▼
'''A functor collecting values accumulated by
n repetitions of m. (List instance only here).
def go(x):▼
)▼
return go(n)▼
# TEST ----------------------------------------------------
# main :: IO ()
def main():
'''Permutations of two elements, drawn from three values'''
print(
replicateM(2)
)([[1, 2, 3], 'abc'])
)
# 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):
'''The binary operator f lifted to a function over two
return lambda xs: lambda ys: concatMap(▼
lists. f applied to each pair of arguments in the
cartesian product of xs and ys.
▲ )(xs)
'''
f(*xy) for xy in product(xs, ys)
]
# DISPLAY -------------------------------------------------
def concatMap(f):▼
# fTable :: String -> (a -> String) ->
return lambda xs: (▼
#
'''Heading -> x display function -> fx display function ->
f -> xs -> tabular string.
'''
def go(xShow, fxShow, f, xs):
ys = [xShow(x) for x in xs]
w = max(map(len, ys))
return s + '\n' + '\n'.join(map(
lambda x, y: y.rjust(w, ' ') + ' -> ' + fxShow(f(x)),
xs, ys
))
return lambda xShow: lambda fxShow: lambda f: lambda xs: go(
xShow, fxShow, f, xs
)
# showList :: [a] -> String
def showList(xs):
'''Stringification of a list.'''
showList(x) if isinstance(x, list) else repr(x) for x in xs
) + ']'
# MAIN ---
if __name__ == '__main__':
main()</lang>
{{Out}}
<pre>Permutations of two elements, drawn from three values:
<pre>[[1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3], [3, 1], [3, 2], [3, 3]]</pre>▼
'abc' -> [['a','a'],['a','b'],['a','c'],['b','a'],['b','b'],['b','c'],['c','a'],['c','b'],['c','c']]</pre>
===Lazy evaluation with a generator===
| |||