<

The procedure  Partition  significantly generalizes the standard procedure  combinat[partition]  in several ways. The user specifies the number of parts of the partition, and can also set different limitations on parts partition.

Required parameters:  n - a nonnegative integer, - a positive integer or a range (k  specifies the number of parts of the partition). The parameter  res  is the optional parameter (by default  res is  ). If  res  is a number, all elements of  k-tuples must be greater than or equal  res .  If  res  is a range  a .. b ,   all elements of  k-tuples must be greater than or equal  a  and  less than or equal  b . The optional parameter  S  - set, which includes elements of the partition. By default  S = {$ 0.. n} .

The code of the procedure:

Partition:=proc(n::nonnegint, k::{posint,range}, res::{range, nonnegint} := 1, S::set:={$0..n})  # Generates a list of all partitions of an integer n into k parts

local k_Partition, n1, k1, L;

 

k_Partition := proc (n, k::posint, res, S)

local m, M, a, b, S1, It, L0;

m:=S[1]; M:=S[-1];

if res::nonnegint then a := max(res,m); b := min(n-(k-1)*a,M)  else a := max(lhs(res),m); b := min(rhs(res),M) fi;

S1:={$a..b} intersect S;

if b < a or b*k < n or a*k > n  then return [ ] fi;

It := proc (L)

local m, j, P, R, i, N;

m := nops(L[1]); j := k-m; N := 0;

for i to nops(L) do

R := n-`+`(op(L[i]));

if R <= b*j and a*j <= R then N := N+1;

P[N] := [seq([op(L[i]), s], s = {$ max(a, R-b*(j-1)) .. min(R, b)} intersect select(t->t>=L[i,-1],S1) )] fi;

od;

[seq(op(P[s]), s = 1 .. N)];

end proc;

if k=1 then [[b]] else (It@@(k-1))(map(t->[t],S1))  fi;

end proc;

 

if k::posint then return k_Partition(n,k,res,S) else n1:=0;

for k1 from lhs(k) to rhs(k) do

n1:=n1+1; L[n1]:=k_Partition(n,k1,res,S)

od;

L:=convert(L,list);

[seq(op(L[i]), i=1..n1)] fi;

 

end proc:

 

Examples of use:

Partition(15, 3);

 

 

Partition(15, 3..5, 1..5);  # The number of parts from 3 to 5, and each summand from 1 to 5

 

 

Partition(15, 5, {seq(2*n-1, n=1..8)});  # 5 summands and all are odd numbers 

 

 

A more interesting example.
There are  k banknotes in possible denominations of 5, 10, 20, 50, 100 dollars. At what number of banknotes  k  the number of variants of exchange  $140  will be maximum?

n:=0:

for k from 3 to 28 do

n:=n+1: V[n]:=[k, nops(Partition(140, k, {5,10,20,50,100}))];

od:

V:=convert(V, list);

max(seq(V[i,2], i=1..nops(V)));

select(t->t[2]=8, V);

 

Here are these variants:

Partition(140, 10, {5,10,20,50,100});

Partition(140, 13, {5,10,20,50,100});

 

 Partition.mws

 

 

 


Please Wait...