The work contains two procedures called  SetPartition  and  NumbPart .

The first procedure  SetPartition  generates all the partitions of a set  S  into disjoint subsets of specific sizes defined by a list  Q. The third optional parameter is the symbol  `ordered`  or  `nonordered`  (by default) . It determines whether the order of subsets in a partition is significant.

The second procedure  NumbPart  returns the number of all partitions of the sizes indicated by  Q .


Codes of these procedures:

SetPartition:=proc(S::set, Q::list(posint), K::symbol:=nonordered)  # Procedure finds all partitions of the set  S  into subsets of the specific size given Q.

local L, P, T, S1, S2, n, i, j, m, k, M;

uses ListTools,combinat;

if `+`(op(Q))<>nops(S) then error "Should be `+`(op(Q))=nops(S)" fi;


T:=[seq([L[i],Occurrences(L[i],Q)], i=1..nops(L))];


S1:=S;  S2:={`if`(K=ordered,[],{})}; n:=nops(P);

for i to n do

m:=P[i,1]; k:=P[i,2];

for j to k do

S2:={seq(seq(`if`(K=ordered,[op(s),t],{op(s),t}), t=choose(S1 minus `union`(op(s)),m)), s=S2)};

od; od;

if K=ordered then {map(op@permute,S2)[]} else S2 fi;

end proc:


NumbPart:=proc(Q::list(posint), K::symbol:=nonordered)  # Procedure finds the number of all partitions of a set into subsets of the specific size given  Q

local L, T, P, n, S, N;

uses ListTools;


T:=[seq([L[i],Occurrences(L[i],Q)], i=1..nops(L))];


n:=nops(P);  N:=add(P[i,2], i=1..n);


if K=nonordered then return S else  S*N! fi;

end proc:


Examples of use:

SetPartition({a,b,c,d,e}, [1,1,3]);  nops(%);  # Nonordered partitions and their number

SetPartition({a,b,c,d,e}, [1,1,3], ordered);  nops(%);  # Ordered partitions and their number



Here's a more interesting example. 5 fruits  {apple, pear, orange, mango, peach}  must be put on three plates so that  on each of two plates there are 2  fruits, and there is one fruit  on one plate. Two variants to solve: 1) plates are indistinguishable and 2) different plates. In how many ways can this be done?

SetPartition({apple,pear,orange,mango,peach}, [1,2,2]);  nops(%);  # plates are indistinguishable


NumbPart([1,2,2], ordered);  # Number of ways for  different plates



Another example - how many ways can be divided  100 objects into 10 equal parts?





Please Wait...