Ordered partitions
editable example
Click the pencil to open this in an editor, change it, and run it in your browser. The same solution is posted on Rosetta Code.
ghul
use IO.Std.write_line
use Collections.LIST
use Collections.List
use Ghul.Pipes
combinations(items: List[int], k: int) -> Pipe[List[int]] is
if k == 0 then
yield LIST[int]()
elif items.count >= k then
let rest = items[1..<0]
for tail in combinations(rest, k - 1) do
let whole = LIST[int]()
whole.add(items[0])
for value in tail do
whole.add(value)
od
yield whole
od
yield in combinations(rest, k)
fi
si
partitions(items: List[int], sizes: List[int]) -> Pipe[List[List[int]]] is
if sizes.count == 0 then
yield LIST[List[int]]()
else
for block in combinations(items, sizes[0]) do
let remaining = items |> except(block) |> collect_list()
for tail in partitions(remaining, sizes[1..<0]) do
let whole = LIST[List[int]]()
whole.add(block)
for rest in tail do
whole.add(rest)
od
yield whole
od
od
fi
si
braces(block: List[int]) -> string =>
"{{" "{block |> join(", ")}" "}}"
show(sizes: int[]) is
let total = sizes |> reduce(0, (running, size) => running + size)
let items = (1::total) |> collect_list()
write_line("partitions({sizes |> join(", ")}):")
partitions(items, sizes |> collect_list())
|> each(partition =>
write_line(" ({partition |> map(braces) |> join(", ")})"))
si
show([2, 0, 2])