Ordered partitions: Difference between revisions
m (added whitespace to task's preamble.) |
m (→{{header|Wren}}: Changed to Wren S/H) |
||
(25 intermediate revisions by 14 users not shown) | |||
Line 48: | Line 48: | ||
<math>\mathit{arg}_1,\mathit{arg}_2,...,\mathit{arg}_n</math> are the arguments — natural numbers — that the sought function receives. |
<math>\mathit{arg}_1,\mathit{arg}_2,...,\mathit{arg}_n</math> are the arguments — natural numbers — that the sought function receives. |
||
<br><br> |
<br><br> |
||
=={{header|11l}}== |
|||
{{trans|Nim}} |
|||
<syntaxhighlight lang="11l">F partitions(lengths) |
|||
[[[Int]]] r |
|||
[(Int, Int)] slices |
|||
V delta = -1 |
|||
V idx = 0 |
|||
L(length) lengths |
|||
assert(length >= 0, ‘lengths must not be negative.’) |
|||
delta += length |
|||
slices.append((idx, delta)) |
|||
idx += length |
|||
V n = sum(lengths) |
|||
V perm = Array(1 .. n) |
|||
L |
|||
[[Int]] part |
|||
L(start, end) slices |
|||
V s = perm[start .. end] |
|||
I !s.is_sorted() |
|||
L.break |
|||
part.append(s) |
|||
L.was_no_break |
|||
r.append(part) |
|||
I !perm.next_permutation() |
|||
L.break |
|||
R r |
|||
F toString(part) |
|||
V result = ‘(’ |
|||
L(s) part |
|||
I result.len > 1 |
|||
result ‘’= ‘, ’ |
|||
result ‘’= ‘{’s.join(‘, ’)‘}’ |
|||
R result‘)’ |
|||
F displayPermutations(lengths) |
|||
print(‘Ordered permutations for (’lengths.join(‘, ’)‘):’) |
|||
L(part) partitions(lengths) |
|||
print(toString(part)) |
|||
:start: |
|||
I :argv.len > 1 |
|||
displayPermutations(:argv[1..].map(Int)) |
|||
E |
|||
displayPermutations([2, 0, 2])</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Ordered permutations for (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}) |
|||
Ordered permutations for (1, 1, 1): |
|||
({1}, {2}, {3}) |
|||
({1}, {3}, {2}) |
|||
({2}, {1}, {3}) |
|||
({2}, {3}, {1}) |
|||
({3}, {1}, {2}) |
|||
({3}, {2}, {1}) |
|||
</pre> |
|||
=={{header|Ada}}== |
=={{header|Ada}}== |
||
partitions.ads: |
partitions.ads: |
||
< |
<syntaxhighlight lang="ada">with Ada.Containers.Indefinite_Ordered_Sets; |
||
with Ada.Containers.Ordered_Sets; |
with Ada.Containers.Ordered_Sets; |
||
package Partitions is |
package Partitions is |
||
Line 63: | Line 133: | ||
(Partition); |
(Partition); |
||
function Create_Partitions (Args : Arguments) return Partition_Sets.Set; |
function Create_Partitions (Args : Arguments) return Partition_Sets.Set; |
||
end Partitions;</ |
end Partitions;</syntaxhighlight> |
||
partitions.adb: |
partitions.adb: |
||
< |
<syntaxhighlight lang="ada">package body Partitions is |
||
-- compare number sets (not provided) |
-- compare number sets (not provided) |
||
function "<" (Left, Right : Number_Sets.Set) return Boolean is |
function "<" (Left, Right : Number_Sets.Set) return Boolean is |
||
Line 213: | Line 283: | ||
return Result; |
return Result; |
||
end Create_Partitions; |
end Create_Partitions; |
||
end Partitions;</ |
end Partitions;</syntaxhighlight> |
||
example main.adb: |
example main.adb: |
||
< |
<syntaxhighlight lang="ada">with Ada.Text_IO; |
||
with Partitions; |
with Partitions; |
||
procedure Main is |
procedure Main is |
||
Line 276: | Line 346: | ||
Ada.Text_IO.New_Line; |
Ada.Text_IO.New_Line; |
||
end; |
end; |
||
end Main;</ |
end Main;</syntaxhighlight> |
||
Output: |
Output: |
||
Line 289: | Line 359: | ||
=={{header|BBC BASIC}}== |
=={{header|BBC BASIC}}== |
||
{{works with|BBC BASIC for Windows}} |
{{works with|BBC BASIC for Windows}} |
||
< |
<syntaxhighlight lang="bbcbasic"> DIM list1%(2) : list1%() = 2, 0, 2 |
||
PRINT "partitions(2,0,2):" |
PRINT "partitions(2,0,2):" |
||
PRINT FNpartitions(list1%()) |
PRINT FNpartitions(list1%()) |
||
Line 340: | Line 410: | ||
j% -= 1 |
j% -= 1 |
||
ENDWHILE |
ENDWHILE |
||
= TRUE</ |
= TRUE</syntaxhighlight> |
||
'''Output:''' |
'''Output:''' |
||
<pre> |
<pre> |
||
Line 376: | Line 446: | ||
=={{header|C}}== |
=={{header|C}}== |
||
Watch out for blank for loops. Iterative permutation generation is described at [[http://en.wikipedia.org/wiki/Permutation#Systematic_generation_of_all_permutations]]; code messness is purely mine. |
Watch out for blank for loops. Iterative permutation generation is described at [[http://en.wikipedia.org/wiki/Permutation#Systematic_generation_of_all_permutations]]; code messness is purely mine. |
||
< |
<syntaxhighlight lang="c">#include <stdio.h> |
||
int next_perm(int size, int * nums) |
int next_perm(int size, int * nums) |
||
Line 426: | Line 496: | ||
return 1; |
return 1; |
||
}</ |
}</syntaxhighlight> |
||
Output: |
Output: |
||
<pre>Part 2 0 2: |
<pre>Part 2 0 2: |
||
Line 444: | Line 514: | ||
{ 0 } { 1 2 } { 3 5 6 } { 4 7 8 9 } |
{ 0 } { 1 2 } { 3 5 6 } { 4 7 8 9 } |
||
....</pre> |
....</pre> |
||
With bitfield:< |
With bitfield:<syntaxhighlight lang="c">#include <stdio.h> |
||
typedef unsigned int uint; |
typedef unsigned int uint; |
||
Line 494: | Line 564: | ||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
=={{header|C sharp}}== |
|||
<syntaxhighlight lang="csharp">using System; |
|||
using System.Linq; |
|||
using System.Collections.Generic; |
|||
public static class OrderedPartitions |
|||
{ |
|||
public static void Main() { |
|||
var input = new [] { new[] { 0, 0, 0, 0, 0 }, new[] { 2, 0, 2 }, new[] { 1, 1, 1 } }; |
|||
foreach (int[] sizes in input) { |
|||
foreach (var partition in Partitions(sizes)) { |
|||
Console.WriteLine(partition.Select(set => set.Delimit(", ").Encase('{','}')).Delimit(", ").Encase('(', ')')); |
|||
} |
|||
Console.WriteLine(); |
|||
} |
|||
} |
|||
static IEnumerable<IEnumerable<int[]>> Partitions(params int[] sizes) { |
|||
var enumerators = new IEnumerator<int[]>[sizes.Length]; |
|||
var unused = Enumerable.Range(1, sizes.Sum()).ToSortedSet(); |
|||
var arrays = sizes.Select(size => new int[size]).ToArray(); |
|||
for (int s = 0; s >= 0; ) { |
|||
if (s == sizes.Length) { |
|||
yield return arrays; |
|||
s--; |
|||
} |
|||
if (enumerators[s] == null) { |
|||
enumerators[s] = Combinations(sizes[s], unused.ToArray()).GetEnumerator(); |
|||
} else { |
|||
unused.UnionWith(arrays[s]); |
|||
} |
|||
if (enumerators[s].MoveNext()) { |
|||
enumerators[s].Current.CopyTo(arrays[s], 0); |
|||
unused.ExceptWith(arrays[s]); |
|||
s++; |
|||
} else { |
|||
enumerators[s] = null; |
|||
s--; |
|||
} |
|||
} |
|||
} |
|||
static IEnumerable<T[]> Combinations<T>(int count, params T[] array) { |
|||
T[] result = new T[count]; |
|||
foreach (int pattern in BitPatterns(array.Length - count, array.Length)) { |
|||
for (int b = 1 << (array.Length - 1), i = 0, r = 0; b > 0; b >>= 1, i++) { |
|||
if ((pattern & b) == 0) result[r++] = array[i]; |
|||
} |
|||
yield return result; |
|||
} |
|||
} |
|||
static IEnumerable<int> BitPatterns(int ones, int length) { |
|||
int initial = (1 << ones) - 1; |
|||
int blockMask = (1 << length) - 1; |
|||
for (int v = initial; v >= initial; ) { |
|||
yield return v; |
|||
if (v == 0) break; |
|||
int w = (v | (v - 1)) + 1; |
|||
w |= (((w & -w) / (v & -v)) >> 1) - 1; |
|||
v = w & blockMask; |
|||
} |
|||
} |
|||
static string Delimit<T>(this IEnumerable<T> source, string separator) => string.Join(separator, source); |
|||
static string Encase(this string s, char start, char end) => start + s + end; |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
({}, {}, {}, {}, {}) |
|||
({1, 2}, {}, {3, 4}) |
|||
({1, 3}, {}, {2, 4}) |
|||
({1, 4}, {}, {2, 3}) |
|||
({2, 3}, {}, {1, 4}) |
|||
({2, 4}, {}, {1, 3}) |
|||
({3, 4}, {}, {1, 2}) |
|||
({1}, {2}, {3}) |
|||
({1}, {3}, {2}) |
|||
({2}, {1}, {3}) |
|||
({2}, {3}, {1}) |
|||
({3}, {1}, {2}) |
|||
({3}, {2}, {1})</pre> |
|||
=={{header|C++}}== |
|||
<syntaxhighlight lang="cpp"> |
|||
#include <iostream> |
|||
#include <algorithm> |
|||
#include <vector> |
|||
#include <numeric> |
|||
void partitions(std::vector<size_t> args) { |
|||
size_t sum = std::accumulate(std::begin(args), std::end(args), 0); |
|||
std::vector<size_t> nums(sum); |
|||
std::iota(std::begin(nums), std::end(nums), 1); |
|||
do { |
|||
size_t total_index = 0; |
|||
std::vector<std::vector<size_t>> parts; |
|||
for (const auto& a : args) { |
|||
std::vector<size_t> part; |
|||
bool cont = true; |
|||
for (size_t j = 0; j < a; ++j) { |
|||
for (const auto& p : part) { |
|||
if (nums[total_index] < p) { |
|||
cont = false; |
|||
break; |
|||
} |
|||
} |
|||
if (cont) { |
|||
part.push_back(nums[total_index]); |
|||
++total_index; |
|||
} |
|||
} |
|||
if (part.size() != a) { |
|||
break; |
|||
} |
|||
parts.push_back(part); |
|||
} |
|||
if (parts.size() == args.size()) { |
|||
std::cout << "("; |
|||
for (const auto& p : parts) { |
|||
std::cout << "{ "; |
|||
for (const auto& e : p) { |
|||
std::cout << e << " "; |
|||
} |
|||
std::cout << "},"; |
|||
} |
|||
std::cout << ")," << std::endl; |
|||
} |
|||
} while (std::next_permutation(std::begin(nums), std::end(nums))); |
|||
} |
|||
int main() { |
|||
std::vector<size_t> args = { 2, 0, 2 }; |
|||
partitions(args); |
|||
std::cin.ignore(); |
|||
std::cin.get(); |
|||
return 0; |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>({ 1 2 },{ },{ 3 4 },), |
|||
({ 1 3 },{ },{ 2 4 },), |
|||
({ 1 4 },{ },{ 2 3 },), |
|||
({ 2 3 },{ },{ 1 4 },), |
|||
({ 2 4 },{ },{ 1 3 },), |
|||
({ 3 4 },{ },{ 1 2 },),</pre> |
|||
=={{header|Common Lisp}}== |
=={{header|Common Lisp}}== |
||
Lexicographical generation of partitions. Pros: can handle duplicate elements; probably faster than some methods generating all permutations then throwing bad ones out. Cons: clunky (which is probably my fault). |
Lexicographical generation of partitions. Pros: can handle duplicate elements; probably faster than some methods generating all permutations then throwing bad ones out. Cons: clunky (which is probably my fault). |
||
< |
<syntaxhighlight lang="lisp">(defun fill-part (x i j l) |
||
(let ((e (elt x i))) |
(let ((e (elt x i))) |
||
(loop for c in l do |
(loop for c in l do |
||
Line 543: | Line 764: | ||
(loop while a do |
(loop while a do |
||
(format t "~a~%" a) |
(format t "~a~%" a) |
||
(setf a (next-part a #'string<))))</ |
(setf a (next-part a #'string<))))</syntaxhighlight>output |
||
<pre>#((1 2) NIL (3 4)) |
<pre>#((1 2) NIL (3 4)) |
||
#((1 3) NIL (2 4)) |
#((1 3) NIL (2 4)) |
||
Line 559: | Line 780: | ||
{{trans|Python}} |
{{trans|Python}} |
||
Using module of the third D entry of the Combination Task. |
Using module of the third D entry of the Combination Task. |
||
< |
<syntaxhighlight lang="d">import std.stdio, std.algorithm, std.range, std.array, std.conv, |
||
combinations3; |
combinations3; |
||
Line 583: | Line 804: | ||
auto b = args.length > 1 ? args.dropOne.to!(int[]) : [2, 0, 2]; |
auto b = args.length > 1 ? args.dropOne.to!(int[]) : [2, 0, 2]; |
||
writefln("%(%s\n%)", b.orderPart); |
writefln("%(%s\n%)", b.orderPart); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>[[1, 2], [], [3, 4]] |
<pre>[[1, 2], [], [3, 4]] |
||
Line 594: | Line 815: | ||
===Alternative Version=== |
===Alternative Version=== |
||
{{trans|C}} |
{{trans|C}} |
||
< |
<syntaxhighlight lang="d">import core.stdc.stdio; |
||
void genBits(size_t N)(ref uint[N] bits, in ref uint[N] parts, |
void genBits(size_t N)(ref uint[N] bits, in ref uint[N] parts, |
||
Line 637: | Line 858: | ||
uint[parts.length] bits; |
uint[parts.length] bits; |
||
genBits(bits, parts, m - 1, m - 1, 0, parts[0], 0); |
genBits(bits, parts, m - 1, m - 1, 0, parts[0], 0); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>[1 2 ][][3 4 ] |
<pre>[1 2 ][][3 4 ] |
||
Line 647: | Line 868: | ||
=={{header|EchoLisp}}== |
=={{header|EchoLisp}}== |
||
< |
<syntaxhighlight lang="scheme"> |
||
(lib 'list) ;; (combinations L k) |
(lib 'list) ;; (combinations L k) |
||
Line 673: | Line 894: | ||
writeln |
writeln |
||
(_partitions (range 1 (1+ (apply + args))) args ))) |
(_partitions (range 1 (1+ (apply + args))) args ))) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 710: | Line 931: | ||
{{trans|Ruby}} |
{{trans|Ruby}} |
||
Brute force approach: |
Brute force approach: |
||
< |
<syntaxhighlight lang="elixir">defmodule Ordered do |
||
def partition([]), do: [[]] |
def partition([]), do: [[]] |
||
def partition(mask) do |
def partition(mask) do |
||
Line 739: | Line 960: | ||
IO.inspect part |
IO.inspect part |
||
end) |
end) |
||
end)</ |
end)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 765: | Line 986: | ||
[[1, 2], [], [3, 4]] |
[[1, 2], [], [3, 4]] |
||
</pre> |
</pre> |
||
=={{header|FreeBASIC}}== |
|||
{{trans|BBC BASIC}} |
|||
<syntaxhighlight lang="freebasic">Function Perm(x() As Integer) As Boolean |
|||
Dim As Integer i, j |
|||
For i = Ubound(x,1)-1 To 0 Step -1 |
|||
If x(i) < x(i+1) Then Exit For |
|||
Next i |
|||
If i < 0 Then Return False |
|||
j = Ubound(x,1) |
|||
While x(j) <= x(i) |
|||
j -= 1 |
|||
Wend |
|||
Swap x(i), x(j) |
|||
i += 1 |
|||
j = Ubound(x,1) |
|||
While i < j |
|||
Swap x(i), x(j) |
|||
i += 1 |
|||
j -= 1 |
|||
Wend |
|||
Return True |
|||
End Function |
|||
Function Particiones(list() As Integer) As String |
|||
Dim As Integer i, j, n, p ', x() |
|||
Dim As String oSS = "" |
|||
n = Ubound(list) |
|||
Dim As Integer x(n) |
|||
For i = 0 To n |
|||
If list(i) Then |
|||
For j = 1 To list(i) |
|||
x(p) = i |
|||
p += 1 |
|||
Next j |
|||
End If |
|||
Next i |
|||
Do |
|||
For i = 0 To n |
|||
oSS += " ( " |
|||
For j = 0 To Ubound(x,1) |
|||
If x(j) = i Then oSS += Str(j+1) + " " |
|||
Next j |
|||
oSS += ")" |
|||
Next i |
|||
oSS += Chr(13) + Chr(10) |
|||
Loop Until Not Perm(x()) |
|||
Return oSS |
|||
End Function |
|||
Dim list2(2) As Integer = {1, 1, 1} |
|||
Print "Particiones(1, 1, 1):" |
|||
Print Particiones(list2()) |
|||
Dim list3(3) As Integer = {1, 2, 0, 1} |
|||
Print !"\nParticiones(1, 2, 0, 1):" |
|||
Print Particiones(list3()) |
|||
Sleep</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Particiones(1, 1, 1): |
|||
( 1 ) ( 2 ) ( 3 ) |
|||
( 1 ) ( 3 ) ( 2 ) |
|||
( 2 ) ( 1 ) ( 3 ) |
|||
( 3 ) ( 1 ) ( 2 ) |
|||
( 2 ) ( 3 ) ( 1 ) |
|||
( 3 ) ( 2 ) ( 1 ) |
|||
Particiones(1, 2, 0, 1): |
|||
( 1 ) ( 2 3 ) ( ) ( 4 ) |
|||
( 1 ) ( 2 4 ) ( ) ( 3 ) |
|||
( 1 ) ( 3 4 ) ( ) ( 2 ) |
|||
( 2 ) ( 1 3 ) ( ) ( 4 ) |
|||
( 2 ) ( 1 4 ) ( ) ( 3 ) |
|||
( 3 ) ( 1 2 ) ( ) ( 4 ) |
|||
( 4 ) ( 1 2 ) ( ) ( 3 ) |
|||
( 3 ) ( 1 4 ) ( ) ( 2 ) |
|||
( 4 ) ( 1 3 ) ( ) ( 2 ) |
|||
( 2 ) ( 3 4 ) ( ) ( 1 ) |
|||
( 3 ) ( 2 4 ) ( ) ( 1 ) |
|||
( 4 ) ( 2 3 ) ( ) ( 1 ) |
|||
</pre> |
|||
=={{header|GAP}}== |
=={{header|GAP}}== |
||
< |
<syntaxhighlight lang="gap">FixedPartitions := function(arg) |
||
local aux; |
local aux; |
||
aux := function(i, u) |
aux := function(i, u) |
||
Line 794: | Line 1,100: | ||
FixedPartitions(1, 1, 1); |
FixedPartitions(1, 1, 1); |
||
# [ [ [ 1 ], [ 2 ], [ 3 ] ], [ [ 1 ], [ 3 ], [ 2 ] ], [ [ 2 ], [ 1 ], [ 3 ] ], |
# [ [ [ 1 ], [ 2 ], [ 3 ] ], [ [ 1 ], [ 3 ], [ 2 ] ], [ [ 2 ], [ 1 ], [ 3 ] ], |
||
# [ [ 2 ], [ 3 ], [ 1 ] ], [ [ 3 ], [ 1 ], [ 2 ] ], [ [ 3 ], [ 2 ], [ 1 ] ] ]</ |
# [ [ 2 ], [ 3 ], [ 1 ] ], [ [ 3 ], [ 1 ], [ 2 ] ], [ [ 3 ], [ 2 ], [ 1 ] ] ]</syntaxhighlight> |
||
=={{header|Go}}== |
=={{header|Go}}== |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 856: | Line 1,162: | ||
} |
} |
||
ordered_part(n) |
ordered_part(n) |
||
}</ |
}</syntaxhighlight> |
||
Example command line use: |
Example command line use: |
||
<pre> |
<pre> |
||
Line 892: | Line 1,198: | ||
=={{header|Groovy}}== |
=={{header|Groovy}}== |
||
Solution: |
Solution: |
||
< |
<syntaxhighlight lang="groovy">def partitions = { int... sizes -> |
||
int n = (sizes as List).sum() |
int n = (sizes as List).sum() |
||
def perms = n == 0 ? [[]] : (1..n).permutations() |
def perms = n == 0 ? [[]] : (1..n).permutations() |
||
Line 904: | Line 1,210: | ||
return recomp[0] <=> recomp[1] |
return recomp[0] <=> recomp[1] |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
Test: |
Test: |
||
< |
<syntaxhighlight lang="groovy">partitions(2, 0, 2).each { |
||
println it |
println it |
||
}</ |
}</syntaxhighlight> |
||
Output: |
Output: |
||
Line 920: | Line 1,226: | ||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
< |
<syntaxhighlight lang="haskell">import Data.List ((\\)) |
||
comb :: Int -> [a] -> [[a]] |
comb :: Int -> [a] -> [[a]] |
||
Line 932: | Line 1,238: | ||
p xs (k:ks) = [ cs:rs | cs <- comb k xs, rs <- p (xs \\ cs) ks ] |
p xs (k:ks) = [ cs:rs | cs <- comb k xs, rs <- p (xs \\ cs) ks ] |
||
main = print $ partitions [2,0,2]</ |
main = print $ partitions [2,0,2]</syntaxhighlight> |
||
An alternative where <code>\\</code> is not needed anymore because <code>comb</code> now not only |
An alternative where <code>\\</code> is not needed anymore because <code>comb</code> now not only |
||
keeps the chosen elements but also the not chosen elements together in a tuple. |
keeps the chosen elements but also the not chosen elements together in a tuple. |
||
< |
<syntaxhighlight lang="haskell">comb :: Int -> [a] -> [([a],[a])] |
||
comb 0 xs = [([],xs)] |
comb 0 xs = [([],xs)] |
||
comb _ [] = [] |
comb _ [] = [] |
||
Line 948: | Line 1,254: | ||
p xs (k:ks) = [ cs:rs | (cs,zs) <- comb k xs, rs <- p zs ks ] |
p xs (k:ks) = [ cs:rs | (cs,zs) <- comb k xs, rs <- p zs ks ] |
||
main = print $ partitions [2,0,2]</ |
main = print $ partitions [2,0,2]</syntaxhighlight> |
||
Output: |
Output: |
||
Line 957: | Line 1,263: | ||
Faster by keeping track of the length of lists: |
Faster by keeping track of the length of lists: |
||
<syntaxhighlight lang="haskell">import Data.Bifunctor (first, second) |
|||
<lang haskell>-- choose m out of n items, return tuple of chosen and the rest |
|||
choose aa _ 0 = [([], aa)] |
|||
choose aa@(a:as) n m |
|||
| n == m = [(aa, [])] |
|||
| otherwise = map (\(x,y) -> (a:x, y)) (choose as (n-1) (m-1)) ++ |
|||
map (\(x,y) -> (x, a:y)) (choose as (n-1) m) |
|||
-- choose m out of n items, return tuple of chosen and the rest |
|||
partitions x = combos [1..n] n x where |
|||
n = sum x |
|||
combos _ _ [] = [[]] |
|||
combos s n (x:xs) = [ l : r | (l,rest) <- choose s n x, |
|||
r <- combos rest (n - x) xs] |
|||
choose :: [Int] -> Int -> Int -> [([Int], [Int])] |
|||
choose [] _ _ = [([], [])] |
|||
choose aa _ 0 = [([], aa)] |
|||
choose aa@(a : as) n m |
|||
| n == m = [(aa, [])] |
|||
| otherwise = |
|||
(first (a :) <$> choose as (n - 1) (m - 1)) |
|||
<> (second (a :) <$> choose as (n - 1) m) |
|||
partitions :: [Int] -> [[[Int]]] |
|||
partitions x = combos [1 .. n] n x |
|||
where |
|||
n = sum x |
|||
combos _ _ [] = [[]] |
|||
combos s n (x : xs) = |
|||
[ l : r |
|||
| (l, rest) <- choose s n x, |
|||
r <- combos rest (n - x) xs |
|||
] |
|||
main :: IO () |
|||
main = mapM_ print $ partitions [5,5,5]</lang> |
|||
main = mapM_ print $ partitions [5, 5, 5]</syntaxhighlight> |
|||
=={{header|J}}== |
=={{header|J}}== |
||
Line 977: | Line 1,294: | ||
Brute force approach: |
Brute force approach: |
||
< |
<syntaxhighlight lang="j">require'stats' |
||
partitions=: ([,] {L:0 (i.@#@, -. [)&;)/"1@>@,@{@({@comb&.> +/\.)</ |
partitions=: ([,] {L:0 (i.@#@, -. [)&;)/"1@>@,@{@({@comb&.> +/\.)</syntaxhighlight> |
||
First we compute each of the corresponding combinations for each argument, then we form their cartesian product and then we restructure each of those products by: eliminating from values populating the the larger set combinations the combinations already picked from the smaller set and using the combinations from the larger set to index into the options which remain. |
First we compute each of the corresponding combinations for each argument, then we form their cartesian product and then we restructure each of those products by: eliminating from values populating the the larger set combinations the combinations already picked from the smaller set and using the combinations from the larger set to index into the options which remain. |
||
Line 984: | Line 1,301: | ||
Examples: |
Examples: |
||
< |
<syntaxhighlight lang="j"> partitions 2 0 2 |
||
┌───┬┬───┐ |
┌───┬┬───┐ |
||
│0 1││2 3│ |
│0 1││2 3│ |
||
Line 1,022: | Line 1,339: | ||
360360 |
360360 |
||
*/ (! +/\.)3 5 7 |
*/ (! +/\.)3 5 7 |
||
360360</ |
360360</syntaxhighlight> |
||
Here's some intermediate results for that first example: |
Here's some intermediate results for that first example: |
||
< |
<syntaxhighlight lang="j"> +/\. 2 0 2 |
||
4 2 2 |
4 2 2 |
||
({@comb&.> +/\.) 2 0 2 |
({@comb&.> +/\.) 2 0 2 |
||
Line 1,047: | Line 1,364: | ||
├───┼┼───┤ |
├───┼┼───┤ |
||
│2 3││0 1│ |
│2 3││0 1│ |
||
└───┴┴───┘</ |
└───┴┴───┘</syntaxhighlight> |
||
In other words, initially we just work with relevant combinations (working from right to left). To understand the step which produces the final result, consider this next sequence of results (J's <code>/</code> operator works from right to left, as that's the pattern established by assignment operations, and because that has some interesting and useful mathematical properties): |
In other words, initially we just work with relevant combinations (working from right to left). To understand the step which produces the final result, consider this next sequence of results (J's <code>/</code> operator works from right to left, as that's the pattern established by assignment operations, and because that has some interesting and useful mathematical properties): |
||
< |
<syntaxhighlight lang="j"> ([,] {L:0 (i.@#@, -. [)&;)/0 1;0 1 |
||
┌───┬───┐ |
┌───┬───┐ |
||
│0 1│2 3│ |
│0 1│2 3│ |
||
Line 1,062: | Line 1,379: | ||
┌───┬───┬───┬───┐ |
┌───┬───┬───┬───┐ |
||
│0 1│2 3│4 5│6 7│ |
│0 1│2 3│4 5│6 7│ |
||
└───┴───┴───┴───┘</ |
└───┴───┴───┴───┘</syntaxhighlight> |
||
Breaking down that last example: |
Breaking down that last example: |
||
< |
<syntaxhighlight lang="j"> (<0 1) ([,] {L:0 (i.@#@, -. [)&;)0 1;2 3;4 5 |
||
┌───┬───┬───┬───┐ |
┌───┬───┬───┬───┐ |
||
│0 1│2 3│4 5│6 7│ |
│0 1│2 3│4 5│6 7│ |
||
└───┴───┴───┴───┘</ |
└───┴───┴───┴───┘</syntaxhighlight> |
||
Here, on the right hand side we form 0 1 0 1 2 3 4 5, count how many things are in it (8), form 0 1 2 3 4 5 6 7 from that and then remove 0 1 (the values in the left argument) leaving us with 2 3 4 5 6 7. Meanwhile, on the left side, keep our left argument intact and use the indices in the remaining boxes to select from the right argument. In theoretical terms this is not particularly efficient, but we are working with very short lists here (because otherwise we run out of memory for the result as a whole), so the actual cost is trivial. Also note that sequential loops tend to be faster than nested loops (though we do get the effect of a nested loop, here - and that was the theoretical inefficiency). |
Here, on the right hand side we form 0 1 0 1 2 3 4 5, count how many things are in it (8), form 0 1 2 3 4 5 6 7 from that and then remove 0 1 (the values in the left argument) leaving us with 2 3 4 5 6 7. Meanwhile, on the left side, keep our left argument intact and use the indices in the remaining boxes to select from the right argument. In theoretical terms this is not particularly efficient, but we are working with very short lists here (because otherwise we run out of memory for the result as a whole), so the actual cost is trivial. Also note that sequential loops tend to be faster than nested loops (though we do get the effect of a nested loop, here - and that was the theoretical inefficiency). |
||
=={{header|Java}}== |
|||
<syntaxhighlight lang="java"> |
|||
import java.util.ArrayList; |
|||
import java.util.Arrays; |
|||
import java.util.List; |
|||
import java.util.stream.Collectors; |
|||
import java.util.stream.IntStream; |
|||
public final class OrderedPartitions { |
|||
public static void main(String[] aArgs) { |
|||
List<Integer> sizes = ( aArgs == null || aArgs.length == 0 ) ? |
|||
List.of( 2, 0, 2 ) : Arrays.stream(aArgs).map( s -> Integer.valueOf(s) ).toList(); |
|||
System.out.println("Partitions for " + sizes + ":"); |
|||
final int total = sizes.stream().reduce(0, Integer::sum); |
|||
List<Integer> permutation = IntStream.rangeClosed(1, total).boxed().collect(Collectors.toList()); |
|||
while ( hasNextPermutation(permutation) ) { |
|||
List<List<Integer>> partition = new ArrayList<List<Integer>>(); |
|||
int sum = 0; |
|||
boolean isValid = true; |
|||
for ( int size : sizes ) { |
|||
List<Integer> subList = permutation.subList(sum, sum + size); |
|||
if ( ! isIncreasing(subList) ) { |
|||
isValid = false; |
|||
break; |
|||
} |
|||
partition.add(subList); |
|||
sum += size; |
|||
} |
|||
if ( isValid ) { |
|||
System.out.println(" ".repeat(4) + partition); |
|||
} |
|||
} |
|||
} |
|||
private static boolean hasNextPermutation(List<Integer> aPerm) { |
|||
final int lastIndex = aPerm.size() - 1; |
|||
int i = lastIndex; |
|||
while ( i > 0 && aPerm.get(i - 1) >= aPerm.get(i) ) { |
|||
i--; |
|||
} |
|||
if ( i <= 0 ) { |
|||
return false; |
|||
} |
|||
int j = lastIndex; |
|||
while ( aPerm.get(j) <= aPerm.get(i - 1) ) { |
|||
j--; |
|||
} |
|||
swap(aPerm, i - 1, j); |
|||
j = lastIndex; |
|||
while ( i < j ) { |
|||
swap(aPerm, i++, j--); |
|||
} |
|||
return true; |
|||
} |
|||
private static boolean isIncreasing(List<Integer> aList) { |
|||
return aList.stream().sorted().toList().equals(aList); |
|||
} |
|||
private static void swap(List<Integer> aList, int aOne, int aTwo) { |
|||
final int temp = aList.get(aOne); |
|||
aList.set(aOne, aList.get(aTwo)); |
|||
aList.set(aTwo, temp); |
|||
} |
|||
} |
|||
</syntaxhighlight> |
|||
{{ out }} |
|||
<pre> |
|||
Partitions for [2, 0, 2]: |
|||
[[1, 3], [], [2, 4]] |
|||
[[1, 4], [], [2, 3]] |
|||
[[2, 3], [], [1, 4]] |
|||
[[2, 4], [], [1, 3]] |
|||
[[3, 4], [], [1, 2]] |
|||
</pre> |
|||
=={{header|JavaScript}}== |
=={{header|JavaScript}}== |
||
Line 1,079: | Line 1,483: | ||
{{trans|Haskell}} |
{{trans|Haskell}} |
||
< |
<syntaxhighlight lang="javascript">(function () { |
||
'use strict'; |
'use strict'; |
||
Line 1,139: | Line 1,543: | ||
return partitions(2, 0, 2); |
return partitions(2, 0, 2); |
||
})();</ |
})();</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
< |
<syntaxhighlight lang="javascript">[[[1, 2], [], [3, 4]], |
||
[[1, 3], [], [2, 4]], |
[[1, 3], [], [2, 4]], |
||
[[1, 4], [], [2, 3]], |
[[1, 4], [], [2, 3]], |
||
[[2, 3], [], [1, 4]], |
[[2, 3], [], [1, 4]], |
||
[[2, 4], [], [1, 3]], |
[[2, 4], [], [1, 3]], |
||
[[3, 4], [], [1, 2]]]</ |
[[3, 4], [], [1, 2]]]</syntaxhighlight> |
||
=={{header|jq}}== |
=={{header|jq}}== |
||
{{works with|jq|1.4}} |
{{works with|jq|1.4}} |
||
''The approach adopted here is similar to the [[#Python]] solution''. |
''The approach adopted here is similar to the [[#Python]] solution''. |
||
< |
<syntaxhighlight lang="jq"># Generate a stream of the distinct combinations of r items taken from the input array. |
||
def combination(r): |
def combination(r): |
||
if r > length or r < 0 then empty |
if r > length or r < 0 then empty |
||
Line 1,172: | Line 1,576: | ||
| [$c] + ($mask[1:] | p(s - $c)) |
| [$c] + ($mask[1:] | p(s - $c)) |
||
end; |
end; |
||
. as $mask | p( [range(1; 1 + ($mask|add))] );</ |
. as $mask | p( [range(1; 1 + ($mask|add))] );</syntaxhighlight> |
||
'''Example''': |
'''Example''': |
||
< |
<syntaxhighlight lang="jq">([],[0,0,0],[1,1,1],[2,0,2]) |
||
| . as $test_case |
| . as $test_case |
||
| "partitions \($test_case):" , ($test_case | partition), ""</ |
| "partitions \($test_case):" , ($test_case | partition), ""</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
< |
<syntaxhighlight lang="sh">$ jq -M -n -c -r -f Ordered_partitions.jq |
||
partitions []: |
partitions []: |
||
Line 1,200: | Line 1,604: | ||
[[2,3],[],[1,4]] |
[[2,3],[],[1,4]] |
||
[[2,4],[],[1,3]] |
[[2,4],[],[1,3]] |
||
[[3,4],[],[1,2]]</ |
[[3,4],[],[1,2]]</syntaxhighlight> |
||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
The method used, as seen in the function masked(), is to take a brute force permutation of size n = sum of partition, |
The method used, as seen in the function masked(), is to take a brute force permutation of size n = sum of partition, |
||
partition it using the provided mask, and then sort the inner lists in order to properly filter duplicates. |
partition it using the provided mask, and then sort the inner lists in order to properly filter duplicates. |
||
<syntaxhighlight lang="julia"> |
|||
<lang Julian> |
|||
using Combinatorics |
using Combinatorics |
||
Line 1,231: | Line 1,635: | ||
println(orderedpartitions([1, 1, 1])) |
println(orderedpartitions([1, 1, 1])) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{output}} |
{{output}} |
||
<pre> |
<pre> |
||
Line 1,249: | Line 1,653: | ||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
< |
<syntaxhighlight lang="scala">// version 1.1.3 |
||
fun nextPerm(perm: IntArray): Boolean { |
fun nextPerm(perm: IntArray): Boolean { |
||
Line 1,317: | Line 1,721: | ||
while (nextPerm(perm)) |
while (nextPerm(perm)) |
||
println("]") |
println("]") |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,350: | Line 1,754: | ||
=={{header|Lua}}== |
=={{header|Lua}}== |
||
A pretty verbose solution. Maybe somebody can replace with something terser/better. |
A pretty verbose solution. Maybe somebody can replace with something terser/better. |
||
< |
<syntaxhighlight lang="lua">--- Create a list {1,...,n}. |
||
local function range(n) |
local function range(n) |
||
local res = {} |
local res = {} |
||
Line 1,438: | Line 1,842: | ||
end |
end |
||
io.write "]" |
io.write "]" |
||
io.write "\n"</ |
io.write "\n"</syntaxhighlight> |
||
Output: |
Output: |
||
Line 1,446: | Line 1,850: | ||
</pre> |
</pre> |
||
=={{header|Mathematica}}== |
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
||
This code works as follows: |
This code works as follows: |
||
'''Permutations''' finds all permutations of the numbers ranging from 1 to n. |
'''Permutations''' finds all permutations of the numbers ranging from 1 to n. |
||
'''w''' finds the required partition for an individual permutation. |
'''w''' finds the required partition for an individual permutation. |
||
'''m''' finds partitions for all permutations. |
'''m''' finds partitions for all permutations. |
||
'''Sort''' and '''Union''' eliminate duplicates. |
'''Sort''' and '''Union''' eliminate duplicates. |
||
<syntaxhighlight lang="mathematica">w[partitions_]:=Module[{s={},t=Total@partitions,list=partitions,k}, n=Length[list]; |
|||
<lang Mathematica> |
|||
w[partitions_]:=Module[{s={},t=Total@partitions,list=partitions,k}, n=Length[list]; |
|||
While[n>0,s=Join[s,{Take[t,(k=First[list])]}];t=Drop[t,k];list=Rest[list];n--]; s] |
While[n>0,s=Join[s,{Take[t,(k=First[list])]}];t=Drop[t,k];list=Rest[list];n--]; s] |
||
m[p_]:=(Sort/@#)&/@(w[#,p]&/@Permutations[Range@Total[p]])//Union</syntaxhighlight> |
|||
'''Usage''' |
|||
Grid displays the output in a table. |
|||
<syntaxhighlight lang="mathematica">Grid@m[{2, 0, 2}] |
|||
Grid@m[{1, 1, 1}]</syntaxhighlight> |
|||
[[File:Example.png]] |
|||
=={{header|Nim}}== |
|||
m[p_]:=(Sort/@#)&/@(w[#,p]&/@Permutations[Range@Total[p]])//Union |
|||
We use the function <code>nextPermutation</code> form standard module “algorithm” to build the permutations. The partition is built by using a list of slices. We keep only the partitions which contain sequences sorted by ascending order. Those partitions are yielded by an iterator. |
|||
</lang> |
|||
The iterator may be called with a list of integer arguments or a single list of integers as argument. |
|||
As requested, the arguments specifying the length of each sequence may also be provided on the command line. |
|||
<syntaxhighlight lang="nim">import algorithm, math, sequtils, strutils |
|||
'''Usage''' |
|||
type Partition = seq[seq[int]] |
|||
Grid displays the output in a table. |
|||
<lang Mathematica> |
|||
Grid@m[{2, 0, 2}] |
|||
func isIncreasing(s: seq[int]): bool = |
|||
Grid@m[{1, 1, 1}] |
|||
## Return true if the sequence is sorted in increasing order. |
|||
</lang> |
|||
var prev = 0 |
|||
for val in s: |
|||
if prev >= val: return false |
|||
prev = val |
|||
result = true |
|||
[[File:Example.png]] |
|||
iterator partitions(lengths: varargs[int]): Partition = |
|||
## Yield the partitions for lengths "lengths". |
|||
# Build the list of slices to use for partitionning. |
|||
var slices: seq[Slice[int]] |
|||
var delta = -1 |
|||
var idx = 0 |
|||
for length in lengths: |
|||
assert length >= 0, "lengths must not be negative." |
|||
inc delta, length |
|||
slices.add idx..delta |
|||
inc idx, length |
|||
# Build the partitions. |
|||
let n = sum(lengths) |
|||
var perm = toSeq(1..n) |
|||
while true: |
|||
block buildPartition: |
|||
var part: Partition |
|||
for slice in slices: |
|||
let s = perm[slice] |
|||
if not s.isIncreasing(): |
|||
break buildPartition |
|||
part.add s |
|||
yield part |
|||
if not perm.nextPermutation(): |
|||
break |
|||
func toString(part: Partition): string = |
|||
## Return the string representation of a partition. |
|||
result = "(" |
|||
for s in part: |
|||
result.addSep(", ", 1) |
|||
result.add '{' & s.join(", ") & '}' |
|||
result.add ')' |
|||
when isMainModule: |
|||
import os |
|||
proc displayPermutations(lengths: varargs[int]) = |
|||
## Display the permutations. |
|||
echo "Ordered permutations for (", lengths.join(", "), "):" |
|||
for part in partitions(lengths): |
|||
echo part.toString |
|||
if paramCount() > 0: |
|||
var args: seq[int] |
|||
for param in commandLineParams(): |
|||
try: |
|||
let val = param.parseInt() |
|||
if val < 0: raise newException(ValueError, "") |
|||
args.add val |
|||
except ValueError: |
|||
quit "Wrong parameter: " & param |
|||
displayPermutations(args) |
|||
else: |
|||
displayPermutations(2, 0, 2)</syntaxhighlight> |
|||
{{out}} |
|||
<pre>$ ./ordered_partitions |
|||
Ordered permutations for (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})</pre> |
|||
<pre>$ ./ordered_partitions 1 1 1 |
|||
Ordered permutations for (1, 1, 1): |
|||
({1}, {2}, {3}) |
|||
({1}, {3}, {2}) |
|||
({2}, {1}, {3}) |
|||
({2}, {3}, {1}) |
|||
({3}, {1}, {2}) |
|||
({3}, {2}, {1})</pre> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
===Threaded Generator Method=== |
|||
Code 1: threaded generator method. This code demonstrates how to make something like Python's |
|||
This code demonstrates how to make something like Python's |
|||
generators or Go's channels by using Thread::Queue. Granted, this is horribly inefficient, with constantly creating and killing threads and whatnot (every time a partition is created, a thread is made to produce the next partition, so thousands if not millions of threads live and die, depending on the problem size). But algorithms are often more naturally expressed in a coroutine manner -- for this example, "making a new partition" and "picking elements for a partition" can be done in separate recursions cleanly if so desired. It's about 20 times slower than the next code example, so there. |
generators or Go's channels by using Thread::Queue. Granted, this is horribly inefficient, with constantly creating and killing threads and whatnot (every time a partition is created, a thread is made to produce the next partition, so thousands if not millions of threads live and die, depending on the problem size). But algorithms are often more naturally expressed in a coroutine manner -- for this example, "making a new partition" and "picking elements for a partition" can be done in separate recursions cleanly if so desired. It's about 20 times slower than the next code example, so there. |
||
<lang |
<syntaxhighlight lang="perl">use strict; |
||
use warnings; |
|||
use Thread 'async'; |
|||
use Thread::Queue; |
use Thread::Queue; |
||
Line 1,508: | Line 2,001: | ||
}; |
}; |
||
$q = |
$q = Thread::Queue->new; |
||
(async{ &$gen; # start the main work load |
(async{ &$gen; # start the main work load |
||
$q->enqueue(undef) # signal that there's no more data |
$q->enqueue(undef) # signal that there's no more data |
||
Line 1,524: | Line 2,017: | ||
print "@$a | @$b | @$rb\n"; |
print "@$a | @$b | @$rb\n"; |
||
} |
} |
||
}</syntaxhighlight> |
|||
} |
|||
</lang> |
|||
===Recursive solution=== |
|||
{{trans| |
{{trans|Raku}} |
||
<lang |
<syntaxhighlight lang="perl">use strict; |
||
use warnings; |
|||
use List::Util 1.33 qw(sum pairmap); |
|||
sub partition { |
sub partition { |
||
Line 1,547: | Line 2,041: | ||
print "(" . join(', ', map { "{".join(', ', @$_)."}" } @$_) . ")\n" |
print "(" . join(', ', map { "{".join(', ', @$_)."}" } @$_) . ")\n" |
||
for partition( @ARGV ? @ARGV : (2, 0, 2) );</ |
for partition( @ARGV ? @ARGV : (2, 0, 2) );</syntaxhighlight> |
||
Example command-line use: |
Example command-line use: |
||
Line 1,568: | Line 2,062: | ||
</pre> |
</pre> |
||
The set of ordered partitions is not returned in lexicographical order itself; but it's supposed to be a set so that's hopefully okay. (One could sort the output before printing, but (unlike in |
The set of ordered partitions is not returned in lexicographical order itself; but it's supposed to be a set so that's hopefully okay. (One could sort the output before printing, but (unlike in Raku) Perl's built-in sort routine cannot meaningfully compare arrays without being passed a custom comparator to do that, which is a little messy and thus omitted here.) |
||
=={{header|Perl 6}}== |
|||
{{works with|Rakudo|2018.04.1}} |
|||
<lang perl6>sub partition(@mask is copy) { |
|||
my @op; |
|||
my $last = [+] @mask or return [] xx 1; |
|||
for @mask.kv -> $k, $v { |
|||
next unless $v; |
|||
temp @mask[$k] -= 1; |
|||
for partition @mask -> @p { |
|||
@p[$k].push: $last; |
|||
@op.push: @p; |
|||
} |
|||
} |
|||
return @op; |
|||
} |
|||
.say for reverse partition [2,0,2];</lang> |
|||
{{out}} |
|||
<pre>[[1, 2], (Any), [3, 4]] |
|||
[[1, 3], (Any), [2, 4]] |
|||
[[2, 3], (Any), [1, 4]] |
|||
[[1, 4], (Any), [2, 3]] |
|||
[[2, 4], (Any), [1, 3]] |
|||
[[3, 4], (Any), [1, 2]]</pre> |
|||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
Uses the permutes() routine [new in 1.0.2], which handles duplicate elements properly, so in the {1,2,3,4} test |
|||
Note that the builtin permute() function returns results in an idiosyncratic manner, so we use sort a lot and check for duplicates, |
|||
this only generates 12,600 combinations, whereas the previous version generated and obviously filtered and sorted |
|||
which might make this a tad inefficient. |
|||
all of the possible 3,628,800 full permutations, therefore it is now at least a couple of hundred times faster. |
|||
<lang Phix>function partitions(sequence s) |
|||
<!--<syntaxhighlight lang="phix">(phixonline)--> |
|||
integer N = sum(s) |
|||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
sequence set = tagset(N), perm, |
|||
<span style="color: #7060A8;">requires</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"1.0.2"</span><span style="color: #0000FF;">)</span> |
|||
results = {}, result, resi |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">partitions</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> |
|||
for i=1 to factorial(N) do |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">N</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sum</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> |
|||
perm = permute(i,set) |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">pset</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{},</span> <span style="color: #000080;font-style:italic;">-- eg s==={2,0,2} -> {1,1,3,3}</span> |
|||
integer n = 1 |
|||
<span style="color: #000000;">rn</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- "" -> <nowiki>{{</nowiki>0,0},{},{0,0<nowiki>}}</nowiki></span> |
|||
result = {} |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">l</span> <span style="color: #008080;">do</span> |
|||
for j=1 to length(s) do |
|||
<span style="color: #000000;">pset</span> <span style="color: #0000FF;">&=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span> |
|||
resi = {} |
|||
<span style="color: #000000;">rn</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span> |
|||
for k=1 to s[j] do |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
resi = append(resi,perm[n]) |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">pset</span><span style="color: #0000FF;">={}</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">rn</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #000080;font-style:italic;">-- edge case</span> |
|||
n += 1 |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">permutes</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pset</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span> |
|||
end for |
|||
<span style="color: #000080;font-style:italic;">-- eg {1,1,3,3} means put 1,2 in [1], 3,4 in [3] |
|||
result = append(result,sort(resi)) |
|||
-- .. {3,3,1,1} means put 1,2 in [3], 3,4 in [1]</span> |
|||
end for |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
if not find(result,results) then |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">ri</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span> <span style="color: #000080;font-style:italic;">-- a "flat" permute</span> |
|||
results = append(results,result) |
|||
<span style="color: #000000;">rdii</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- where per set</span> |
|||
end if |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">rii</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> |
|||
end for |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ri</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
return sort(results) |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">rdx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ri</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">],</span> <span style="color: #000080;font-style:italic;">-- which set</span> |
|||
end function |
|||
<span style="color: #000000;">rnx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rdii</span><span style="color: #0000FF;">[</span><span style="color: #000000;">rdx</span><span style="color: #0000FF;">]</span> <span style="color: #000080;font-style:italic;">-- wherein""</span> |
|||
<span style="color: #000000;">rii</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
ppOpt({pp_Nest,1}) |
|||
<span style="color: #000000;">rn</span><span style="color: #0000FF;">[</span><span style="color: #000000;">rdx</span><span style="color: #0000FF;">][</span><span style="color: #000000;">rnx</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rii</span> <span style="color: #000080;font-style:italic;">-- plant 1..N</span> |
|||
pp(partitions({2,0,2})) |
|||
<span style="color: #000000;">rdii</span><span style="color: #0000FF;">[</span><span style="color: #000000;">rdx</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rnx</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> |
|||
pp(partitions({1,1,1})) |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
pp(partitions({1,2,0,1})) |
|||
<span style="color: #7060A8;">assert</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rii</span><span style="color: #0000FF;">=</span><span style="color: #000000;">N</span><span style="color: #0000FF;">)</span> |
|||
pp(partitions({})) |
|||
<span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rn</span><span style="color: #0000FF;">)</span> |
|||
pp(partitions({0,0,0}))</lang> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
<span style="color: #008080;">procedure</span> <span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">q</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">partitions</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #004080;">string</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">ia</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">q</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">?{</span><span style="color: #008000;">"is"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">""</span><span style="color: #0000FF;">}:{</span><span style="color: #008000;">"are"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"s"</span><span style="color: #0000FF;">})</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"There %s %,d ordered partion%s for %v:\n{%s}\n"</span><span style="color: #0000FF;">,</span> |
|||
<span style="color: #0000FF;">{</span><span style="color: #000000;">ia</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">q</span><span style="color: #0000FF;">),</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">shorten</span><span style="color: #0000FF;">(</span><span style="color: #000000;">q</span><span style="color: #0000FF;">,</span><span style="color: #008000;">""</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%v"</span><span style="color: #0000FF;">),</span><span style="color: #008000;">"\n "</span><span style="color: #0000FF;">)})</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span> |
|||
<span style="color: #7060A8;">papply</span><span style="color: #0000FF;">({{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">},{},{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}},</span><span style="color: #000000;">test</span><span style="color: #0000FF;">)</span> |
|||
<!--</syntaxhighlight>--> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
There are 6 ordered partions for {2,0,2}: |
|||
{{{1,2}, {}, {3,4}}, |
|||
{{{1,2},{},{3,4}} |
|||
{{1, |
{{1,3},{},{2,4}} |
||
{{ |
{{1,4},{},{2,3}} |
||
{{2, |
{{2,3},{},{1,4}} |
||
{{ |
{{2,4},{},{1,3}} |
||
{{ |
{{3,4},{},{1,2}}} |
||
There are 6 ordered partions for {1,1,1}: |
|||
{{1}, {3}, {2}}, |
|||
{{{1},{2},{3}} |
|||
{{ |
{{1},{3},{2}} |
||
{{ |
{{2},{1},{3}} |
||
{{3}, |
{{3},{1},{2}} |
||
{{ |
{{2},{3},{1}} |
||
{{ |
{{3},{2},{1}}} |
||
There are 12 ordered partions for {1,2,0,1}: |
|||
{{1}, {3,4}, {}, {2}}, |
|||
{{{1},{2,3},{},{4}} |
|||
{{ |
{{1},{2,4},{},{3}} |
||
{{ |
{{1},{3,4},{},{2}} |
||
{{ |
{{2},{1,3},{},{4}} |
||
{{ |
{{2},{1,4},{},{3}} |
||
{{3}, |
{{3},{1,2},{},{4}} |
||
{{4}, |
{{4},{1,2},{},{3}} |
||
{{ |
{{3},{1,4},{},{2}} |
||
{{4}, |
{{4},{1,3},{},{2}} |
||
{{2},{3,4},{},{1}} |
|||
{{3},{2,4},{},{1}} |
|||
{{4},{2,3},{},{1}}} |
|||
There are 12,600 ordered partions for {1,2,3,4}: |
|||
{{{1},{2,3},{4,5,6},{7,8,9,10}} |
|||
{{1},{2,3},{4,5,7},{6,8,9,10}} |
|||
{{1},{2,3},{4,5,8},{6,7,9,10}} |
|||
{{1},{2,3},{4,5,9},{6,7,8,10}} |
|||
{{1},{2,3},{4,5,10},{6,7,8,9}} |
|||
... |
|||
{{9},{7,10},{5,6,8},{1,2,3,4}} |
|||
{{10},{7,9},{5,6,8},{1,2,3,4}} |
|||
{{8},{9,10},{5,6,7},{1,2,3,4}} |
|||
{{9},{8,10},{5,6,7},{1,2,3,4}} |
|||
{{10},{8,9},{5,6,7},{1,2,3,4}}} |
|||
There is 1 ordered partion for {}: |
|||
{{}} |
{{}} |
||
There is 1 ordered partion for {0,0,0}: |
|||
{{{}, {}, {}}} |
|||
{{{},{},{}}} |
|||
</pre> |
</pre> |
||
=={{header|PicoLisp}}== |
=={{header|PicoLisp}}== |
||
Uses the 'comb' function from [[Combinations#PicoLisp]] |
Uses the 'comb' function from [[Combinations#PicoLisp]] |
||
< |
<syntaxhighlight lang="picolisp">(de partitions (Args) |
||
(let Lst (range 1 (apply + Args)) |
(let Lst (range 1 (apply + Args)) |
||
(recur (Args Lst) |
(recur (Args Lst) |
||
Line 1,669: | Line 2,167: | ||
'((R) (cons L R)) |
'((R) (cons L R)) |
||
(recurse (cdr Args) (diff Lst L)) ) ) |
(recurse (cdr Args) (diff Lst L)) ) ) |
||
(comb (car Args) Lst) ) ) ) ) )</ |
(comb (car Args) Lst) ) ) ) ) )</syntaxhighlight> |
||
Output: |
Output: |
||
<pre>: (more (partitions (2 0 2))) |
<pre>: (more (partitions (2 0 2))) |
||
Line 1,690: | Line 2,188: | ||
=={{header|Python}}== |
=={{header|Python}}== |
||
< |
<syntaxhighlight lang="python">from itertools import combinations |
||
def partitions(*args): |
def partitions(*args): |
||
Line 1,704: | Line 2,202: | ||
return p(s, *args) |
return p(s, *args) |
||
print partitions(2, 0, 2)</ |
print partitions(2, 0, 2)</syntaxhighlight> |
||
An equivalent but terser solution. |
An equivalent but terser solution. |
||
< |
<syntaxhighlight lang="python">from itertools import combinations as comb |
||
def partitions(*args): |
def partitions(*args): |
||
Line 1,716: | Line 2,214: | ||
return p(range(1, sum(args) + 1), *args) |
return p(range(1, sum(args) + 1), *args) |
||
print partitions(2, 0, 2)</ |
print partitions(2, 0, 2)</syntaxhighlight> |
||
Output: |
Output: |
||
Line 1,723: | Line 2,221: | ||
[[(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}} |
|||
<syntaxhighlight 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()</syntaxhighlight> |
|||
{{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}}== |
||
Line 1,728: | Line 2,357: | ||
{{trans|Haskell}} |
{{trans|Haskell}} |
||
<syntaxhighlight lang="racket"> |
|||
<lang Racket> |
|||
#lang racket |
#lang racket |
||
(define (comb k xs) |
(define (comb k xs) |
||
Line 1,752: | Line 2,381: | ||
(run 2 0 2) |
(run 2 0 2) |
||
(run 1 1 1) |
(run 1 1 1) |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output: |
Output: |
||
Line 1,772: | Line 2,401: | ||
((3) (2) (1)) |
((3) (2) (1)) |
||
</pre> |
</pre> |
||
=={{header|Raku}}== |
|||
(formerly Perl 6) |
|||
{{works with|Rakudo|2018.04.1}} |
|||
<syntaxhighlight lang="raku" line>sub partition(@mask is copy) { |
|||
my @op; |
|||
my $last = [+] @mask or return [] xx 1; |
|||
for @mask.kv -> $k, $v { |
|||
next unless $v; |
|||
temp @mask[$k] -= 1; |
|||
for partition @mask -> @p { |
|||
@p[$k].push: $last; |
|||
@op.push: @p; |
|||
} |
|||
} |
|||
return @op; |
|||
} |
|||
.say for reverse partition [2,0,2];</syntaxhighlight> |
|||
{{out}} |
|||
<pre>[[1, 2], (Any), [3, 4]] |
|||
[[1, 3], (Any), [2, 4]] |
|||
[[2, 3], (Any), [1, 4]] |
|||
[[1, 4], (Any), [2, 3]] |
|||
[[2, 4], (Any), [1, 3]] |
|||
[[3, 4], (Any), [1, 2]]</pre> |
|||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
< |
<syntaxhighlight lang="rexx">//*REXX program displays the ordered partitions as: orderedPartitions(i, j, k, ···). */ |
||
call orderedPartitions 2,0,2 /*Note: 2,,2 will also work. */ |
call orderedPartitions 2,0,2 /*Note: 2,,2 will also work. */ |
||
call orderedPartitions 1,1,1 |
call orderedPartitions 1,1,1 |
||
Line 1,817: | Line 2,472: | ||
say center($, length(hdr) ) /*display numbers in ordered partition.*/ |
say center($, length(hdr) ) /*display numbers in ordered partition.*/ |
||
end /*g*/ |
end /*g*/ |
||
return</ |
return</syntaxhighlight> |
||
{{out|output|text= when using the default inputs:}} |
{{out|output|text= when using the default inputs:}} |
||
<pre> |
<pre> |
||
Line 1,856: | Line 2,511: | ||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
'''Brute force approach:''' simple but very slow |
'''Brute force approach:''' simple but very slow |
||
< |
<syntaxhighlight lang="ruby">def partition(mask) |
||
return [[]] if mask.empty? |
return [[]] if mask.empty? |
||
[*1..mask.inject(:+)].permutation.map {|perm| |
[*1..mask.inject(:+)].permutation.map {|perm| |
||
mask.map {|num_elts| perm.shift(num_elts).sort } |
mask.map {|num_elts| perm.shift(num_elts).sort } |
||
}.uniq |
}.uniq |
||
end</ |
end</syntaxhighlight> |
||
'''Recursive version:''' faster |
'''Recursive version:''' faster |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="ruby">def part(s, args) |
||
return [[]] if args.empty? |
return [[]] if args.empty? |
||
s.combination(args[0]).each_with_object([]) do |c, res| |
s.combination(args[0]).each_with_object([]) do |c, res| |
||
Line 1,874: | Line 2,529: | ||
return [[]] if args.empty? |
return [[]] if args.empty? |
||
part((1..args.inject(:+)).to_a, args) |
part((1..args.inject(:+)).to_a, args) |
||
end</ |
end</syntaxhighlight> |
||
'''Test:''' |
'''Test:''' |
||
< |
<syntaxhighlight lang="ruby">[[],[0,0,0],[1,1,1],[2,0,2]].each do |test_case| |
||
puts "partitions #{test_case}:" |
puts "partitions #{test_case}:" |
||
partition(test_case).each{|part| p part } |
partition(test_case).each{|part| p part } |
||
puts |
puts |
||
end</ |
end</syntaxhighlight> |
||
{{Output}} |
{{Output}} |
||
<pre> |
<pre> |
||
Line 1,905: | Line 2,560: | ||
[[2, 4], [], [1, 3]] |
[[2, 4], [], [1, 3]] |
||
[[3, 4], [], [1, 2]] |
[[3, 4], [], [1, 2]] |
||
</pre> |
|||
=={{header|Rust}}== |
|||
<syntaxhighlight lang="rust"> |
|||
use itertools::Itertools; |
|||
type NArray = Vec<Vec<Vec<usize>>>; |
|||
fn generate_partitions(args: &[usize]) -> NArray { |
|||
// calculate the sum of all partitions |
|||
let max = args.iter().sum(); |
|||
// generate combinations with the given lengths |
|||
// for each partition |
|||
let c = args.iter().fold(vec![], |mut acc, arg| { |
|||
acc.push((1..=max).combinations(*arg).collect::<Vec<_>>()); |
|||
acc |
|||
}); |
|||
// create a cartesian product of all individual combinations |
|||
// filter/keep only where all the elements are there and exactly once |
|||
c.iter() |
|||
.map(|i| i.iter().cloned()) |
|||
.multi_cartesian_product() |
|||
.unique() |
|||
.filter(|x| x.iter().cloned().flatten().unique().count() == max) |
|||
.collect::<Vec<_>>() |
|||
} |
|||
#[allow(clippy::clippy::ptr_arg)] |
|||
fn print_partitions(result: &NArray) { |
|||
println!("Partitions:"); |
|||
for partition in result { |
|||
println!("{:?}", partition); |
|||
} |
|||
} |
|||
fn main() { |
|||
print_partitions(generate_partitions(&[2, 0, 2]).as_ref()); |
|||
print_partitions(generate_partitions(&[1, 1, 1]).as_ref()); |
|||
print_partitions(generate_partitions(&[2, 3]).as_ref()); |
|||
print_partitions(generate_partitions(&[0]).as_ref()); |
|||
} |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Partitions: |
|||
[[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], [2], [3]] |
|||
[[1], [3], [2]] |
|||
[[2], [1], [3]] |
|||
[[2], [3], [1]] |
|||
[[3], [1], [2]] |
|||
[[3], [2], [1]] |
|||
Partitions: |
|||
[[1, 2], [3, 4, 5]] |
|||
[[1, 3], [2, 4, 5]] |
|||
[[1, 4], [2, 3, 5]] |
|||
[[1, 5], [2, 3, 4]] |
|||
[[2, 3], [1, 4, 5]] |
|||
[[2, 4], [1, 3, 5]] |
|||
[[2, 5], [1, 3, 4]] |
|||
[[3, 4], [1, 2, 5]] |
|||
[[3, 5], [1, 2, 4]] |
|||
[[4, 5], [1, 2, 3]] |
|||
Partitions: |
|||
[[]] |
|||
</pre> |
</pre> |
||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
{{trans|Ruby}} |
{{trans|Ruby}} |
||
< |
<syntaxhighlight lang="ruby">func part(_, {.is_empty}) { [[]] } |
||
func partitions({.is_empty}) { [[]] } |
func partitions({.is_empty}) { [[]] } |
||
Line 1,915: | Line 2,642: | ||
gather { |
gather { |
||
s.combinations(args[0], { |*c| |
s.combinations(args[0], { |*c| |
||
part(s - c, args. |
part(s - c, args.slice(1)).each{|r| take([c] + r) } |
||
}) |
}) |
||
} |
} |
||
Line 1,928: | Line 2,655: | ||
partitions(test_case).each{|part| say part } |
partitions(test_case).each{|part| say part } |
||
print "\n" |
print "\n" |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,957: | Line 2,684: | ||
=={{header|Tcl}}== |
=={{header|Tcl}}== |
||
{{tcllib|struct::set}} |
{{tcllib|struct::set}} |
||
< |
<syntaxhighlight lang="tcl">package require Tcl 8.5 |
||
package require struct::set |
package require struct::set |
||
Line 2,008: | Line 2,735: | ||
return [buildPartitions $startingSet {*}$args] |
return [buildPartitions $startingSet {*}$args] |
||
}</ |
}</syntaxhighlight> |
||
Demonstration code: |
Demonstration code: |
||
< |
<syntaxhighlight lang="tcl">puts [partitions 1 1 1] |
||
puts [partitions 2 2] |
puts [partitions 2 2] |
||
puts [partitions 2 0 2] |
puts [partitions 2 0 2] |
||
puts [partitions 2 2 0]</ |
puts [partitions 2 2 0]</syntaxhighlight> |
||
Output: |
Output: |
||
<pre> |
<pre> |
||
Line 2,023: | Line 2,750: | ||
=={{header|Ursala}}== |
=={{header|Ursala}}== |
||
< |
<syntaxhighlight lang="ursala">#import std |
||
#import nat |
#import nat |
||
Line 2,030: | Line 2,757: | ||
-+ |
-+ |
||
~&art^?\~&alNCNC ^|JalSPfarSPMplrDSL/~& ^DrlPrrPlXXS/~&rt ^DrlrjXS/~&l choices@lrhPX, |
~&art^?\~&alNCNC ^|JalSPfarSPMplrDSL/~& ^DrlPrrPlXXS/~&rt ^DrlrjXS/~&l choices@lrhPX, |
||
^\~& nrange/1+ sum:-0+-</ |
^\~& nrange/1+ sum:-0+-</syntaxhighlight> |
||
The library function <code>choices</code> used in this solution takes a pair <math>(s,k)</math> and returns the set of all subsets of <math>s</math> having cardinality <math>k</math>. The library function <code>nrange</code> takes a pair of natural numbers to the minimum consecutive sequence containing them. The <code>sum</code> function adds a pair of natural numbers.< |
The library function <code>choices</code> used in this solution takes a pair <math>(s,k)</math> and returns the set of all subsets of <math>s</math> having cardinality <math>k</math>. The library function <code>nrange</code> takes a pair of natural numbers to the minimum consecutive sequence containing them. The <code>sum</code> function adds a pair of natural numbers.<syntaxhighlight lang="ursala">#cast %nLLL |
||
test = opart <2,0,2></ |
test = opart <2,0,2></syntaxhighlight> |
||
output: |
output: |
||
<pre>< |
<pre>< |
||
Line 2,042: | Line 2,769: | ||
<<2,4>,<>,<1,3>>, |
<<2,4>,<>,<1,3>>, |
||
<<3,4>,<>,<1,2>>></pre> |
<<3,4>,<>,<1,2>>></pre> |
||
=={{header|Wren}}== |
|||
{{trans|Go}} |
|||
<syntaxhighlight lang="wren">import "os" for Process |
|||
var genPart // recursive so predeclare |
|||
genPart = Fn.new { |n, res, pos| |
|||
if (pos == res.count) { |
|||
var x = List.filled(n.count, null) |
|||
for (i in 0...x.count) x[i] = [] |
|||
var i = 0 |
|||
for (c in res) { |
|||
x[c].add(i+1) |
|||
i = i + 1 |
|||
} |
|||
System.print(x) |
|||
return |
|||
} |
|||
for (i in 0...n.count) { |
|||
if (n[i] != 0) { |
|||
n[i] = n[i] - 1 |
|||
res[pos] = i |
|||
genPart.call(n, res, pos+1) |
|||
n[i] = n[i] + 1 |
|||
} |
|||
} |
|||
} |
|||
var orderedPart = Fn.new { |nParts| |
|||
System.print("Ordered %(nParts)") |
|||
var sum = 0 |
|||
for (c in nParts) sum = sum + c |
|||
genPart.call(nParts, List.filled(sum, 0), 0) |
|||
} |
|||
var args = Process.arguments |
|||
if (args.count == 0) { |
|||
orderedPart.call([2, 0, 2]) |
|||
return |
|||
} |
|||
var n = List.filled(args.count, 0) |
|||
var i = 0 |
|||
for (a in args) { |
|||
n[i] = Num.fromString(a) |
|||
if (n[i] < 0) { |
|||
System.print("negative partition size not meaningful") |
|||
return |
|||
} |
|||
i = i + 1 |
|||
} |
|||
orderedPart.call(n)</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
$ wren_cli ordered_partitions.wren |
|||
Ordered [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]] |
|||
$ wren_cli ordered_partitions.wren 1 1 1 |
|||
Ordered [1, 1, 1] |
|||
[[1], [2], [3]] |
|||
[[1], [3], [2]] |
|||
[[2], [1], [3]] |
|||
[[3], [1], [2]] |
|||
[[2], [3], [1]] |
|||
[[3], [2], [1]] |
|||
$ wren_cli ordered_partitions.wren 1 2 3 4 | head |
|||
Ordered [1, 2, 3, 4] |
|||
[[1], [2, 3], [4, 5, 6], [7, 8, 9, 10]] |
|||
[[1], [2, 3], [4, 5, 7], [6, 8, 9, 10]] |
|||
[[1], [2, 3], [4, 5, 8], [6, 7, 9, 10]] |
|||
[[1], [2, 3], [4, 5, 9], [6, 7, 8, 10]] |
|||
[[1], [2, 3], [4, 5, 10], [6, 7, 8, 9]] |
|||
[[1], [2, 3], [4, 6, 7], [5, 8, 9, 10]] |
|||
[[1], [2, 3], [4, 6, 8], [5, 7, 9, 10]] |
|||
[[1], [2, 3], [4, 6, 9], [5, 7, 8, 10]] |
|||
[[1], [2, 3], [4, 6, 10], [5, 7, 8, 9]] |
|||
</pre> |
|||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="zkl">fcn partitions(args){ |
||
args=vm.arglist; |
args=vm.arglist; |
||
s:=(1).pump(args.sum(0),List); // (1,2,3,...) |
s:=(1).pump(args.sum(0),List); // (1,2,3,...) |
||
Line 2,057: | Line 2,868: | ||
res |
res |
||
}(s,args) |
}(s,args) |
||
}</ |
}</syntaxhighlight> |
||
< |
<syntaxhighlight lang="zkl">args:=vm.arglist.apply("toInt"); // aka argv[1..] |
||
if(not args) args=T(2,0,2); |
if(not args) args=T(2,0,2); |
||
partitions(args.xplode()).pump(Console.println,Void); |
partitions(args.xplode()).pump(Console.println,Void); |
||
// or: foreach p in (partitions(1,1,1)){ println(p) }</ |
// or: foreach p in (partitions(1,1,1)){ println(p) }</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
Latest revision as of 10:14, 9 January 2024
You are encouraged to solve this task according to the task description, using any language you may know.
In this task we want to find the ordered partitions into fixed-size blocks.
This task is related to Combinations in that it has to do with discrete mathematics and moreover a helper function to compute combinations is (probably) needed to solve this task.
should generate all distributions of the elements in into blocks of respective size .
Example 1: would create:
{({1, 2}, {}, {3, 4}), ({1, 3}, {}, {2, 4}), ({1, 4}, {}, {2, 3}), ({2, 3}, {}, {1, 4}), ({2, 4}, {}, {1, 3}), ({3, 4}, {}, {1, 2})}
Example 2: would create:
{({1}, {2}, {3}), ({1}, {3}, {2}), ({2}, {1}, {3}), ({2}, {3}, {1}), ({3}, {1}, {2}), ({3}, {2}, {1})}
Note that the number of elements in the list is
(see the definition of the binomial coefficient if you are not familiar with this notation) and the number of elements remains the same regardless of how the argument is permuted (i.e. the multinomial coefficient).
Also, creates the permutations of and thus there would be elements in the list.
Note: Do not use functions that are not in the standard library of the programming language you use. Your file should be written so that it can be executed on the command line and by default outputs the result of . If the programming language does not support polyvariadic functions pass a list as an argument.
Notation
Here are some explanatory remarks on the notation used in the task description:
denotes the set of consecutive numbers from to , e.g. if .
is the mathematical notation for summation, e.g. (see also [1]).
are the arguments — natural numbers — that the sought function receives.
11l
F partitions(lengths)
[[[Int]]] r
[(Int, Int)] slices
V delta = -1
V idx = 0
L(length) lengths
assert(length >= 0, ‘lengths must not be negative.’)
delta += length
slices.append((idx, delta))
idx += length
V n = sum(lengths)
V perm = Array(1 .. n)
L
[[Int]] part
L(start, end) slices
V s = perm[start .. end]
I !s.is_sorted()
L.break
part.append(s)
L.was_no_break
r.append(part)
I !perm.next_permutation()
L.break
R r
F toString(part)
V result = ‘(’
L(s) part
I result.len > 1
result ‘’= ‘, ’
result ‘’= ‘{’s.join(‘, ’)‘}’
R result‘)’
F displayPermutations(lengths)
print(‘Ordered permutations for (’lengths.join(‘, ’)‘):’)
L(part) partitions(lengths)
print(toString(part))
:start:
I :argv.len > 1
displayPermutations(:argv[1..].map(Int))
E
displayPermutations([2, 0, 2])
- Output:
Ordered permutations for (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}) Ordered permutations for (1, 1, 1): ({1}, {2}, {3}) ({1}, {3}, {2}) ({2}, {1}, {3}) ({2}, {3}, {1}) ({3}, {1}, {2}) ({3}, {2}, {1})
Ada
partitions.ads:
with Ada.Containers.Indefinite_Ordered_Sets;
with Ada.Containers.Ordered_Sets;
package Partitions is
-- Argument type for Create_Partitions: Array of Numbers
type Arguments is array (Positive range <>) of Natural;
package Number_Sets is new Ada.Containers.Ordered_Sets
(Natural);
type Partition is array (Positive range <>) of Number_Sets.Set;
function "<" (Left, Right : Partition) return Boolean;
package Partition_Sets is new Ada.Containers.Indefinite_Ordered_Sets
(Partition);
function Create_Partitions (Args : Arguments) return Partition_Sets.Set;
end Partitions;
partitions.adb:
package body Partitions is
-- compare number sets (not provided)
function "<" (Left, Right : Number_Sets.Set) return Boolean is
use type Ada.Containers.Count_Type;
use Number_Sets;
Left_Pos : Cursor := Left.First;
Right_Pos : Cursor := Right.First;
begin
-- compare each element, until one or both lists finishes
while Left_Pos /= No_Element and then Right_Pos /= No_Element loop
-- compare elements
if Element (Left_Pos) < Element (Right_Pos) then
return True;
elsif Element (Left_Pos) > Element (Right_Pos) then
return False;
end if;
-- increase iterator
Next (Left_Pos);
Next (Right_Pos);
end loop;
-- Right is longer
if Right_Pos /= No_Element then
return True;
else
-- Left is longer, or Left and Right are identical.
return False;
end if;
end "<";
-- compare two Partitions
function "<" (Left, Right : Partition) return Boolean is
use type Ada.Containers.Count_Type;
use type Number_Sets.Set;
begin
-- check length
if Left'Length < Right'Length then
return True;
elsif Left'Length > Right'Length then
return False;
end if;
-- same length
if Left'Length > 0 then
for I in Left'Range loop
if Left (I) < Right (I) then
return True;
elsif Left (I) /= Right (I) then
return False;
end if;
end loop;
end if;
-- length = 0 are always smallest
return False;
end "<";
-- create partitions (as the task describes)
function Create_Partitions (Args : Arguments) return Partition_Sets.Set is
-- permutations needed
type Permutation is array (Positive range <>) of Natural;
-- exception to be thrown after last permutation reached
No_More_Permutations : exception;
-- get initial permutation (ordered small->big)
function Initial_Permutation (Max : Natural) return Permutation is
Result : Permutation (1 .. Max);
begin
for I in 1 .. Max loop
Result (I) := I;
end loop;
return Result;
end Initial_Permutation;
-- get next permutation
function Next_Permutation (Current : Permutation) return Permutation is
K : Natural := Current'Last - 1;
L : Positive := Current'Last;
Result : Permutation := Current;
begin
-- 1. Find the largest index k such that a[k] < a[k + 1].
while K /= 0 and then Current (K) > Current (K + 1) loop
K := K - 1;
end loop;
-- If no such index exists, the permutation is the last permutation.
if K = 0 then
raise No_More_Permutations;
end if;
-- 2. Find the largest index l such that a[k] < a[l].
-- Since k + 1 is such an index, l is well defined
-- and satisfies k < l.
while Current (K) > Current (L) loop
L := L - 1;
end loop;
-- 3. Swap a[k] with a[l].
Result (K) := Current (L);
Result (L) := Current (K);
-- 4. Reverse the sequence from a[k + 1] up to and including the
-- final element a[n].
for I in 1 .. (Result'Last - K) / 2 loop
declare
Temp : constant Natural := Result (K + I);
begin
Result (K + I) := Result (Result'Last - I + 1);
Result (Result'Last - I + 1) := Temp;
end;
end loop;
return Result;
end Next_Permutation;
Result : Partition_Sets.Set;
Sum : Natural := 0;
begin
-- get number of elements
for I in Args'Range loop
Sum := Sum + Args (I);
end loop;
declare
-- initial permutation
Current_Permutation : Permutation := Initial_Permutation (Sum);
begin
-- loop through permutations
loop
-- create Partition (same count of Number_Sets.Set as Args)
declare
Item : Natural := Current_Permutation'First;
Current_Partition : Partition (Args'Range);
begin
-- loop each partition
for I in Args'Range loop
-- fill in the number of elements requested
for J in 1 .. Args (I) loop
Current_Partition (I).Insert
(New_Item => Current_Permutation (Item));
Item := Item + 1;
end loop;
end loop;
-- insert partition into result set
Result.Insert (New_Item => Current_Partition);
exception
when Constraint_Error =>
-- partition was already inserted, ignore it.
-- this happens when one of the args > 1.
null;
end;
-- create next permutation
Current_Permutation := Next_Permutation (Current_Permutation);
end loop;
exception
when No_More_Permutations =>
-- no more permutations, we are finished
null;
end;
return Result;
end Create_Partitions;
end Partitions;
example main.adb:
with Ada.Text_IO;
with Partitions;
procedure Main is
package Natural_IO is new Ada.Text_IO.Integer_IO (Natural);
Example_Partitions : Partitions.Partition_Sets.Set;
begin
Ada.Text_IO.Put_Line ("Partitions for (2, 0, 2):");
-- create partition
Example_Partitions := Partitions.Create_Partitions (Args => (2, 0, 2));
-- pretty print the result
declare
use type Partitions.Partition_Sets.Cursor;
Position : Partitions.Partition_Sets.Cursor := Example_Partitions.First;
begin
Ada.Text_IO.Put ('{');
while Position /= Partitions.Partition_Sets.No_Element loop
if Position /= Example_Partitions.First then
Ada.Text_IO.Put (' ');
end if;
declare
Current_Partition : constant Partitions.Partition :=
Partitions.Partition_Sets.Element (Position);
begin
Ada.Text_IO.Put ('(');
for I in Current_Partition'Range loop
Ada.Text_IO.Put ('{');
declare
use type Partitions.Number_Sets.Cursor;
Current_Number : Partitions.Number_Sets.Cursor :=
Current_Partition (I).First;
begin
while Current_Number /= Partitions.Number_Sets.No_Element
loop
Natural_IO.Put
(Item =>
Partitions.Number_Sets.Element (Current_Number),
Width => 1);
Partitions.Number_Sets.Next (Current_Number);
if Current_Number /=
Partitions.Number_Sets.No_Element then
Ada.Text_IO.Put (',');
end if;
end loop;
end;
Ada.Text_IO.Put ('}');
if I /= Current_Partition'Last then
Ada.Text_IO.Put (", ");
end if;
end loop;
end;
Ada.Text_IO.Put (')');
Partitions.Partition_Sets.Next (Position);
if Position /= Partitions.Partition_Sets.No_Element then
Ada.Text_IO.Put (',');
Ada.Text_IO.New_Line;
end if;
end loop;
Ada.Text_IO.Put ('}');
Ada.Text_IO.New_Line;
end;
end Main;
Output:
Partitions for (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})}
BBC BASIC
DIM list1%(2) : list1%() = 2, 0, 2
PRINT "partitions(2,0,2):"
PRINT FNpartitions(list1%())
DIM list2%(2) : list2%() = 1, 1, 1
PRINT "partitions(1,1,1):"
PRINT FNpartitions(list2%())
DIM list3%(3) : list3%() = 1, 2, 0, 1
PRINT "partitions(1,2,0,1):"
PRINT FNpartitions(list3%())
END
DEF FNpartitions(list%())
LOCAL i%, j%, n%, p%, o$, x%()
n% = DIM(list%(),1)
DIM x%(SUM(list%())-1)
FOR i% = 0 TO n%
IF list%(i%) THEN
FOR j% = 1 TO list%(i%)
x%(p%) = i%
p% += 1
NEXT
ENDIF
NEXT i%
REPEAT
FOR i% = 0 TO n%
o$ += " ( "
FOR j% = 0 TO DIM(x%(),1)
IF x%(j%) = i% o$ += STR$(j%+1) + " "
NEXT
o$ += ")"
NEXT i%
o$ += CHR$13 + CHR$10
UNTIL NOT FNperm(x%())
= o$
DEF FNperm(x%())
LOCAL i%, j%
FOR i% = DIM(x%(),1)-1 TO 0 STEP -1
IF x%(i%) < x%(i%+1) EXIT FOR
NEXT
IF i% < 0 THEN = FALSE
j% = DIM(x%(),1)
WHILE x%(j%) <= x%(i%) j% -= 1 : ENDWHILE
SWAP x%(i%), x%(j%)
i% += 1
j% = DIM(x%(),1)
WHILE i% < j%
SWAP x%(i%), x%(j%)
i% += 1
j% -= 1
ENDWHILE
= TRUE
Output:
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 ) ( 3 ) ( 1 ) ( 2 ) ( 2 ) ( 3 ) ( 1 ) ( 3 ) ( 2 ) ( 1 ) partitions(1,2,0,1): ( 1 ) ( 2 3 ) ( ) ( 4 ) ( 1 ) ( 2 4 ) ( ) ( 3 ) ( 1 ) ( 3 4 ) ( ) ( 2 ) ( 2 ) ( 1 3 ) ( ) ( 4 ) ( 2 ) ( 1 4 ) ( ) ( 3 ) ( 3 ) ( 1 2 ) ( ) ( 4 ) ( 4 ) ( 1 2 ) ( ) ( 3 ) ( 3 ) ( 1 4 ) ( ) ( 2 ) ( 4 ) ( 1 3 ) ( ) ( 2 ) ( 2 ) ( 3 4 ) ( ) ( 1 ) ( 3 ) ( 2 4 ) ( ) ( 1 ) ( 4 ) ( 2 3 ) ( ) ( 1 )
C
Watch out for blank for loops. Iterative permutation generation is described at [[2]]; code messness is purely mine.
#include <stdio.h>
int next_perm(int size, int * nums)
{
int *l, *k, tmp;
for (k = nums + size - 2; k >= nums && k[0] >= k[1]; k--) {};
if (k < nums) return 0;
for (l = nums + size - 1; *l <= *k; l--) {};
tmp = *k; *k = *l; *l = tmp;
for (l = nums + size - 1, k++; k < l; k++, l--) {
tmp = *k; *k = *l; *l = tmp;
}
return 1;
}
void make_part(int n, int * sizes)
{
int x[1024], i, j, *ptr, len = 0;
for (ptr = x, i = 0; i < n; i++)
for (j = 0, len += sizes[i]; j < sizes[i]; j++, *(ptr++) = i);
do {
for (i = 0; i < n; i++) {
printf(" { ");
for (j = 0; j < len; j++)
if (x[j] == i) printf("%d ", j);
printf("}");
}
printf("\n");
} while (next_perm(len, x));
}
int main()
{
int s1[] = {2, 0, 2};
int s2[] = {1, 2, 3, 4};
printf("Part 2 0 2:\n");
make_part(3, s1);
printf("\nPart 1 2 3 4:\n");
make_part(4, s2);
return 1;
}
Output:
Part 2 0 2: { 0 1 } { } { 2 3 } { 0 2 } { } { 1 3 } { 0 3 } { } { 1 2 } { 1 2 } { } { 0 3 } { 1 3 } { } { 0 2 } { 2 3 } { } { 0 1 } Part 1 2 3 4: { 0 } { 1 2 } { 3 4 5 } { 6 7 8 9 } { 0 } { 1 2 } { 3 4 6 } { 5 7 8 9 } { 0 } { 1 2 } { 3 4 7 } { 5 6 8 9 } { 0 } { 1 2 } { 3 4 8 } { 5 6 7 9 } { 0 } { 1 2 } { 3 4 9 } { 5 6 7 8 } { 0 } { 1 2 } { 3 5 6 } { 4 7 8 9 } ....
With bitfield:
#include <stdio.h>
typedef unsigned int uint;
int parts[] = {2, 1, 2};
#define n_parts sizeof(parts)/sizeof(parts[0])
int bits[n_parts];
void show_part(uint x)
{
uint i;
putchar('{');
for (i = 0; (1 << i) <= x; i ++)
if (x & (1 << i)) printf(" %d", i + 1);
printf("%s", " } ");
}
void gen_bits(uint mask, uint all, uint res, int n, int pid)
{
uint i;
while (!n) {
bits[pid++] = res;
if (pid == n_parts) {
for (i = 0; i < n_parts; i++)
show_part(bits[i]);
putchar('\n');
return;
}
mask = all &= ~res;
res = 0;
n = parts[pid];
}
while (mask) {
mask &= ~(i = mask & -(int)mask);
gen_bits(mask, all, res | i, n - 1, pid);
}
}
int main(void)
{
uint i, m;
for (m = 1, i = 0; i < n_parts; i++)
m <<= parts[i];
m--;
gen_bits(m, m, 0, parts[0], 0);
return 0;
}
C#
using System;
using System.Linq;
using System.Collections.Generic;
public static class OrderedPartitions
{
public static void Main() {
var input = new [] { new[] { 0, 0, 0, 0, 0 }, new[] { 2, 0, 2 }, new[] { 1, 1, 1 } };
foreach (int[] sizes in input) {
foreach (var partition in Partitions(sizes)) {
Console.WriteLine(partition.Select(set => set.Delimit(", ").Encase('{','}')).Delimit(", ").Encase('(', ')'));
}
Console.WriteLine();
}
}
static IEnumerable<IEnumerable<int[]>> Partitions(params int[] sizes) {
var enumerators = new IEnumerator<int[]>[sizes.Length];
var unused = Enumerable.Range(1, sizes.Sum()).ToSortedSet();
var arrays = sizes.Select(size => new int[size]).ToArray();
for (int s = 0; s >= 0; ) {
if (s == sizes.Length) {
yield return arrays;
s--;
}
if (enumerators[s] == null) {
enumerators[s] = Combinations(sizes[s], unused.ToArray()).GetEnumerator();
} else {
unused.UnionWith(arrays[s]);
}
if (enumerators[s].MoveNext()) {
enumerators[s].Current.CopyTo(arrays[s], 0);
unused.ExceptWith(arrays[s]);
s++;
} else {
enumerators[s] = null;
s--;
}
}
}
static IEnumerable<T[]> Combinations<T>(int count, params T[] array) {
T[] result = new T[count];
foreach (int pattern in BitPatterns(array.Length - count, array.Length)) {
for (int b = 1 << (array.Length - 1), i = 0, r = 0; b > 0; b >>= 1, i++) {
if ((pattern & b) == 0) result[r++] = array[i];
}
yield return result;
}
}
static IEnumerable<int> BitPatterns(int ones, int length) {
int initial = (1 << ones) - 1;
int blockMask = (1 << length) - 1;
for (int v = initial; v >= initial; ) {
yield return v;
if (v == 0) break;
int w = (v | (v - 1)) + 1;
w |= (((w & -w) / (v & -v)) >> 1) - 1;
v = w & blockMask;
}
}
static string Delimit<T>(this IEnumerable<T> source, string separator) => string.Join(separator, source);
static string Encase(this string s, char start, char end) => start + s + end;
}
- Output:
({}, {}, {}, {}, {}) ({1, 2}, {}, {3, 4}) ({1, 3}, {}, {2, 4}) ({1, 4}, {}, {2, 3}) ({2, 3}, {}, {1, 4}) ({2, 4}, {}, {1, 3}) ({3, 4}, {}, {1, 2}) ({1}, {2}, {3}) ({1}, {3}, {2}) ({2}, {1}, {3}) ({2}, {3}, {1}) ({3}, {1}, {2}) ({3}, {2}, {1})
C++
#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>
void partitions(std::vector<size_t> args) {
size_t sum = std::accumulate(std::begin(args), std::end(args), 0);
std::vector<size_t> nums(sum);
std::iota(std::begin(nums), std::end(nums), 1);
do {
size_t total_index = 0;
std::vector<std::vector<size_t>> parts;
for (const auto& a : args) {
std::vector<size_t> part;
bool cont = true;
for (size_t j = 0; j < a; ++j) {
for (const auto& p : part) {
if (nums[total_index] < p) {
cont = false;
break;
}
}
if (cont) {
part.push_back(nums[total_index]);
++total_index;
}
}
if (part.size() != a) {
break;
}
parts.push_back(part);
}
if (parts.size() == args.size()) {
std::cout << "(";
for (const auto& p : parts) {
std::cout << "{ ";
for (const auto& e : p) {
std::cout << e << " ";
}
std::cout << "},";
}
std::cout << ")," << std::endl;
}
} while (std::next_permutation(std::begin(nums), std::end(nums)));
}
int main() {
std::vector<size_t> args = { 2, 0, 2 };
partitions(args);
std::cin.ignore();
std::cin.get();
return 0;
}
- Output:
({ 1 2 },{ },{ 3 4 },), ({ 1 3 },{ },{ 2 4 },), ({ 1 4 },{ },{ 2 3 },), ({ 2 3 },{ },{ 1 4 },), ({ 2 4 },{ },{ 1 3 },), ({ 3 4 },{ },{ 1 2 },),
Common Lisp
Lexicographical generation of partitions. Pros: can handle duplicate elements; probably faster than some methods generating all permutations then throwing bad ones out. Cons: clunky (which is probably my fault).
(defun fill-part (x i j l)
(let ((e (elt x i)))
(loop for c in l do
(loop while (>= j (length e)) do
(setf j 0 e (elt x (incf i))))
(setf (elt e j) c)
(incf j))))
;;; take a list of lists and return next partitioning
;;; it's caller's responsibility to ensure each sublist is sorted
(defun next-part (list cmp)
(let* ((l (coerce list 'vector))
(i (1- (length l)))
(e (elt l i)))
(loop while (<= 0 (decf i)) do
;; e holds all the right most elements
(let ((p (elt l i)) (q (car (last e))))
;; find the right-most list that has an element that's smaller
;; than _something_ in later lists
(when (and p (funcall cmp (first p) q))
;; find largest element that can be increased
(loop for j from (1- (length p)) downto 0 do
(when (funcall cmp (elt p j) q)
;; find the smallest element that's larger than
;; that largest
(loop for x from 0 to (1- (length e)) do
(when (funcall cmp (elt p j) (elt e x))
(rotatef (elt p j) (elt e x))
(loop while (< (incf j) (length p)) do
(setf (elt p j) (elt e (incf x))
(elt e x) nil))
(fill-part l i j (remove nil e))
(return-from next-part l))))
(setf e (append e (list (elt p j))))))
(setf e (append e p))))))
(let ((a '#((1 2) () (3 4))))
(loop while a do
(format t "~a~%" a)
(setf a (next-part a #'<))))
(write-line "with dupe elements:")
(let ((a '#((a c) (c c d))))
(loop while a do
(format t "~a~%" a)
(setf a (next-part a #'string<))))
output
#((1 2) NIL (3 4)) #((1 3) NIL (2 4)) #((1 4) NIL (2 3)) #((2 3) NIL (1 4)) #((2 4) NIL (1 3)) #((3 4) NIL (1 2)) with dupe elements: #((A C) (C C D)) #((A D) (C C C)) #((C C) (A C D)) #((C D) (A C C))
D
Using module of the third D entry of the Combination Task.
import std.stdio, std.algorithm, std.range, std.array, std.conv,
combinations3;
alias iRNG = int[];
iRNG[][] orderPart(iRNG blockSize...) {
iRNG tot = iota(1, 1 + blockSize.sum).array;
iRNG[][] p(iRNG s, in iRNG b) {
if (b.empty)
return [[]];
iRNG[][] res;
foreach (c; s.combinations(b[0]))
foreach (r; p(setDifference(s, c).array, b.dropOne))
res ~= c.dup ~ r;
return res;
}
return p(tot, blockSize);
}
void main(in string[] args) {
auto b = args.length > 1 ? args.dropOne.to!(int[]) : [2, 0, 2];
writefln("%(%s\n%)", b.orderPart);
}
- Output:
[[1, 2], [], [3, 4]] [[1, 3], [], [2, 4]] [[1, 4], [], [2, 3]] [[2, 3], [], [1, 4]] [[2, 4], [], [1, 3]] [[3, 4], [], [1, 2]]
Alternative Version
import core.stdc.stdio;
void genBits(size_t N)(ref uint[N] bits, in ref uint[N] parts,
uint mask, uint all, uint res, uint n, uint pid)
nothrow @nogc {
static void showPart(in uint x) nothrow @nogc {
'['.putchar;
for (uint i = 0; (1 << i) <= x; i++)
if (x & (1 << i))
printf("%d ", i + 1);
']'.putchar;
}
while (!n) {
bits[pid] = res;
pid++;
if (pid == N) {
foreach (immutable b; bits)
showPart(b);
'\n'.putchar;
return;
}
all &= ~res;
mask = all;
res = 0;
n = parts[pid];
}
while (mask) {
immutable uint i = mask & -int(mask);
mask &= ~i;
genBits(bits, parts, mask, all, res | i, n - 1, pid);
}
}
void main() nothrow @nogc {
immutable uint[3] parts = [2, 0, 2];
uint m = 1;
foreach (immutable p; parts)
m <<= p;
uint[parts.length] bits;
genBits(bits, parts, m - 1, m - 1, 0, parts[0], 0);
}
- Output:
[1 2 ][][3 4 ] [1 3 ][][2 4 ] [1 4 ][][2 3 ] [2 3 ][][1 4 ] [2 4 ][][1 3 ] [3 4 ][][1 2 ]
EchoLisp
(lib 'list) ;; (combinations L k)
;; add a combination to each partition in ps
(define (pproduct c ps) (for/list ((x ps)) (cons c x)))
;; apply to any type of set S
;; ns is list of cardinals for each partition
;; for all combinations Ci of n objects from S
;; set S <- LS minus Ci , set n <- next n , and recurse
(define (_partitions S ns )
(cond
([empty? (rest ns)] (list (combinations S (first ns))))
(else
(for/fold (parts null)
([c (combinations S (first ns))])
(append
parts
(pproduct c (_partitions (set-substract S c) (rest ns))))))))
;; task : S = ( 0 , 1 ... n-1) args = ns
(define (partitions . args)
(for-each
writeln
(_partitions (range 1 (1+ (apply + args))) args )))
- Output:
(partitions 1 1 1) ({ 1 } { 2 } { 3 }) ({ 1 } { 3 } { 2 }) ({ 2 } { 1 } { 3 }) ({ 2 } { 3 } { 1 }) ({ 3 } { 1 } { 2 }) ({ 3 } { 2 } { 1 }) (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 }) (for-each writeln (_partitions (make-set '(b a d c )) '(1 2 1))) ({ a } { b c } { d }) ({ a } { b d } { c }) ({ a } { c d } { b }) ({ b } { a c } { d }) ({ b } { a d } { c }) ({ b } { c d } { a }) ({ c } { a b } { d }) ({ c } { a d } { b }) ({ c } { b d } { a }) ({ d } { a b } { c }) ({ d } { a c } { b }) ({ d } { b c } { a })
Elixir
Brute force approach:
defmodule Ordered do
def partition([]), do: [[]]
def partition(mask) do
sum = Enum.sum(mask)
if sum == 0 do
[Enum.map(mask, fn _ -> [] end)]
else
Enum.to_list(1..sum)
|> permute
|> Enum.reduce([], fn perm,acc ->
{_, part} = Enum.reduce(mask, {perm,[]}, fn num,{pm,a} ->
{p, rest} = Enum.split(pm, num)
{rest, [Enum.sort(p) | a]}
end)
[Enum.reverse(part) | acc]
end)
|> Enum.uniq
end
end
defp permute([]), do: [[]]
defp permute(list), do: for x <- list, y <- permute(list -- [x]), do: [x|y]
end
Enum.each([[],[0,0,0],[1,1,1],[2,0,2]], fn test_case ->
IO.puts "\npartitions #{inspect test_case}:"
Enum.each(Ordered.partition(test_case), fn part ->
IO.inspect part
end)
end)
- Output:
partitions []: [] partitions [0, 0, 0]: [[], [], []] partitions [1, 1, 1]: [[3], [2], [1]] [[3], [1], [2]] [[2], [3], [1]] [[2], [1], [3]] [[1], [3], [2]] [[1], [2], [3]] partitions [2, 0, 2]: [[3, 4], [], [1, 2]] [[2, 4], [], [1, 3]] [[1, 4], [], [2, 3]] [[2, 3], [], [1, 4]] [[1, 3], [], [2, 4]] [[1, 2], [], [3, 4]]
FreeBASIC
Function Perm(x() As Integer) As Boolean
Dim As Integer i, j
For i = Ubound(x,1)-1 To 0 Step -1
If x(i) < x(i+1) Then Exit For
Next i
If i < 0 Then Return False
j = Ubound(x,1)
While x(j) <= x(i)
j -= 1
Wend
Swap x(i), x(j)
i += 1
j = Ubound(x,1)
While i < j
Swap x(i), x(j)
i += 1
j -= 1
Wend
Return True
End Function
Function Particiones(list() As Integer) As String
Dim As Integer i, j, n, p ', x()
Dim As String oSS = ""
n = Ubound(list)
Dim As Integer x(n)
For i = 0 To n
If list(i) Then
For j = 1 To list(i)
x(p) = i
p += 1
Next j
End If
Next i
Do
For i = 0 To n
oSS += " ( "
For j = 0 To Ubound(x,1)
If x(j) = i Then oSS += Str(j+1) + " "
Next j
oSS += ")"
Next i
oSS += Chr(13) + Chr(10)
Loop Until Not Perm(x())
Return oSS
End Function
Dim list2(2) As Integer = {1, 1, 1}
Print "Particiones(1, 1, 1):"
Print Particiones(list2())
Dim list3(3) As Integer = {1, 2, 0, 1}
Print !"\nParticiones(1, 2, 0, 1):"
Print Particiones(list3())
Sleep
- Output:
Particiones(1, 1, 1): ( 1 ) ( 2 ) ( 3 ) ( 1 ) ( 3 ) ( 2 ) ( 2 ) ( 1 ) ( 3 ) ( 3 ) ( 1 ) ( 2 ) ( 2 ) ( 3 ) ( 1 ) ( 3 ) ( 2 ) ( 1 ) Particiones(1, 2, 0, 1): ( 1 ) ( 2 3 ) ( ) ( 4 ) ( 1 ) ( 2 4 ) ( ) ( 3 ) ( 1 ) ( 3 4 ) ( ) ( 2 ) ( 2 ) ( 1 3 ) ( ) ( 4 ) ( 2 ) ( 1 4 ) ( ) ( 3 ) ( 3 ) ( 1 2 ) ( ) ( 4 ) ( 4 ) ( 1 2 ) ( ) ( 3 ) ( 3 ) ( 1 4 ) ( ) ( 2 ) ( 4 ) ( 1 3 ) ( ) ( 2 ) ( 2 ) ( 3 4 ) ( ) ( 1 ) ( 3 ) ( 2 4 ) ( ) ( 1 ) ( 4 ) ( 2 3 ) ( ) ( 1 )
GAP
FixedPartitions := function(arg)
local aux;
aux := function(i, u)
local r, v, w;
if i = Size(arg) then
return [[u]];
else
r := [ ];
for v in Combinations(u, arg[i]) do
for w in aux(i + 1, Difference(u, v)) do
Add(r, Concatenation([v], w));
od;
od;
return r;
fi;
end;
return aux(1, [1 .. Sum(arg)]);
end;
FixedPartitions(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 ] ] ]
FixedPartitions(1, 1, 1);
# [ [ [ 1 ], [ 2 ], [ 3 ] ], [ [ 1 ], [ 3 ], [ 2 ] ], [ [ 2 ], [ 1 ], [ 3 ] ],
# [ [ 2 ], [ 3 ], [ 1 ] ], [ [ 3 ], [ 1 ], [ 2 ] ], [ [ 3 ], [ 2 ], [ 1 ] ] ]
Go
package main
import (
"fmt"
"os"
"strconv"
)
func gen_part(n, res []int, pos int) {
if pos == len(res) {
x := make([][]int, len(n))
for i, c := range res {
x[c] = append(x[c], i+1)
}
fmt.Println(x)
return
}
for i := range n {
if n[i] == 0 {
continue
}
n[i], res[pos] = n[i]-1, i
gen_part(n, res, pos+1)
n[i]++
}
}
func ordered_part(n_parts []int) {
fmt.Println("Ordered", n_parts)
sum := 0
for _, c := range n_parts {
sum += c
}
gen_part(n_parts, make([]int, sum), 0)
}
func main() {
if len(os.Args) < 2 {
ordered_part([]int{2, 0, 2})
return
}
n := make([]int, len(os.Args)-1)
var err error
for i, a := range os.Args[1:] {
n[i], err = strconv.Atoi(a)
if err != nil {
fmt.Println(err)
return
}
if n[i] < 0 {
fmt.Println("negative partition size not meaningful")
return
}
}
ordered_part(n)
}
Example command line use:
> op Ordered [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]] > op 1 1 1 Ordered [1 1 1] [[1] [2] [3]] [[1] [3] [2]] [[2] [1] [3]] [[3] [1] [2]] [[2] [3] [1]] [[3] [2] [1]] > op 1 2 3 4 | head Ordered [1 2 3 4] [[1] [2 3] [4 5 6] [7 8 9 10]] [[1] [2 3] [4 5 7] [6 8 9 10]] [[1] [2 3] [4 5 8] [6 7 9 10]] [[1] [2 3] [4 5 9] [6 7 8 10]] [[1] [2 3] [4 5 10] [6 7 8 9]] [[1] [2 3] [4 6 7] [5 8 9 10]] [[1] [2 3] [4 6 8] [5 7 9 10]] [[1] [2 3] [4 6 9] [5 7 8 10]] [[1] [2 3] [4 6 10] [5 7 8 9]]
Groovy
Solution:
def partitions = { int... sizes ->
int n = (sizes as List).sum()
def perms = n == 0 ? [[]] : (1..n).permutations()
Set parts = perms.collect { p -> sizes.collect { s -> (0..<s).collect { p.pop() } as Set } }
parts.sort{ a, b ->
if (!a) return 0
def comp = [a,b].transpose().find { aa, bb -> aa != bb }
if (!comp) return 0
def recomp = comp.collect{ it as List }.transpose().find { aa, bb -> aa != bb }
if (!recomp) return 0
return recomp[0] <=> recomp[1]
}
}
Test:
partitions(2, 0, 2).each {
println it
}
Output:
[[1, 2], [], [3, 4]] [[1, 3], [], [2, 4]] [[1, 4], [], [2, 3]] [[2, 3], [], [1, 4]] [[2, 4], [], [1, 3]] [[3, 4], [], [1, 2]]
Haskell
import Data.List ((\\))
comb :: Int -> [a] -> [[a]]
comb 0 _ = [[]]
comb _ [] = []
comb k (x:xs) = map (x:) (comb (k-1) xs) ++ comb k xs
partitions :: [Int] -> [[[Int]]]
partitions xs = p [1..sum xs] xs
where p _ [] = [[]]
p xs (k:ks) = [ cs:rs | cs <- comb k xs, rs <- p (xs \\ cs) ks ]
main = print $ partitions [2,0,2]
An alternative where \\
is not needed anymore because comb
now not only
keeps the chosen elements but also the not chosen elements together in a tuple.
comb :: Int -> [a] -> [([a],[a])]
comb 0 xs = [([],xs)]
comb _ [] = []
comb k (x:xs) = [ (x:cs,zs) | (cs,zs) <- comb (k-1) xs ] ++
[ (cs,x:zs) | (cs,zs) <- comb k xs ]
partitions :: [Int] -> [[[Int]]]
partitions xs = p [1..sum xs] xs
where p _ [] = [[]]
p xs (k:ks) = [ cs:rs | (cs,zs) <- comb k xs, rs <- p zs ks ]
main = print $ partitions [2,0,2]
Output:
[[[1,2],[],[3,4]],[[1,3],[],[2,4]],[[1,4],[],[2,3]],[[2,3],[],[1,4]],[[2,4],[],[1,3]],[[3,4],[],[1,2]]]
Faster by keeping track of the length of lists:
import Data.Bifunctor (first, second)
-- choose m out of n items, return tuple of chosen and the rest
choose :: [Int] -> Int -> Int -> [([Int], [Int])]
choose [] _ _ = [([], [])]
choose aa _ 0 = [([], aa)]
choose aa@(a : as) n m
| n == m = [(aa, [])]
| otherwise =
(first (a :) <$> choose as (n - 1) (m - 1))
<> (second (a :) <$> choose as (n - 1) m)
partitions :: [Int] -> [[[Int]]]
partitions x = combos [1 .. n] n x
where
n = sum x
combos _ _ [] = [[]]
combos s n (x : xs) =
[ l : r
| (l, rest) <- choose s n x,
r <- combos rest (n - x) xs
]
main :: IO ()
main = mapM_ print $ partitions [5, 5, 5]
J
Brute force approach:
require'stats'
partitions=: ([,] {L:0 (i.@#@, -. [)&;)/"1@>@,@{@({@comb&.> +/\.)
First we compute each of the corresponding combinations for each argument, then we form their cartesian product and then we restructure each of those products by: eliminating from values populating the the larger set combinations the combinations already picked from the smaller set and using the combinations from the larger set to index into the options which remain.
Examples:
partitions 2 0 2
┌───┬┬───┐
│0 1││2 3│
├───┼┼───┤
│0 2││1 3│
├───┼┼───┤
│0 3││1 2│
├───┼┼───┤
│1 2││0 3│
├───┼┼───┤
│1 3││0 2│
├───┼┼───┤
│2 3││0 1│
└───┴┴───┘
partitions 1 1 1
┌─┬─┬─┐
│0│1│2│
├─┼─┼─┤
│0│2│1│
├─┼─┼─┤
│1│0│2│
├─┼─┼─┤
│1│2│0│
├─┼─┼─┤
│2│0│1│
├─┼─┼─┤
│2│1│0│
└─┴─┴─┘
#partitions 2 3 5
2520
#partitions 5 7 11
|out of memory: partitions
| # partitions 5 7 11
*/ (! +/\.)5 7 11
1070845776
#partitions 3 5 7
360360
*/ (! +/\.)3 5 7
360360
Here's some intermediate results for that first example:
+/\. 2 0 2
4 2 2
({@comb&.> +/\.) 2 0 2
┌─────────────────────────┬──┬─────┐
│┌───┬───┬───┬───┬───┬───┐│┌┐│┌───┐│
││0 1│0 2│0 3│1 2│1 3│2 3││││││0 1││
│└───┴───┴───┴───┴───┴───┘│└┘│└───┘│
└─────────────────────────┴──┴─────┘
>@,@{@({@comb&.> +/\.) 2 0 2
┌───┬┬───┐
│0 1││0 1│
├───┼┼───┤
│0 2││0 1│
├───┼┼───┤
│0 3││0 1│
├───┼┼───┤
│1 2││0 1│
├───┼┼───┤
│1 3││0 1│
├───┼┼───┤
│2 3││0 1│
└───┴┴───┘
In other words, initially we just work with relevant combinations (working from right to left). To understand the step which produces the final result, consider this next sequence of results (J's /
operator works from right to left, as that's the pattern established by assignment operations, and because that has some interesting and useful mathematical properties):
([,] {L:0 (i.@#@, -. [)&;)/0 1;0 1
┌───┬───┐
│0 1│2 3│
└───┴───┘
([,] {L:0 (i.@#@, -. [)&;)/0 1;0 1;0 1
┌───┬───┬───┐
│0 1│2 3│4 5│
└───┴───┴───┘
([,] {L:0 (i.@#@, -. [)&;)/0 1;0 1;0 1;0 1
┌───┬───┬───┬───┐
│0 1│2 3│4 5│6 7│
└───┴───┴───┴───┘
Breaking down that last example:
(<0 1) ([,] {L:0 (i.@#@, -. [)&;)0 1;2 3;4 5
┌───┬───┬───┬───┐
│0 1│2 3│4 5│6 7│
└───┴───┴───┴───┘
Here, on the right hand side we form 0 1 0 1 2 3 4 5, count how many things are in it (8), form 0 1 2 3 4 5 6 7 from that and then remove 0 1 (the values in the left argument) leaving us with 2 3 4 5 6 7. Meanwhile, on the left side, keep our left argument intact and use the indices in the remaining boxes to select from the right argument. In theoretical terms this is not particularly efficient, but we are working with very short lists here (because otherwise we run out of memory for the result as a whole), so the actual cost is trivial. Also note that sequential loops tend to be faster than nested loops (though we do get the effect of a nested loop, here - and that was the theoretical inefficiency).
Java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public final class OrderedPartitions {
public static void main(String[] aArgs) {
List<Integer> sizes = ( aArgs == null || aArgs.length == 0 ) ?
List.of( 2, 0, 2 ) : Arrays.stream(aArgs).map( s -> Integer.valueOf(s) ).toList();
System.out.println("Partitions for " + sizes + ":");
final int total = sizes.stream().reduce(0, Integer::sum);
List<Integer> permutation = IntStream.rangeClosed(1, total).boxed().collect(Collectors.toList());
while ( hasNextPermutation(permutation) ) {
List<List<Integer>> partition = new ArrayList<List<Integer>>();
int sum = 0;
boolean isValid = true;
for ( int size : sizes ) {
List<Integer> subList = permutation.subList(sum, sum + size);
if ( ! isIncreasing(subList) ) {
isValid = false;
break;
}
partition.add(subList);
sum += size;
}
if ( isValid ) {
System.out.println(" ".repeat(4) + partition);
}
}
}
private static boolean hasNextPermutation(List<Integer> aPerm) {
final int lastIndex = aPerm.size() - 1;
int i = lastIndex;
while ( i > 0 && aPerm.get(i - 1) >= aPerm.get(i) ) {
i--;
}
if ( i <= 0 ) {
return false;
}
int j = lastIndex;
while ( aPerm.get(j) <= aPerm.get(i - 1) ) {
j--;
}
swap(aPerm, i - 1, j);
j = lastIndex;
while ( i < j ) {
swap(aPerm, i++, j--);
}
return true;
}
private static boolean isIncreasing(List<Integer> aList) {
return aList.stream().sorted().toList().equals(aList);
}
private static void swap(List<Integer> aList, int aOne, int aTwo) {
final int temp = aList.get(aOne);
aList.set(aOne, aList.get(aTwo));
aList.set(aTwo, temp);
}
}
- Output:
Partitions for [2, 0, 2]: [[1, 3], [], [2, 4]] [[1, 4], [], [2, 3]] [[2, 3], [], [1, 4]] [[2, 4], [], [1, 3]] [[3, 4], [], [1, 2]]
JavaScript
Functional (ES 5)
(function () {
'use strict';
// [n] -> [[[n]]]
function partitions(a1, a2, a3) {
var n = a1 + a2 + a3;
return combos(range(1, n), n, [a1, a2, a3]);
}
function combos(s, n, xxs) {
if (!xxs.length) return [[]];
var x = xxs[0],
xs = xxs.slice(1);
return mb( choose(s, n, x), function (l_rest) {
return mb( combos(l_rest[1], (n - x), xs), function (r) {
// monadic return/injection requires 1 additional
// layer of list nesting:
return [ [l_rest[0]].concat(r) ];
})});
}
function choose(aa, n, m) {
if (!m) return [[[], aa]];
var a = aa[0],
as = aa.slice(1);
return n === m ? (
[[aa, []]]
) : (
choose(as, n - 1, m - 1).map(function (xy) {
return [[a].concat(xy[0]), xy[1]];
}).concat(choose(as, n - 1, m).map(function (xy) {
return [xy[0], [a].concat(xy[1])];
}))
);
}
// GENERIC
// Monadic bind (chain) for lists
function mb(xs, f) {
return [].concat.apply([], xs.map(f));
}
// [m..n]
function range(m, n) {
return Array.apply(null, Array(n - m + 1)).map(function (x, i) {
return m + i;
});
}
// EXAMPLE
return partitions(2, 0, 2);
})();
- Output:
[[[1, 2], [], [3, 4]],
[[1, 3], [], [2, 4]],
[[1, 4], [], [2, 3]],
[[2, 3], [], [1, 4]],
[[2, 4], [], [1, 3]],
[[3, 4], [], [1, 2]]]
jq
The approach adopted here is similar to the #Python solution.
# Generate a stream of the distinct combinations of r items taken from the input array.
def combination(r):
if r > length or r < 0 then empty
elif r == length then .
else ( [.[0]] + (.[1:]|combination(r-1))),
( .[1:]|combination(r))
end;
# Input: a mask, that is, an array of lengths.
# Output: a stream of the distinct partitions defined by the mask.
def partition:
# partition an array of entities, s, according to a mask presented as input:
def p(s):
if length == 0 then []
else . as $mask
| (s | combination($mask[0])) as $c
| [$c] + ($mask[1:] | p(s - $c))
end;
. as $mask | p( [range(1; 1 + ($mask|add))] );
Example:
([],[0,0,0],[1,1,1],[2,0,2])
| . as $test_case
| "partitions \($test_case):" , ($test_case | partition), ""
- Output:
$ jq -M -n -c -r -f Ordered_partitions.jq
partitions []:
[]
partitions [0,0,0]:
[[],[],[]]
partitions [1,1,1]:
[[1],[2],[3]]
[[1],[3],[2]]
[[2],[1],[3]]
[[2],[3],[1]]
[[3],[1],[2]]
[[3],[2],[1]]
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]]
Julia
The method used, as seen in the function masked(), is to take a brute force permutation of size n = sum of partition, partition it using the provided mask, and then sort the inner lists in order to properly filter duplicates.
using Combinatorics
function masked(mask, lis)
combos = []
idx = 1
for step in mask
if(step < 1)
push!(combos, Array{Int,1}[])
else
push!(combos, sort(lis[idx:idx+step-1]))
idx += step
end
end
Array{Array{Int, 1}, 1}(combos)
end
function orderedpartitions(mask)
tostring(masklis) = replace("$masklis", r"Array{Int\d?\d?,1}|Int\d?\d?", "")
join([tostring(lis) for lis in unique([masked(mask, p)
for p in permutations(1:sum(mask))])], "\n")
end
println(orderedpartitions([2, 0, 2]))
println(orderedpartitions([1, 1, 1]))
- Output:
[[1, 2], [], [3, 4]] [[1, 3], [], [2, 4]] [[1, 4], [], [2, 3]] [[2, 3], [], [1, 4]] [[2, 4], [], [1, 3]] [[3, 4], [], [1, 2]] [[1], [2], [3]] [[1], [3], [2]] [[2], [1], [3]] [[2], [3], [1]] [[3], [1], [2]] [[3], [2], [1]]
Kotlin
// version 1.1.3
fun nextPerm(perm: IntArray): Boolean {
val size = perm.size
var k = -1
for (i in size - 2 downTo 0) {
if (perm[i] < perm[i + 1]) {
k = i
break
}
}
if (k == -1) return false // last permutation
for (l in size - 1 downTo k) {
if (perm[k] < perm[l]) {
val temp = perm[k]
perm[k] = perm[l]
perm[l] = temp
var m = k + 1
var n = size - 1
while (m < n) {
val temp2 = perm[m]
perm[m++] = perm[n]
perm[n--] = temp2
}
break
}
}
return true
}
fun List<Int>.isMonotonic(): Boolean {
for (i in 1 until this.size) {
if (this[i] < this[i - 1]) return false
}
return true
}
fun main(args: Array<String>) {
val sizes = args.map { it.toInt() }
println("Partitions for $sizes:\n[")
val totalSize = sizes.sum()
val perm = IntArray(totalSize) { it + 1 }
do {
val partition = mutableListOf<List<Int>>()
var sum = 0
var isValid = true
for (size in sizes) {
if (size == 0) {
partition.add(emptyList<Int>())
}
else if (size == 1) {
partition.add(listOf(perm[sum]))
}
else {
val sl = perm.slice(sum until sum + size)
if (!sl.isMonotonic()) {
isValid = false
break
}
partition.add(sl)
}
sum += size
}
if (isValid) println(" $partition")
}
while (nextPerm(perm))
println("]")
}
- Output:
Combined output of 3 separate runs with different command line parameters:
Partitions for [0, 0, 0]: [ [[], [], []] ] Partitions for [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 for [1, 1, 1]: [ [[1], [2], [3]] [[1], [3], [2]] [[2], [1], [3]] [[2], [3], [1]] [[3], [1], [2]] [[3], [2], [1]] ]
Lua
A pretty verbose solution. Maybe somebody can replace with something terser/better.
--- Create a list {1,...,n}.
local function range(n)
local res = {}
for i=1,n do
res[i] = i
end
return res
end
--- Return true if the element x is in t.
local function isin(t, x)
for _,x_t in ipairs(t) do
if x_t == x then return true end
end
return false
end
--- Return the sublist from index u to o (inclusive) from t.
local function slice(t, u, o)
local res = {}
for i=u,o do
res[#res+1] = t[i]
end
return res
end
--- Compute the sum of the elements in t.
-- Assume that t is a list of numbers.
local function sum(t)
local s = 0
for _,x in ipairs(t) do
s = s + x
end
return s
end
--- Generate all combinations of t of length k (optional, default is #t).
local function combinations(m, r)
local function combgen(m, n)
if n == 0 then coroutine.yield({}) end
for i=1,#m do
if n == 1 then coroutine.yield({m[i]})
else
for m0 in coroutine.wrap(function() combgen(slice(m, i+1, #m), n-1) end) do
coroutine.yield({m[i], unpack(m0)})
end
end
end
end
return coroutine.wrap(function() combgen(m, r) end)
end
--- Generate a list of partitions into fized-size blocks.
local function partitions(...)
local function helper(s, ...)
local args = {...}
if #args == 0 then return {% templatetag openvariable %}{% templatetag closevariable %} end
local res = {}
for c in combinations(s, args[1]) do
local s0 = {}
for _,x in ipairs(s) do if not isin(c, x) then s0[#s0+1] = x end end
for _,r in ipairs(helper(s0, unpack(slice(args, 2, #args)))) do
res[#res+1] = {{unpack(c)}, unpack(r)}
end
end
return res
end
return helper(range(sum({...})), ...)
end
-- Print the solution
io.write "["
local parts = partitions(2,0,2)
for i,tuple in ipairs(parts) do
io.write "("
for j,set in ipairs(tuple) do
io.write "{"
for k,element in ipairs(set) do
io.write(element)
if k ~= #set then io.write(", ") end
end
io.write "}"
if j ~= #tuple then io.write(", ") end
end
io.write ")"
if i ~= #parts then io.write(", ") end
end
io.write "]"
io.write "\n"
Output:
[({1, 2}, {}, {3, 4}), ({1, 3}, {}, {2, 4}), ({1, 4}, {}, {2, 3}), ({2, 3}, {}, {1, 4}), ({2, 4}, {}, {1, 3}), ({3, 4}, {}, {1, 2})]
Mathematica/Wolfram Language
This code works as follows: Permutations finds all permutations of the numbers ranging from 1 to n. w finds the required partition for an individual permutation. m finds partitions for all permutations. Sort and Union eliminate duplicates.
w[partitions_]:=Module[{s={},t=Total@partitions,list=partitions,k}, n=Length[list];
While[n>0,s=Join[s,{Take[t,(k=First[list])]}];t=Drop[t,k];list=Rest[list];n--]; s]
m[p_]:=(Sort/@#)&/@(w[#,p]&/@Permutations[Range@Total[p]])//Union
Usage Grid displays the output in a table.
Grid@m[{2, 0, 2}]
Grid@m[{1, 1, 1}]
Nim
We use the function nextPermutation
form standard module “algorithm” to build the permutations. The partition is built by using a list of slices. We keep only the partitions which contain sequences sorted by ascending order. Those partitions are yielded by an iterator.
The iterator may be called with a list of integer arguments or a single list of integers as argument. As requested, the arguments specifying the length of each sequence may also be provided on the command line.
import algorithm, math, sequtils, strutils
type Partition = seq[seq[int]]
func isIncreasing(s: seq[int]): bool =
## Return true if the sequence is sorted in increasing order.
var prev = 0
for val in s:
if prev >= val: return false
prev = val
result = true
iterator partitions(lengths: varargs[int]): Partition =
## Yield the partitions for lengths "lengths".
# Build the list of slices to use for partitionning.
var slices: seq[Slice[int]]
var delta = -1
var idx = 0
for length in lengths:
assert length >= 0, "lengths must not be negative."
inc delta, length
slices.add idx..delta
inc idx, length
# Build the partitions.
let n = sum(lengths)
var perm = toSeq(1..n)
while true:
block buildPartition:
var part: Partition
for slice in slices:
let s = perm[slice]
if not s.isIncreasing():
break buildPartition
part.add s
yield part
if not perm.nextPermutation():
break
func toString(part: Partition): string =
## Return the string representation of a partition.
result = "("
for s in part:
result.addSep(", ", 1)
result.add '{' & s.join(", ") & '}'
result.add ')'
when isMainModule:
import os
proc displayPermutations(lengths: varargs[int]) =
## Display the permutations.
echo "Ordered permutations for (", lengths.join(", "), "):"
for part in partitions(lengths):
echo part.toString
if paramCount() > 0:
var args: seq[int]
for param in commandLineParams():
try:
let val = param.parseInt()
if val < 0: raise newException(ValueError, "")
args.add val
except ValueError:
quit "Wrong parameter: " & param
displayPermutations(args)
else:
displayPermutations(2, 0, 2)
- Output:
$ ./ordered_partitions Ordered permutations for (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})
$ ./ordered_partitions 1 1 1 Ordered permutations for (1, 1, 1): ({1}, {2}, {3}) ({1}, {3}, {2}) ({2}, {1}, {3}) ({2}, {3}, {1}) ({3}, {1}, {2}) ({3}, {2}, {1})
Perl
Threaded Generator Method
This code demonstrates how to make something like Python's generators or Go's channels by using Thread::Queue. Granted, this is horribly inefficient, with constantly creating and killing threads and whatnot (every time a partition is created, a thread is made to produce the next partition, so thousands if not millions of threads live and die, depending on the problem size). But algorithms are often more naturally expressed in a coroutine manner -- for this example, "making a new partition" and "picking elements for a partition" can be done in separate recursions cleanly if so desired. It's about 20 times slower than the next code example, so there.
use strict;
use warnings;
use Thread 'async';
use Thread::Queue;
sub make_slices {
my ($n, @avail) = (shift, @{ +shift });
my ($q, @part, $gen);
$gen = sub {
my $pos = shift; # where to start in the list
if (@part == $n) {
# we accumulated enough for a partition, emit them and
# wait for main thread to pick them up, then back up
$q->enqueue(\@part, \@avail);
return;
}
# obviously not enough elements left to make a partition, back up
return if (@part + @avail < $n);
for my $i ($pos .. @avail - 1) { # try each in turn
push @part, splice @avail, $i, 1; # take one
$gen->($i); # go deeper
splice @avail, $i, 0, pop @part; # put it back
}
};
$q = Thread::Queue->new;
(async{ &$gen; # start the main work load
$q->enqueue(undef) # signal that there's no more data
})->detach; # let the thread clean up after itself, not my problem
return $q;
}
my $qa = make_slices(4, [ 0 .. 9 ]);
while (my $a = $qa->dequeue) {
my $qb = make_slices(2, $qa->dequeue);
while (my $b = $qb->dequeue) {
my $rb = $qb->dequeue;
print "@$a | @$b | @$rb\n";
}
}
Recursive solution
use strict;
use warnings;
use List::Util 1.33 qw(sum pairmap);
sub partition {
my @mask = @_;
my $last = sum @mask or return [map {[]} 0..$#mask];
return pairmap {
$b ? do {
local $mask[$a] = $b - 1;
map { push @{$_->[$a]}, $last; $_ }
partition(@mask);
} : ()
} %mask[0..$#mask];
}
# Input & Output handling:
print "(" . join(', ', map { "{".join(', ', @$_)."}" } @$_) . ")\n"
for partition( @ARGV ? @ARGV : (2, 0, 2) );
Example command-line use:
> ./ordered_partitions.pl ({3, 4}, {}, {1, 2}) ({2, 4}, {}, {1, 3}) ({1, 4}, {}, {2, 3}) ({2, 3}, {}, {1, 4}) ({1, 3}, {}, {2, 4}) ({1, 2}, {}, {3, 4}) > ./ordered_partitions.pl 1 1 1 ({3}, {2}, {1}) ({3}, {1}, {2}) ({2}, {3}, {1}) ({1}, {3}, {2}) ({2}, {1}, {3}) ({1}, {2}, {3})
The set of ordered partitions is not returned in lexicographical order itself; but it's supposed to be a set so that's hopefully okay. (One could sort the output before printing, but (unlike in Raku) Perl's built-in sort routine cannot meaningfully compare arrays without being passed a custom comparator to do that, which is a little messy and thus omitted here.)
Phix
Uses the permutes() routine [new in 1.0.2], which handles duplicate elements properly, so in the {1,2,3,4} test this only generates 12,600 combinations, whereas the previous version generated and obviously filtered and sorted all of the possible 3,628,800 full permutations, therefore it is now at least a couple of hundred times faster.
with javascript_semantics requires("1.0.2") function partitions(sequence s) integer l = length(s), N = sum(s) sequence pset = {}, -- eg s==={2,0,2} -> {1,1,3,3} rn = repeat(0,l) -- "" -> {{0,0},{},{0,0}} for i=1 to l do pset &= repeat(i,s[i]) rn[i] = repeat(0,s[i]) end for if pset={} then return {rn} end if -- edge case sequence res = permutes(pset,0) -- eg {1,1,3,3} means put 1,2 in [1], 3,4 in [3] -- .. {3,3,1,1} means put 1,2 in [3], 3,4 in [1] for i=1 to length(res) do sequence ri = res[i], -- a "flat" permute rdii = repeat(1,l) -- where per set integer rii = 0 for j=1 to length(ri) do integer rdx = ri[j], -- which set rnx = rdii[rdx] -- wherein"" rii += 1 rn[rdx][rnx] = rii -- plant 1..N rdii[rdx] = rnx+1 end for assert(rii=N) res[i] = deep_copy(rn) end for return res end function procedure test(sequence p) sequence q = partitions(p) string {ia,s} = iff(length(q)=1?{"is",""}:{"are","s"}) printf(1,"There %s %,d ordered partion%s for %v:\n{%s}\n", {ia,length(q),s,p,join(shorten(q,"",5,"%v"),"\n ")}) end procedure papply({{2,0,2},{1,1,1},{1,2,0,1},{1,2,3,4},{},{0,0,0}},test)
- Output:
There are 6 ordered partions for {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}}} There are 6 ordered partions for {1,1,1}: {{{1},{2},{3}} {{1},{3},{2}} {{2},{1},{3}} {{3},{1},{2}} {{2},{3},{1}} {{3},{2},{1}}} There are 12 ordered partions for {1,2,0,1}: {{{1},{2,3},{},{4}} {{1},{2,4},{},{3}} {{1},{3,4},{},{2}} {{2},{1,3},{},{4}} {{2},{1,4},{},{3}} {{3},{1,2},{},{4}} {{4},{1,2},{},{3}} {{3},{1,4},{},{2}} {{4},{1,3},{},{2}} {{2},{3,4},{},{1}} {{3},{2,4},{},{1}} {{4},{2,3},{},{1}}} There are 12,600 ordered partions for {1,2,3,4}: {{{1},{2,3},{4,5,6},{7,8,9,10}} {{1},{2,3},{4,5,7},{6,8,9,10}} {{1},{2,3},{4,5,8},{6,7,9,10}} {{1},{2,3},{4,5,9},{6,7,8,10}} {{1},{2,3},{4,5,10},{6,7,8,9}} ... {{9},{7,10},{5,6,8},{1,2,3,4}} {{10},{7,9},{5,6,8},{1,2,3,4}} {{8},{9,10},{5,6,7},{1,2,3,4}} {{9},{8,10},{5,6,7},{1,2,3,4}} {{10},{8,9},{5,6,7},{1,2,3,4}}} There is 1 ordered partion for {}: {{}} There is 1 ordered partion for {0,0,0}: {{{},{},{}}}
PicoLisp
Uses the 'comb' function from Combinations#PicoLisp
(de partitions (Args)
(let Lst (range 1 (apply + Args))
(recur (Args Lst)
(ifn Args
'(NIL)
(mapcan
'((L)
(mapcar
'((R) (cons L R))
(recurse (cdr Args) (diff Lst L)) ) )
(comb (car Args) Lst) ) ) ) ) )
Output:
: (more (partitions (2 0 2))) ((1 2) NIL (3 4)) ((1 3) NIL (2 4)) ((1 4) NIL (2 3)) ((2 3) NIL (1 4)) ((2 4) NIL (1 3)) ((3 4) NIL (1 2)) -> NIL : (more (partitions (1 1 1))) ((1) (2) (3)) ((1) (3) (2)) ((2) (1) (3)) ((2) (3) (1)) ((3) (1) (2)) ((3) (2) (1)) -> NIL
Python
from itertools import combinations
def partitions(*args):
def p(s, *args):
if not args: return [[]]
res = []
for c in combinations(s, args[0]):
s0 = [x for x in s if x not in c]
for r in p(s0, *args[1:]):
res.append([c] + r)
return res
s = range(sum(args))
return p(s, *args)
print partitions(2, 0, 2)
An equivalent but terser solution.
from itertools import combinations as comb
def partitions(*args):
def minus(s1, s2): return [x for x in s1 if x not in s2]
def p(s, *args):
if not args: return [[]]
return [[c] + r for c in comb(s, args[0]) for r in p(minus(s, c), *args[1:])]
return p(range(1, sum(args) + 1), *args)
print partitions(2, 0, 2)
Output:
[[(0, 1), (), (2, 3)], [(0, 2), (), (1, 3)], [(0, 3), (), (1, 2)], [(1, 2), (), (0, 3)], [(1, 3), (), (0, 2)], [(2, 3), (), (0, 1)]]
Or, more directly, without importing the combinations library:
'''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()
- Output:
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]]
Racket
#lang racket
(define (comb k xs)
(cond [(zero? k) (list (cons '() xs))]
[(null? xs) '()]
[else (append (for/list ([cszs (comb (sub1 k) (cdr xs))])
(cons (cons (car xs) (car cszs)) (cdr cszs)))
(for/list ([cszs (comb k (cdr xs))])
(cons (car cszs) (cons (car xs) (cdr cszs)))))]))
(define (partitions xs)
(define (p xs ks)
(if (null? ks)
'(())
(for*/list ([cszs (comb (car ks) xs)] [rs (p (cdr cszs) (cdr ks))])
(cons (car cszs) rs))))
(p (range 1 (add1 (foldl + 0 xs))) xs))
(define (run . xs)
(printf "partitions~s:\n" xs)
(for ([x (partitions xs)]) (printf " ~s\n" x))
(newline))
(run 2 0 2)
(run 1 1 1)
Output:
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))
Raku
(formerly Perl 6)
sub partition(@mask is copy) {
my @op;
my $last = [+] @mask or return [] xx 1;
for @mask.kv -> $k, $v {
next unless $v;
temp @mask[$k] -= 1;
for partition @mask -> @p {
@p[$k].push: $last;
@op.push: @p;
}
}
return @op;
}
.say for reverse partition [2,0,2];
- Output:
[[1, 2], (Any), [3, 4]] [[1, 3], (Any), [2, 4]] [[2, 3], (Any), [1, 4]] [[1, 4], (Any), [2, 3]] [[2, 4], (Any), [1, 3]] [[3, 4], (Any), [1, 2]]
REXX
//*REXX program displays the ordered partitions as: orderedPartitions(i, j, k, ···). */
call orderedPartitions 2,0,2 /*Note: 2,,2 will also work. */
call orderedPartitions 1,1,1
call orderedPartitions 1,2,0,1 /*Note: 1,2,,1 will also work. */
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
orderedPartitions: procedure; #=arg(); bot.=; top.=; low=; high=; d=123456789
t=0 /*T: is the sum of all the arguments.*/
do i=1 for #; t=t + arg(i) /*sum all the highest numbers in parts.*/
end /*i*/ /* [↑] may have an omitted argument. */
hdr= ' partitions for: ' /*define the start of the header text. */
do j=1 for #; _= arg(j) /* _: is the Jth argument. */
len.j=max(1, _) /*LEN: length of args. «0 is special»*/
bot.j=left(d, _); if _==0 then bot.j=0 /*define the bottom number for range.*/
top.j=right(left(d,t),_); if _==0 then top.j=0 /* " " top " " " */
@.j=left(d, t); if _==0 then @.j=0 /*define the digits used for VERIFY. */
hdr=hdr _ /*build (by appending) display header.*/
low=low || bot.j; high=high || top.j /*the low and high numbers for DO below*/
end /*j*/
/* [↓] same as: okD=left('0'd, t+1) */
/*define the legal digits to be used. */
okD=left(0 || d, t + 1) /*define the legal digits to be used. */
say; hdr=center(hdr" ", 60, '═'); say hdr /*display centered title for the output*/
say /*show a blank line (as a separator). */
do g=low to high /* [↑] generate the ordered partitions*/
if verify(g, okD) \==0 then iterate /*filter out unwanted partitions (digs)*/
p=1 /*P: is the position of a decimal dig.*/
$= /*$: will be the transformed numbers. */
do k=1 for #; _=substr(g, p, len.k) /*verify the partitions numbers. */
if verify(_, @.k) \==0 then iterate g /*is the decimal digit not valid ? */
!= /* [↓] validate the decimal number. */
if @.k\==0 then do j=1 for length(_); z=substr(_, j, 1) /*get a dig.*/
if pos(z, $)\==0 then iterate g /*previous ?*/
!=!','z /*add comma.*/
if j==1 then iterate /*is firstt?*/
if z<=substr(_, j-1, 1) then iterate g /*ordered ?*/
if pos(z, _, 1 +pos(z, _))\==0 then iterate g /*duplicate?*/
end /*j*/
p=p + len.k /*point to the next decimal digit (num)*/
$=$ ' {'strip(translate(!, ,0), ,",")'}' /*dress number up by suppessing LZ ··· */
end /*k*/
say center($, length(hdr) ) /*display numbers in ordered partition.*/
end /*g*/
return
- output when using the default inputs:
══════════════════ partitions for: 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 for: 1 1 1 ══════════════════ {1} {2} {3} {1} {3} {2} {2} {1} {3} {2} {3} {1} {3} {1} {2} {3} {2} {1} ═════════════════ partitions for: 1 2 0 1 ═════════════════ {1} {2,3} {} {4} {1} {2,4} {} {3} {1} {3,4} {} {2} {2} {1,3} {} {4} {2} {1,4} {} {3} {2} {3,4} {} {1} {3} {1,2} {} {4} {3} {1,4} {} {2} {3} {2,4} {} {1} {4} {1,2} {} {3} {4} {1,3} {} {2} {4} {2,3} {} {1}
Ruby
Brute force approach: simple but very slow
def partition(mask)
return [[]] if mask.empty?
[*1..mask.inject(:+)].permutation.map {|perm|
mask.map {|num_elts| perm.shift(num_elts).sort }
}.uniq
end
Recursive version: faster
def part(s, args)
return [[]] if args.empty?
s.combination(args[0]).each_with_object([]) do |c, res|
part(s - c, args[1..-1]).each{|r| res << ([c] + r)}
end
end
def partitions(args)
return [[]] if args.empty?
part((1..args.inject(:+)).to_a, args)
end
Test:
[[],[0,0,0],[1,1,1],[2,0,2]].each do |test_case|
puts "partitions #{test_case}:"
partition(test_case).each{|part| p part }
puts
end
- Output:
partitions []: [] partitions [0, 0, 0]: [[], [], []] partitions [1, 1, 1]: [[1], [2], [3]] [[1], [3], [2]] [[2], [1], [3]] [[2], [3], [1]] [[3], [1], [2]] [[3], [2], [1]] 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]]
Rust
use itertools::Itertools;
type NArray = Vec<Vec<Vec<usize>>>;
fn generate_partitions(args: &[usize]) -> NArray {
// calculate the sum of all partitions
let max = args.iter().sum();
// generate combinations with the given lengths
// for each partition
let c = args.iter().fold(vec![], |mut acc, arg| {
acc.push((1..=max).combinations(*arg).collect::<Vec<_>>());
acc
});
// create a cartesian product of all individual combinations
// filter/keep only where all the elements are there and exactly once
c.iter()
.map(|i| i.iter().cloned())
.multi_cartesian_product()
.unique()
.filter(|x| x.iter().cloned().flatten().unique().count() == max)
.collect::<Vec<_>>()
}
#[allow(clippy::clippy::ptr_arg)]
fn print_partitions(result: &NArray) {
println!("Partitions:");
for partition in result {
println!("{:?}", partition);
}
}
fn main() {
print_partitions(generate_partitions(&[2, 0, 2]).as_ref());
print_partitions(generate_partitions(&[1, 1, 1]).as_ref());
print_partitions(generate_partitions(&[2, 3]).as_ref());
print_partitions(generate_partitions(&[0]).as_ref());
}
- Output:
Partitions: [[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], [2], [3]] [[1], [3], [2]] [[2], [1], [3]] [[2], [3], [1]] [[3], [1], [2]] [[3], [2], [1]] Partitions: [[1, 2], [3, 4, 5]] [[1, 3], [2, 4, 5]] [[1, 4], [2, 3, 5]] [[1, 5], [2, 3, 4]] [[2, 3], [1, 4, 5]] [[2, 4], [1, 3, 5]] [[2, 5], [1, 3, 4]] [[3, 4], [1, 2, 5]] [[3, 5], [1, 2, 4]] [[4, 5], [1, 2, 3]] Partitions: [[]]
Sidef
func part(_, {.is_empty}) { [[]] }
func partitions({.is_empty}) { [[]] }
func part(s, args) {
gather {
s.combinations(args[0], { |*c|
part(s - c, args.slice(1)).each{|r| take([c] + r) }
})
}
}
func partitions(args) {
part(@(1..args.sum), args)
}
[[],[0,0,0],[1,1,1],[2,0,2]].each { |test_case|
say "partitions #{test_case}:"
partitions(test_case).each{|part| say part }
print "\n"
}
- Output:
partitions []: [] partitions [0, 0, 0]: [[], [], []] partitions [1, 1, 1]: [[1], [2], [3]] [[1], [3], [2]] [[2], [1], [3]] [[2], [3], [1]] [[3], [1], [2]] [[3], [2], [1]] 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]]
Tcl
package require Tcl 8.5
package require struct::set
# Selects all k-sized combinations from a list.
# "Borrowed" from elsewhere on RC
proc selectCombinationsFrom {k l} {
if {$k == 0} {return {}} elseif {$k == [llength $l]} {return [list $l]}
set all {}
set n [expr {[llength $l] - [incr k -1]}]
for {set i 0} {$i < $n} {} {
set first [lindex $l $i]
incr i
if {$k == 0} {
lappend all $first
} else {
foreach s [selectCombinationsFrom $k [lrange $l $i end]] {
lappend all [list $first {*}$s]
}
}
}
return $all
}
# Construct the partitioning of a given list
proc buildPartitions {lst n args} {
# Base case when we have no further partitions to process
if {[llength $args] == 0} {
return [list [list $lst]]
}
set result {}
set c [selectCombinationsFrom $n $lst]
if {[llength $c] == 0} {set c [list $c]}
foreach comb $c {
# Sort necessary for "nice" order
set rest [lsort -integer [struct::set difference $lst $comb]]
foreach p [buildPartitions $rest {*}$args] {
lappend result [list $comb {*}$p]
}
}
return $result
}
# Wrapper that assembles the initial list and calls the partitioner
proc partitions args {
set sum [tcl::mathop::+ {*}$args]
set startingSet {}
for {set i 1} {$i <= $sum} {incr i} {
lappend startingSet $i
}
return [buildPartitions $startingSet {*}$args]
}
Demonstration code:
puts [partitions 1 1 1]
puts [partitions 2 2]
puts [partitions 2 0 2]
puts [partitions 2 2 0]
Output:
{1 2 3} {1 3 2} {2 1 3} {2 3 1} {3 1 2} {3 2 1} {{1 2} {3 4}} {{1 3} {2 4}} {{1 4} {2 3}} {{2 3} {1 4}} {{2 4} {1 3}} {{3 4} {1 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}} {{1 2} {3 4} {}} {{1 3} {2 4} {}} {{1 4} {2 3} {}} {{2 3} {1 4} {}} {{2 4} {1 3} {}} {{3 4} {1 2} {}}
Ursala
#import std
#import nat
opart =
-+
~&art^?\~&alNCNC ^|JalSPfarSPMplrDSL/~& ^DrlPrrPlXXS/~&rt ^DrlrjXS/~&l choices@lrhPX,
^\~& nrange/1+ sum:-0+-
The library function choices
used in this solution takes a pair and returns the set of all subsets of having cardinality . The library function nrange
takes a pair of natural numbers to the minimum consecutive sequence containing them. The sum
function adds a pair of natural numbers.
#cast %nLLL
test = opart <2,0,2>
output:
< <<1,2>,<>,<3,4>>, <<1,3>,<>,<2,4>>, <<1,4>,<>,<2,3>>, <<2,3>,<>,<1,4>>, <<2,4>,<>,<1,3>>, <<3,4>,<>,<1,2>>>
Wren
import "os" for Process
var genPart // recursive so predeclare
genPart = Fn.new { |n, res, pos|
if (pos == res.count) {
var x = List.filled(n.count, null)
for (i in 0...x.count) x[i] = []
var i = 0
for (c in res) {
x[c].add(i+1)
i = i + 1
}
System.print(x)
return
}
for (i in 0...n.count) {
if (n[i] != 0) {
n[i] = n[i] - 1
res[pos] = i
genPart.call(n, res, pos+1)
n[i] = n[i] + 1
}
}
}
var orderedPart = Fn.new { |nParts|
System.print("Ordered %(nParts)")
var sum = 0
for (c in nParts) sum = sum + c
genPart.call(nParts, List.filled(sum, 0), 0)
}
var args = Process.arguments
if (args.count == 0) {
orderedPart.call([2, 0, 2])
return
}
var n = List.filled(args.count, 0)
var i = 0
for (a in args) {
n[i] = Num.fromString(a)
if (n[i] < 0) {
System.print("negative partition size not meaningful")
return
}
i = i + 1
}
orderedPart.call(n)
- Output:
$ wren_cli ordered_partitions.wren Ordered [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]] $ wren_cli ordered_partitions.wren 1 1 1 Ordered [1, 1, 1] [[1], [2], [3]] [[1], [3], [2]] [[2], [1], [3]] [[3], [1], [2]] [[2], [3], [1]] [[3], [2], [1]] $ wren_cli ordered_partitions.wren 1 2 3 4 | head Ordered [1, 2, 3, 4] [[1], [2, 3], [4, 5, 6], [7, 8, 9, 10]] [[1], [2, 3], [4, 5, 7], [6, 8, 9, 10]] [[1], [2, 3], [4, 5, 8], [6, 7, 9, 10]] [[1], [2, 3], [4, 5, 9], [6, 7, 8, 10]] [[1], [2, 3], [4, 5, 10], [6, 7, 8, 9]] [[1], [2, 3], [4, 6, 7], [5, 8, 9, 10]] [[1], [2, 3], [4, 6, 8], [5, 7, 9, 10]] [[1], [2, 3], [4, 6, 9], [5, 7, 8, 10]] [[1], [2, 3], [4, 6, 10], [5, 7, 8, 9]]
zkl
fcn partitions(args){
args=vm.arglist;
s:=(1).pump(args.sum(0),List); // (1,2,3,...)
fcn(s,args,p){
if(not args) return(T(T));
res:=List();
foreach c in (Utils.Helpers.pickNFrom(args[0],s)){
s0:=s.copy().removeEach(c);
foreach r in (self.fcn(s0,args[1,*])){ res.append(T(c).extend(r)) }
}
res
}(s,args)
}
args:=vm.arglist.apply("toInt"); // aka argv[1..]
if(not args) args=T(2,0,2);
partitions(args.xplode()).pump(Console.println,Void);
// or: foreach p in (partitions(1,1,1)){ println(p) }
- Output:
$ zkl bbb L(L(1,2),L(),L(3,4)) L(L(1,3),L(),L(2,4)) L(L(1,4),L(),L(2,3)) L(L(2,3),L(),L(1,4)) L(L(2,4),L(),L(1,3)) L(L(3,4),L(),L(1,2)) $ zkl bbb 1 1 1 L(L(1),L(2),L(3)) L(L(1),L(3),L(2)) L(L(2),L(1),L(3)) L(L(2),L(3),L(1)) L(L(3),L(1),L(2)) L(L(3),L(2),L(1))