Permutations: Difference between revisions
→Functional: Edited to preserve the input type, pylinted for Python 3, updated output.
(→Functional: Edited to preserve the input type, pylinted for Python 3, updated output.) |
|||
Line 5,588:
===Functional===
The '''itertools.permutations''' function is polymorphic in its inputs but not in its outputs – it discards the type of input lists and strings, coercing all inputs to tuples.
Expressed (without the need for mutating name-bindings) in terms of two universal abstractions: '''reduce''' and '''concatMap''':▼
▲
<lang python>from functools import (reduce)▼
{{Works with|Python|3.7}}
<lang python>'''Permutations of a list, string or tuple'''
from itertools import (chain)
Line 5,596 ⟶ 5,601:
# permutations :: [a] -> [[a]]
def permutations(xs):
'''Type-preserving permutations of xs.
return reduce(▼
lambda a, x: concatMap(
lambda xs: (
Line 5,602 ⟶ 5,609:
)(a),
xs, [[]]
)
return ps if list == t else (
[''.join(x) for x in ps] if str == t else [
t(x) for x in ps
]
)
Line 5,609 ⟶ 5,622:
# main :: IO ()
def main():
'''Permutations of lists, strings and tuples.'''
print(
permutations
)([
[1, 2, 3],
'abc',
(1, 2, 3),
])
)
# GENERIC -------------------------------------------------
# concatMap :: (a -> [b]) -> [a] -> [b]
def concatMap(f):
'''A concatenated list over which a function has been mapped.
The list monad can be derived by using a function f which
wraps its output in a list,
(using an empty list to represent computational failure).'''
return lambda xs: list(
chain.from_iterable(map(f, xs))
▲ map(f, xs)
▲ )
)
# identity :: a -> a
def identity(x):
'''The identity function.'''
return x
# FORMATTING ----------------------------------------------
# fTable :: String -> (a -> String) ->
# (b -> String) -> (a -> b) -> [a] -> String
def fTable(s):
'''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.'''
return '[' + ','.join(showList(x) for x in xs) + ']' if (
isinstance(xs, list)
) else repr(xs)
# MAIN ---
if __name__ == '__main__':
main()</lang>
{{Out}}
<pre>
[1, 2, 3] -> [[1,2,3],[2,3,1],[3,1,2],[2,1,3],[1,3,2],[3,2,1]]
'abc' -> ['abc','bca','cab','bac','acb','cba']</pre>
=={{header|Qi}}==
| |||