Ordered partitions: Difference between revisions
Content added Content deleted
(Added C#) |
(→{{header|Python}}: Added a version which doesn't import the combinations library.) |
||
Line 1,874: | 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)]] |
[[(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> |
</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}}== |
=={{header|Racket}}== |