Ordered partitions: Difference between revisions

{{task|Discrete math}}

 

<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>.

:<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

 

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.

Here are some explanatory remarks on the notation used in the task description:

 

 

=={{header|Ada}}==

partitions.ads:

with Ada.Containers.Ordered_Sets;

package Partitions is

(Partition);

function Create_Partitions (Args : Arguments) return Partition_Sets.Set;

 

partitions.adb:

-- compare number sets (not provided)

function "<" (Left, Right : Number_Sets.Set) return Boolean is

return Result;

end Create_Partitions;

 

example main.adb:

with Partitions;

procedure Main is

Ada.Text_IO.New_Line;

end;

 

Output:

=={{header|BBC BASIC}}==

{{works with|BBC BASIC for Windows}}

PRINT "partitions(2,0,2):"

PRINT FNpartitions(list1%())

j% -= 1

ENDWHILE

'''Output:'''

<pre>

=={{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)

 

return 1;

Output:

<pre>Part 2 0 2:

{ 0 } { 1 2 } { 3 5 6 } { 4 7 8 9 }

....</pre>

 

typedef unsigned int uint;

 

return 0;

 

=={{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

(loop while a do

(format t "~a~%" a)

<pre>#((1 2) NIL (3 4))

#((1 3) NIL (2 4))

{{trans|Python}}

Using module of the third D entry of the Combination Task.

combinations3;

 

auto b = args.length > 1 ? args.dropOne.to!(int[]) : [2, 0, 2];

writefln("%(%s\n%)", b.orderPart);

{{out}}

<pre>[[1, 2], [], [3, 4]]

===Alternative Version===

{{trans|C}}

 

void genBits(size_t N)(ref uint[N] bits, in ref uint[N] parts,

uint[parts.length] bits;

genBits(bits, parts, m - 1, m - 1, 0, parts[0], 0);

{{out}}

<pre>[1 2 ][][3 4 ]

 

=={{header|EchoLisp}}==

(lib 'list) ;; (combinations L k)

 

writeln

(_partitions (range 1 (1+ (apply + args))) args )))

{{out}}

<pre>

{{trans|Ruby}}

Brute force approach:

def partition([]), do: [[]]

def partition(mask) do

IO.inspect part

end)

 

{{out}}

[[1, 2], [], [3, 4]]

</pre>

 

=={{header|GAP}}==

local aux;

aux := function(i, u)

FixedPartitions(1, 1, 1);

# [ [ [ 1 ], [ 2 ], [ 3 ] ], [ [ 1 ], [ 3 ], [ 2 ] ], [ [ 2 ], [ 1 ], [ 3 ] ],

 

=={{header|Go}}==

 

import (

}

ordered_part(n)

Example command line use:

<pre>

=={{header|Groovy}}==

Solution:

int n = (sizes as List).sum()

def perms = n == 0 ? [[]] : (1..n).permutations()

return recomp[0] <=> recomp[1]

}

 

Test:

println it

 

Output:

 

=={{header|Haskell}}==

 

comb :: Int -> [a] -> [[a]]

p xs (k:ks) = [ cs:rs | cs <- comb k xs, rs <- p (xs \\ cs) ks ]

 

 

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 _ [] = []

p xs (k:ks) = [ cs:rs | (cs,zs) <- comb k xs, rs <- p zs ks ]

 

 

Output:

 

Faster by keeping track of the length of lists:

 

 

 

 

=={{header|J}}==

Brute force approach:

 

 

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:

 

┌───┬┬───┐

│0 1││2 3│

360360

*/ (! +/\.)3 5 7

 

Here's some intermediate results for that first example:

 

4 2 2

({@comb&.> +/\.) 2 0 2

├───┼┼───┤

│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│

┌───┬───┬───┬───┐

│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|JavaScript}}==

{{trans|Haskell}}

 

'use strict';

 

return partitions(2, 0, 2);

 

 

{{Out}}

 

[[1, 3], [], [2, 4]],

[[1, 4], [], [2, 3]],

[[2, 3], [], [1, 4]],

[[2, 4], [], [1, 3]],

 

=={{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

| [$c] + ($mask[1:] | p(s - $c))

end;

'''Example''':

| . as $test_case

{{Out}}

 

partitions []:

[[2,3],[],[1,4]]

[[2,4],[],[1,3]]

 

=={{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

 

println(orderedpartitions([1, 1, 1]))

 

{{output}}

<pre>

 

=={{header|Kotlin}}==

 

fun nextPerm(perm: IntArray): Boolean {

while (nextPerm(perm))

println("]")

 

{{out}}

=={{header|Lua}}==

A pretty verbose solution. Maybe somebody can replace with something terser/better.

local function range(n)

local res = {}

end

io.write "]"

 

Output:

</pre>

 

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.

 

While[n>0,s=Join[s,{Take[t,(k=First[list])]}];t=Drop[t,k];list=Rest[list];n--]; s]

 

 

 

 

 

 

 

 

=={{header|Perl}}==

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 Thread::Queue;

 

};

 

(async{ &$gen; # start the main work load

$q->enqueue(undef) # signal that there's no more data

print "@$a | @$b | @$rb\n";

}

 

 

sub partition {

 

print "(" . join(', ', map { "{".join(', ', @$_)."}" } @$_) . ")\n"

 

Example command-line use:

</pre>

 

 

=={{header|Phix}}==

{{out}}

<pre>

{{}}

</pre>

 

=={{header|PicoLisp}}==

Uses the 'comb' function from [[Combinations#PicoLisp]]

(let Lst (range 1 (apply + Args))

(recur (Args Lst)

'((R) (cons L R))

(recurse (cdr Args) (diff Lst L)) ) )

Output:

<pre>: (more (partitions (2 0 2)))

 

=={{header|Python}}==

 

def partitions(*args):

return p(s, *args)

 

 

An equivalent but terser solution.

 

def partitions(*args):

return p(range(1, sum(args) + 1), *args)

 

 

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)]]

</pre>

 

=={{header|Racket}}==

{{trans|Haskell}}

 

#lang racket

(define (comb k xs)

(run 2 0 2)

(run 1 1 1)

 

Output:

((3) (2) (1))

</pre>

 

=={{header|REXX}}==

call orderedPartitions 2,0,2 /*Note: 2,,2 will also work. */

call orderedPartitions 1,1,1

exit /*stick a fork in it, we're all done. */

/*──────────────────────────────────────────────────────────────────────────────────────*/

t=0 /*T: is the sum of all the arguments.*/

do j=1 for #; _= arg(j) /* _: is the Jth argument. */

@.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*/

okD=left(0 || d, t + 1) /*define the legal digits to be used. */

do g=low to high /* [↑] generate the ordered partitions*/

p=1 /*P: is the position of a decimal dig.*/

$= /*$: will be the transformed numbers. */

if verify(_, @.k) \==0 then iterate g /*is the decimal digit not valid ? */

!= /* [↓] validate the decimal number. */

end /*j*/

end /*k*/

end /*g*/

{{out|output|text=&nbsp; when using the default inputs:}}

<pre>

 

 

 

 

 

</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

 

'''Recursive version:''' faster

{{trans|Python}}

return [[]] if args.empty?

s.combination(args[0]).each_with_object([]) do |c, res|

return [[]] if args.empty?

part((1..args.inject(:+)).to_a, args)

 

'''Test:'''

puts "partitions #{test_case}:"

partition(test_case).each{|part| p part }

puts

{{Output}}

<pre>

[[2, 4], [], [1, 3]]

[[3, 4], [], [1, 2]]

</pre>

 

=={{header|Sidef}}==

{{trans|Ruby}}

func partitions({.is_empty}) { [[]] }

 

gather {

s.combinations(args[0], { |*c|

})

}

partitions(test_case).each{|part| say part }

print "\n"

 

{{out}}

=={{header|Tcl}}==

{{tcllib|struct::set}}

package require struct::set

 

 

return [buildPartitions $startingSet {*}$args]

Demonstration code:

puts [partitions 2 2]

puts [partitions 2 0 2]

Output:

<pre>

 

=={{header|Ursala}}==

#import nat

 

-+

~&art^?\~&alNCNC ^|JalSPfarSPMplrDSL/~& ^DrlPrrPlXXS/~&rt ^DrlrjXS/~&l choices@lrhPX,

 

output:

<pre><

<<2,4>,<>,<1,3>>,

<<3,4>,<>,<1,2>>></pre>

 

=={{header|zkl}}==

{{trans|Python}}

args=vm.arglist;

s:=(1).pump(args.sum(0),List); // (1,2,3,...)

res

}(s,args)

if(not args) args=T(2,0,2);

partitions(args.xplode()).pump(Console.println,Void);

{{out}}

<pre>