Ordered partitions: Difference between revisions
m
→{{header|Wren}}: Changed to Wren S/H
(Added EchoLisp) |
m (→{{header|Wren}}: Changed to Wren S/H) |
||
(45 intermediate revisions by 16 users not shown) | |||
Line 1:
{{task|Discrete math}}
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.
<math>partitions(\mathit{arg}_1,\mathit{arg}_2,...,\mathit{arg}_n)</math> should generate all distributions of the elements in <math>\{1,...,\Sigma_{i=1}^n\mathit{arg}_i\}</math> into <math>n</math> blocks of respective size <math>\mathit{arg}_1,\mathit{arg}_2,...,\mathit{arg}_n</math>.
Line 29 ⟶ 32:
:<math>{\mathit{arg}_1+\mathit{arg}_2+...+\mathit{arg}_n \choose \mathit{arg}_1} \cdot {\mathit{arg}_2+\mathit{arg}_3+...+\mathit{arg}_n \choose \mathit{arg}_2} \cdot \ldots \cdot {\mathit{arg}_n \choose \mathit{arg}_n}</math>
(see [http://en.wikipedia.org/wiki/Binomial_coefficient 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 [http://en.wikipedia.org/wiki/Multinomial_coefficient multinomial coefficient]).
Also, <math>partitions(1,1,1)</math> creates the permutations of <math>\{1,2,3\}</math> and thus there would be <math>3! = 6</math> 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 <math>partitions(2,0,2)</math>. If the programming language does not support polyvariadic functions pass a list as an argument.
Line 37 ⟶ 42:
Here are some explanatory remarks on the notation used in the task description:
<math>\{1, \ldots, n\}</math> denotes the set of consecutive numbers from <math>1</math> to <math>n</math>, e.g. <math>\{1,2,3\}</math> if <math>n = 3</math>
<math>\Sigma</math> is the mathematical notation for summation, e.g. <math>\Sigma_{i=1}^3 i = 6</math> (see also [http://en.wikipedia.org/wiki/Summation#Capital-sigma_notation]).
<math>\mathit{arg}_1,\mathit{arg}_2,...,\mathit{arg}_n</math> are the arguments — natural numbers — that the sought function receives.
<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}}==
partitions.ads:
<
with Ada.Containers.Ordered_Sets;
package Partitions is
Line 53 ⟶ 133:
(Partition);
function Create_Partitions (Args : Arguments) return Partition_Sets.Set;
end Partitions;</
partitions.adb:
<
-- compare number sets (not provided)
function "<" (Left, Right : Number_Sets.Set) return Boolean is
Line 203 ⟶ 283:
return Result;
end Create_Partitions;
end Partitions;</
example main.adb:
<
with Partitions;
procedure Main is
Line 266 ⟶ 346:
Ada.Text_IO.New_Line;
end;
end Main;</
Output:
Line 279 ⟶ 359:
=={{header|BBC BASIC}}==
{{works with|BBC BASIC for Windows}}
<
PRINT "partitions(2,0,2):"
PRINT FNpartitions(list1%())
Line 330 ⟶ 410:
j% -= 1
ENDWHILE
= TRUE</
'''Output:'''
<pre>
Line 366 ⟶ 446:
=={{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.
<
int next_perm(int size, int * nums)
Line 416 ⟶ 496:
return 1;
}</
Output:
<pre>Part 2 0 2:
Line 434 ⟶ 514:
{ 0 } { 1 2 } { 3 5 6 } { 4 7 8 9 }
....</pre>
With bitfield:<
typedef unsigned int uint;
Line 484 ⟶ 564:
return 0;
}</
=={{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}}==
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).
<
(let ((e (elt x i)))
(loop for c in l do
Line 533 ⟶ 764:
(loop while a do
(format t "~a~%" a)
(setf a (next-part a #'string<))))</
<pre>#((1 2) NIL (3 4))
#((1 3) NIL (2 4))
Line 549 ⟶ 780:
{{trans|Python}}
Using module of the third D entry of the Combination Task.
<
combinations3;
Line 573 ⟶ 804:
auto b = args.length > 1 ? args.dropOne.to!(int[]) : [2, 0, 2];
writefln("%(%s\n%)", b.orderPart);
}</
{{out}}
<pre>[[1, 2], [], [3, 4]]
Line 584 ⟶ 815:
===Alternative Version===
{{trans|C}}
<
void genBits(size_t N)(ref uint[N] bits, in ref uint[N] parts,
Line 627 ⟶ 858:
uint[parts.length] bits;
genBits(bits, parts, m - 1, m - 1, 0, parts[0], 0);
}</
{{out}}
<pre>[1 2 ][][3 4 ]
Line 637 ⟶ 868:
=={{header|EchoLisp}}==
<
(lib 'list) ;; (combinations L k)
Line 663 ⟶ 894:
writeln
(_partitions (range 1 (1+ (apply + args))) args )))
</syntaxhighlight>
{{out}}
<pre>
Line 700 ⟶ 931:
{{trans|Ruby}}
Brute force approach:
<
def partition([]), do: [[]]
def partition(mask) do
Line 729 ⟶ 960:
IO.inspect part
end)
end)</
{{out}}
Line 755 ⟶ 986:
[[1, 2], [], [3, 4]]
</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}}==
<
local aux;
aux := function(i, u)
Line 784 ⟶ 1,100:
FixedPartitions(1, 1, 1);
# [ [ [ 1 ], [ 2 ], [ 3 ] ], [ [ 1 ], [ 3 ], [ 2 ] ], [ [ 2 ], [ 1 ], [ 3 ] ],
# [ [ 2 ], [ 3 ], [ 1 ] ], [ [ 3 ], [ 1 ], [ 2 ] ], [ [ 3 ], [ 2 ], [ 1 ] ] ]</
=={{header|Go}}==
<
import (
Line 846 ⟶ 1,162:
}
ordered_part(n)
}</
Example command line use:
<pre>
Line 882 ⟶ 1,198:
=={{header|Groovy}}==
Solution:
<
int n = (sizes as List).sum()
def perms = n == 0 ? [[]] : (1..n).permutations()
Line 894 ⟶ 1,210:
return recomp[0] <=> recomp[1]
}
}</
Test:
<
println it
}</
Output:
Line 910 ⟶ 1,226:
=={{header|Haskell}}==
<
comb :: Int -> [a] -> [[a]]
Line 922 ⟶ 1,238:
p xs (k:ks) = [ cs:rs | cs <- comb k xs, rs <- p (xs \\ cs) ks ]
main = print $ partitions [2,0,2]</
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.
<
comb 0 xs = [([],xs)]
comb _ [] = []
Line 938 ⟶ 1,254:
p xs (k:ks) = [ cs:rs | (cs,zs) <- comb k xs, rs <- p zs ks ]
main = print $ partitions [2,0,2]</
Output:
Line 947 ⟶ 1,263:
Faster by keeping track of the length of lists:
<syntaxhighlight lang="haskell">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]</syntaxhighlight>
=={{header|J}}==
Line 967 ⟶ 1,294:
Brute force approach:
<
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.
Line 974 ⟶ 1,301:
Examples:
<
┌───┬┬───┐
│0 1││2 3│
Line 1,012 ⟶ 1,339:
360360
*/ (! +/\.)3 5 7
360360</
Here's some intermediate results for that first example:
<
4 2 2
({@comb&.> +/\.) 2 0 2
Line 1,037 ⟶ 1,364:
├───┼┼───┤
│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 <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):
<
┌───┬───┐
│0 1│2 3│
Line 1,052 ⟶ 1,379:
┌───┬───┬───┬───┐
│0 1│2 3│4 5│6 7│
└───┴───┴───┴───┘</
Breaking down that last example:
<
┌───┬───┬───┬───┐
│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).
=={{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}}==
Line 1,069 ⟶ 1,483:
{{trans|Haskell}}
<
'use strict';
Line 1,129 ⟶ 1,543:
return partitions(2, 0, 2);
})();</
{{Out}}
<
[[1, 3], [], [2, 4]],
[[1, 4], [], [2, 3]],
[[2, 3], [], [1, 4]],
[[2, 4], [], [1, 3]],
[[3, 4], [], [1, 2]]]</
=={{header|jq}}==
{{works with|jq|1.4}}
''The approach adopted here is similar to the [[#Python]] solution''.
<
def combination(r):
if r > length or r < 0 then empty
Line 1,162 ⟶ 1,576:
| [$c] + ($mask[1:] | p(s - $c))
end;
. as $mask | p( [range(1; 1 + ($mask|add))] );</
'''Example''':
<
| . as $test_case
| "partitions \($test_case):" , ($test_case | partition), ""</
{{Out}}
<
partitions []:
Line 1,190 ⟶ 1,604:
[[2,3],[],[1,4]]
[[2,4],[],[1,3]]
[[3,4],[],[1,2]]</
=={{header|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.
<syntaxhighlight lang="julia">
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]))
</syntaxhighlight>
{{output}}
<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|Kotlin}}==
<syntaxhighlight lang="scala">// 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("]")
}</syntaxhighlight>
{{out}}
Combined output of 3 separate runs with different command line parameters:
<pre>
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]]
]
</pre>
=={{header|Lua}}==
A pretty verbose solution. Maybe somebody can replace with something terser/better.
<
local function range(n)
local res = {}
Line 1,282 ⟶ 1,842:
end
io.write "]"
io.write "\n"</
Output:
Line 1,290 ⟶ 1,850:
</pre>
=={{header|Mathematica}}/{{header|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.
<syntaxhighlight 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]
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}}==
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.
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
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)</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}}==
===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.
<syntaxhighlight lang
use warnings;
use Thread 'async';
use Thread::Queue;
Line 1,352 ⟶ 2,001:
};
$q =
(async{ &$gen; # start the main work load
$q->enqueue(undef) # signal that there's no more data
Line 1,368 ⟶ 2,017:
print "@$a | @$b | @$rb\n";
}
}</syntaxhighlight>
{{trans|
<syntaxhighlight lang
use warnings;
use List::Util 1.33 qw(sum pairmap);
sub partition {
Line 1,391 ⟶ 2,041:
print "(" . join(', ', map { "{".join(', ', @$_)."}" } @$_) . ")\n"
for partition( @ARGV ? @ARGV : (2, 0, 2) );</
Example command-line use:
Line 1,412 ⟶ 2,062:
</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
=={{header|
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.
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #7060A8;">requires</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"1.0.2"</span><span style="color: #0000FF;">)</span>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<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>
<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>
<span style="color: #000080;font-style:italic;">-- 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]</span>
<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>
<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>
<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>
<span style="color: #004080;">integer</span> <span style="color: #000000;">rii</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<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>
<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>
<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>
<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>
<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>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<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>
<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>
<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}}
<pre>
There are 6 ordered partions for {2,0,2}:
{{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}:
{{{},{},{}}}
</pre>
=={{header|PicoLisp}}==
Uses the 'comb' function from [[Combinations#PicoLisp]]
<
(let Lst (range 1 (apply + Args))
(recur (Args Lst)
Line 1,446 ⟶ 2,167:
'((R) (cons L R))
(recurse (cdr Args) (diff Lst L)) ) )
(comb (car Args) Lst) ) ) ) ) )</
Output:
<pre>: (more (partitions (2 0 2)))
Line 1,467 ⟶ 2,188:
=={{header|Python}}==
<
def partitions(*args):
Line 1,481 ⟶ 2,202:
return p(s, *args)
print partitions(2, 0, 2)</
An equivalent but terser solution.
<
def partitions(*args):
Line 1,493 ⟶ 2,214:
return p(range(1, sum(args) + 1), *args)
print partitions(2, 0, 2)</
Output:
Line 1,500 ⟶ 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)]]
</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}}==
Line 1,505 ⟶ 2,357:
{{trans|Haskell}}
<syntaxhighlight lang="racket">
#lang racket
(define (comb k xs)
Line 1,529 ⟶ 2,381:
(run 2 0 2)
(run 1 1 1)
</syntaxhighlight>
Output:
Line 1,550 ⟶ 2,402:
</pre>
=={{header|
(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;
}
}
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}}==
<syntaxhighlight lang="rexx">//*REXX program displays the ordered partitions as: orderedPartitions(i, j, k, ···). */
call orderedPartitions 2,0,2
call orderedPartitions 1,1,1
call orderedPartitions 1,2,0,1
exit /*
/*──────────────────────────────────────────────────────────────────────────────────────*/
orderedPartitions: procedure; #=arg(); bot.=; top.=; low=; high=; d=123456789
t=0
end /*i*/
hdr= ' partitions for: '
do j=1 for #; _= arg(j) /* _: is the Jth argument.
len.j=max(1, _)
bot.j=left(d,
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
$=$ ' {'strip(translate(!, ,0), ,
end /*k*/
say center($, length(hdr) ) /*display numbers in ordered partition.*/
end /*g*/
return</syntaxhighlight>
{{out|output|text= when using the default inputs:}}
<pre>
══════════════════ 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}
{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}
</pre>
=={{header|Ruby}}==
'''Brute force approach:''' simple but very slow
<
return [[]] if mask.empty?
[*1..mask.inject(:+)].permutation.map {|perm|
mask.map {|num_elts| perm.shift(num_elts).sort }
}.uniq
end</
'''Recursive version:''' faster
{{trans|Python}}
<
return [[]] if args.empty?
s.combination(args[0]).each_with_object([]) do |c, res|
Line 1,655 ⟶ 2,529:
return [[]] if args.empty?
part((1..args.inject(:+)).to_a, args)
end</
'''Test:'''
<
puts "partitions #{test_case}:"
partition(test_case).each{|part| p part }
puts
end</
{{Output}}
<pre>
Line 1,686 ⟶ 2,560:
[[2, 4], [], [1, 3]]
[[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>
=={{header|Sidef}}==
{{trans|Ruby}}
<
func partitions({.is_empty}) { [[]] }
func part(s, args) {
gather {
s.combinations(args[0], { |*c|
part(s - c, args.
})
}
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"
}</
{{out}}
Line 1,738 ⟶ 2,684:
=={{header|Tcl}}==
{{tcllib|struct::set}}
<
package require struct::set
Line 1,789 ⟶ 2,735:
return [buildPartitions $startingSet {*}$args]
}</
Demonstration code:
<
puts [partitions 2 2]
puts [partitions 2 0 2]
puts [partitions 2 2 0]</
Output:
<pre>
Line 1,804 ⟶ 2,750:
=={{header|Ursala}}==
<
#import nat
Line 1,811 ⟶ 2,757:
-+
~&art^?\~&alNCNC ^|JalSPfarSPMplrDSL/~& ^DrlPrrPlXXS/~&rt ^DrlrjXS/~&l choices@lrhPX,
^\~& nrange/1+ sum:-0+-</
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.<
test = opart <2,0,2></
output:
<pre><
Line 1,823 ⟶ 2,769:
<<2,4>,<>,<1,3>>,
<<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}}==
{{trans|Python}}
<
args=vm.arglist;
s:=(1).pump(args.sum(0),List); // (1,2,3,...)
Line 1,838 ⟶ 2,868:
res
}(s,args)
}</
<
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) }</
{{out}}
<pre>
|