Ordered partitions: Difference between revisions
→{{header|Python}}: Added a version which doesn't import the combinations library.
(Added C#) |
(→{{header|Python}}: Added a version which doesn't import the combinations library.) |
||
Line 1,874:
[[(0, 1), (), (2, 3)], [(0, 2), (), (1, 3)], [(0, 3), (), (1, 2)], [(1, 2), (), (0, 3)], [(1, 3), (), (0, 2)], [(2, 3), (), (0, 1)]]
</pre>
Or, more directly, without importing the ''combinations'' library:
{{Works with|Python|3.7}}
<lang python>'''Ordered Partitions'''
# partitions :: [Int] -> [[[Int]]]
def partitions(xs):
'''Ordered partitions of xs.'''
n = sum(xs)
def go(s, n, ys):
return [
[l] + r
for (l, rest) in choose(s)(n)(ys[0])
for r in go(rest, n - ys[0], ys[1:])
] if ys else [[]]
return go(enumFromTo(1)(n), n, xs)
# choose :: [Int] -> Int -> Int -> [([Int], [Int])]
def choose(xs):
'''(m items chosen from n items, the rest)'''
def go(xs, n, m):
f = cons(xs[0])
choice = choose(xs[1:])(n - 1)
return [([], xs)] if 0 == m else (
[(xs, [])] if n == m else (
[first(f)(x) for x in choice(m - 1)] +
[second(f)(x) for x in choice(m)]
)
)
return lambda n: lambda m: go(xs, n, m)
# TEST ----------------------------------------------------
# main :: IO ()
def main():
'''Tests of the partitions function'''
f = partitions
print(
fTable(main.__doc__ + ':')(
lambda x: '\n' + f.__name__ + '(' + repr(x) + ')'
)(
lambda ps: '\n\n' + '\n'.join(repr(p) for p in ps)
)(f)([
[2, 0, 2],
[1, 1, 1]
])
)
# DISPLAY -------------------------------------------------
# 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
)
# GENERIC -------------------------------------------------
# cons :: a -> [a] -> [a]
def cons(x):
'''Construction of a list from x as head,
and xs as tail.
'''
return lambda xs: [x] + xs
# enumFromTo :: (Int, Int) -> [Int]
def enumFromTo(m):
'''Integer enumeration from m to n.'''
return lambda n: list(range(m, 1 + n))
# first :: (a -> b) -> ((a, c) -> (b, c))
def first(f):
'''A simple function lifted to a function over a tuple,
with f applied only the first of two values.
'''
return lambda xy: (f(xy[0]), xy[1])
# second :: (a -> b) -> ((c, a) -> (c, b))
def second(f):
'''A simple function lifted to a function over a tuple,
with f applied only the second of two values.
'''
return lambda xy: (xy[0], f(xy[1]))
# MAIN ---
if __name__ == '__main__':
main()</lang>
{{Out}}
<pre>Tests of the partitions function:
partitions([2, 0, 2]) ->
[[1, 2], [], [3, 4]]
[[1, 3], [], [2, 4]]
[[1, 4], [], [2, 3]]
[[2, 3], [], [1, 4]]
[[2, 4], [], [1, 3]]
[[3, 4], [], [1, 2]]
partitions([1, 1, 1]) ->
[[1], [2], [3]]
[[1], [3], [2]]
[[2], [1], [3]]
[[2], [3], [1]]
[[3], [1], [2]]
[[3], [2], [1]]</pre>
=={{header|Racket}}==
| |||