Ordered partitions: Difference between revisions
m
→{{header|Wren}}: Changed to Wren S/H
(→{{header|Phix}}: replaced with much more efficient version, syntax coloured) |
m (→{{header|Wren}}: Changed to Wren S/H) |
||
| (6 intermediate revisions by 4 users not shown) | |||
Line 52:
{{trans|Nim}}
<
[[[Int]]] r
[(Int, Int)] slices
Line 98:
displayPermutations(:argv[1..].map(Int))
E
displayPermutations([2, 0, 2])</
{{out}}
Line 121:
=={{header|Ada}}==
partitions.ads:
<
with Ada.Containers.Ordered_Sets;
package Partitions is
Line 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 283:
return Result;
end Create_Partitions;
end Partitions;</
example main.adb:
<
with Partitions;
procedure Main is
Line 346:
Ada.Text_IO.New_Line;
end;
end Main;</
Output:
Line 359:
=={{header|BBC BASIC}}==
{{works with|BBC BASIC for Windows}}
<
PRINT "partitions(2,0,2):"
PRINT FNpartitions(list1%())
Line 410:
j% -= 1
ENDWHILE
= TRUE</
'''Output:'''
<pre>
Line 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 496:
return 1;
}</
Output:
<pre>Part 2 0 2:
Line 514:
{ 0 } { 1 2 } { 3 5 6 } { 4 7 8 9 }
....</pre>
With bitfield:<
typedef unsigned int uint;
Line 564:
return 0;
}</
=={{header|C sharp}}==
<
using System.Linq;
using System.Collections.Generic;
Line 634:
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;
}</
{{out}}
<pre>
Line 654:
=={{header|C++}}==
<
#include <iostream>
#include <algorithm>
Line 707:
std::cin.get();
return 0;
}</
{{out}}
Line 719:
=={{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 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 780:
{{trans|Python}}
Using module of the third D entry of the Combination Task.
<
combinations3;
Line 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 815:
===Alternative Version===
{{trans|C}}
<
void genBits(size_t N)(ref uint[N] bits, in ref uint[N] parts,
Line 858:
uint[parts.length] bits;
genBits(bits, parts, m - 1, m - 1, 0, parts[0], 0);
}</
{{out}}
<pre>[1 2 ][][3 4 ]
Line 868:
=={{header|EchoLisp}}==
<
(lib 'list) ;; (combinations L k)
Line 894:
writeln
(_partitions (range 1 (1+ (apply + args))) args )))
</syntaxhighlight>
{{out}}
<pre>
Line 931:
{{trans|Ruby}}
Brute force approach:
<
def partition([]), do: [[]]
def partition(mask) do
Line 960:
IO.inspect part
end)
end)</
{{out}}
Line 990:
=={{header|FreeBASIC}}==
{{trans|BBC BASIC}}
<
Dim As Integer i, j
For i = Ubound(x,1)-1 To 0 Step -1
Line 1,044:
Print Particiones(list3())
Sleep</
{{out}}
<pre>
Line 1,073:
=={{header|GAP}}==
<
local aux;
aux := function(i, u)
Line 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 1,162:
}
ordered_part(n)
}</
Example command line use:
<pre>
Line 1,198:
=={{header|Groovy}}==
Solution:
<
int n = (sizes as List).sum()
def perms = n == 0 ? [[]] : (1..n).permutations()
Line 1,210:
return recomp[0] <=> recomp[1]
}
}</
Test:
<
println it
}</
Output:
Line 1,226:
=={{header|Haskell}}==
<
comb :: Int -> [a] -> [[a]]
Line 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 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 1,263:
Faster by keeping track of the length of lists:
<
-- choose m out of n items, return tuple of chosen and the rest
Line 1,288:
main :: IO ()
main = mapM_ print $ partitions [5, 5, 5]</
=={{header|J}}==
Line 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 1,301:
Examples:
<
┌───┬┬───┐
│0 1││2 3│
Line 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,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,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,396 ⟶ 1,483:
{{trans|Haskell}}
<
'use strict';
Line 1,456 ⟶ 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,489 ⟶ 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,517 ⟶ 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.
<
using Combinatorics
Line 1,548 ⟶ 1,635:
println(orderedpartitions([1, 1, 1]))
</syntaxhighlight>
{{output}}
<pre>
Line 1,566 ⟶ 1,653:
=={{header|Kotlin}}==
<
fun nextPerm(perm: IntArray): Boolean {
Line 1,634 ⟶ 1,721:
while (nextPerm(perm))
println("]")
}</
{{out}}
Line 1,667 ⟶ 1,754:
=={{header|Lua}}==
A pretty verbose solution. Maybe somebody can replace with something terser/better.
<
local function range(n)
local res = {}
Line 1,755 ⟶ 1,842:
end
io.write "]"
io.write "\n"</
Output:
Line 1,770 ⟶ 1,857:
'''Sort''' and '''Union''' eliminate duplicates.
<
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[{1, 1, 1}]</
[[File:Example.png]]
Line 1,785 ⟶ 1,872:
As requested, the arguments specifying the length of each sequence may also be provided on the command line.
<
type Partition = seq[seq[int]]
Line 1,861 ⟶ 1,948:
else:
displayPermutations(2, 0, 2)</
{{out}}
Line 1,882 ⟶ 1,969:
=={{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,911 ⟶ 2,001:
};
$q =
(async{ &$gen; # start the main work load
$q->enqueue(undef) # signal that there's no more data
Line 1,927 ⟶ 2,017:
print "@$a | @$b | @$rb\n";
}
}</syntaxhighlight>
{{trans|Raku}}
<syntaxhighlight lang
use warnings;
use List::Util 1.33 qw(sum pairmap);
sub partition {
Line 1,950 ⟶ 2,041:
print "(" . join(', ', map { "{".join(', ', @$_)."}" } @$_) . ")\n"
for partition( @ARGV ? @ARGV : (2, 0, 2) );</
Example command-line use:
Line 1,977 ⟶ 2,068:
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.
<!--<
<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>
Line 2,016 ⟶ 2,107:
<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>
<!--</
{{out}}
<pre>
Line 2,066 ⟶ 2,157:
=={{header|PicoLisp}}==
Uses the 'comb' function from [[Combinations#PicoLisp]]
<
(let Lst (range 1 (apply + Args))
(recur (Args Lst)
Line 2,076 ⟶ 2,167:
'((R) (cons L R))
(recurse (cdr Args) (diff Lst L)) ) )
(comb (car Args) Lst) ) ) ) ) )</
Output:
<pre>: (more (partitions (2 0 2)))
Line 2,097 ⟶ 2,188:
=={{header|Python}}==
<
def partitions(*args):
Line 2,111 ⟶ 2,202:
return p(s, *args)
print partitions(2, 0, 2)</
An equivalent but terser solution.
<
def partitions(*args):
Line 2,123 ⟶ 2,214:
return p(range(1, sum(args) + 1), *args)
print partitions(2, 0, 2)</
Output:
Line 2,134 ⟶ 2,225:
Or, more directly, without importing the ''combinations'' library:
{{Works with|Python|3.7}}
<
Line 2,240 ⟶ 2,331:
# MAIN ---
if __name__ == '__main__':
main()</
{{Out}}
<pre>Tests of the partitions function:
Line 2,266 ⟶ 2,357:
{{trans|Haskell}}
<syntaxhighlight lang="racket">
#lang racket
(define (comb k xs)
Line 2,290 ⟶ 2,381:
(run 2 0 2)
(run 1 1 1)
</syntaxhighlight>
Output:
Line 2,314 ⟶ 2,405:
(formerly Perl 6)
{{works with|Rakudo|2018.04.1}}
<syntaxhighlight lang="raku"
my @op;
my $last = [+] @mask or return [] xx 1;
Line 2,328 ⟶ 2,419:
}
.say for reverse partition [2,0,2];</
{{out}}
<pre>[[1, 2], (Any), [3, 4]]
Line 2,338 ⟶ 2,429:
=={{header|REXX}}==
<
call orderedPartitions 2,0,2 /*Note: 2,,2 will also work. */
call orderedPartitions 1,1,1
Line 2,381 ⟶ 2,472:
say center($, length(hdr) ) /*display numbers in ordered partition.*/
end /*g*/
return</
{{out|output|text= when using the default inputs:}}
<pre>
Line 2,420 ⟶ 2,511:
=={{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 2,438 ⟶ 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 2,472 ⟶ 2,563:
=={{header|Rust}}==
<
use itertools::Itertools;
Line 2,511 ⟶ 2,602:
print_partitions(generate_partitions(&[0]).as_ref());
}
</syntaxhighlight>
{{out}}
<pre>
Line 2,545 ⟶ 2,636:
=={{header|Sidef}}==
{{trans|Ruby}}
<
func partitions({.is_empty}) { [[]] }
Line 2,551 ⟶ 2,642:
gather {
s.combinations(args[0], { |*c|
part(s - c, args.
})
}
Line 2,564 ⟶ 2,655:
partitions(test_case).each{|part| say part }
print "\n"
}</
{{out}}
Line 2,593 ⟶ 2,684:
=={{header|Tcl}}==
{{tcllib|struct::set}}
<
package require struct::set
Line 2,644 ⟶ 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 2,659 ⟶ 2,750:
=={{header|Ursala}}==
<
#import nat
Line 2,666 ⟶ 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 2,681 ⟶ 2,772:
=={{header|Wren}}==
{{trans|Go}}
<
var genPart // recursive so predeclare
Line 2,728 ⟶ 2,819:
i = i + 1
}
orderedPart.call(n)</
{{out}}
Line 2,765 ⟶ 2,856:
=={{header|zkl}}==
{{trans|Python}}
<
args=vm.arglist;
s:=(1).pump(args.sum(0),List); // (1,2,3,...)
Line 2,777 ⟶ 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>
| |||