## 20454 Reputation

16 years, 64 days

## Partition of an integer with restriction...

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});

## For Valentine's Day....

A heart shape in 3d:

The code of the animation:

A := plots[animate](plot3d, [[16*sin(t)^3*cos(s), 16*sin(t)^3*sin(s), 13*cos(t)-5*cos(2*t)-2*cos(3*t)-cos(4*t)], t = 0 .. u, s = 0 .. 2*Pi, color = red, style = surface, axes = none], u = 0 .. Pi, frames = 100):

B := plots[animate](plot3d, [[16*sin(t)^3*cos(s), 16*sin(t)^3*sin(s), 13*cos(t)-5*cos(2*t)-2*cos(3*t)-cos(4*t)], t = u .. Pi, s = 0 .. 2*Pi, color = "LightBlue", style = surface, axes = none], u = 0 .. Pi, frames = 100):

plots[display](A, B);

Edited. The direction of painting changed.

## Generalization of combinat[composition]...

The well-known  combinat[composition]  command computes and returns a list containing all distinct ordered  k-tuples of positive integers whose elements sum equals  . These are known as the compositions of  n .  For some applications, additional constraints are required for the elements of these k-tuples, for example, that they are within a certain range.

The  Composition  procedure solves this problem. Required parameters:  n - a nonnegative integer, - a positive integer. 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 .  Composition(n,k,1)  is equivalent to  combinat[composition](n,k) .

The code of the procedure:

Composition := proc (n::nonnegint, k::posint, res::{range, nonnegint} := 0)

local a, b, It, L0;

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

if b < a or b*k < n then return `No solutions` 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))] fi;

od;

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

end proc;

L0 := [[]];

(It@@k)(L0);

end proc:

Three simple examples:

Composition(10,3); ``;   # All terms greater than or equal 0

Composition(10,3, 2);   # All terms greater than or equal 2

Composition(10,3, 2..4);   # All terms greater than or equal 2 and less than or equal to 4

A more complex example. The problem - to find all the numbers in the range  1 .. 99999999  whose digits sum is equal to 21 .

Each number is represented by a list of digits from left to right, replacing missing digits at the left with zeros.

M:=Composition(21,8, 0..9):

nops(M);  # The number of solutions

[seq(M[1+100000*i], i=0..9)]; # 10 solutions from the list M starting the first one

seq(add(%[i,k]*10^(8-k), k=1..8),i=1..nops(%));  # Conversion into numbers

Composition.mws

## Games with numbers...

The procedure  NumbersGame  generalizes the well-known 24 game  (implementation in Maple see here), as well as related issues (see here and here).

Required parameters of the procedure:

Result is an integer or a fraction of any sign.

Numbers is a list of positive integers.

Optional parameters:

Operators is a list of permitted arithmetic operations. By default  Operators is  ["+","-","*","/"]

NumbersOrder is a string. It is equal to "strict order" or "arbitrary order" . By default  NumbersOrder is "strict order"

Parentheses is a symbol  no  or  yes . By default  Parentheses is  no

The procedure puts the signs of operations from the list  Operators  between the numbers from  Numbers  so that the result is equal to Result. The procedure finds all possible solutions. The global  M  saves the list of the all solutions.

Code the procedure:

restart;

NumbersGame:=proc(Result::{integer,fraction}, Numbers::list(posint), Operators::list:=["+","-","*","/"], NumbersOrder::string:="strict order", Parentheses::symbol:=no)

local MyHandler, It, K, i, P, S, n, s, L, c;

global M;

uses StringTools, ListTools, combinat;

MyHandler := proc(operator,operands,default_value)

NumericStatus( division_by_zero = false );

return infinity;

end proc;

NumericEventHandler(division_by_zero=MyHandler);

if Parentheses=yes then

It:=proc(L1,L2)

local i, j, L;

for i in L1 do

for j in L2 do

L[i,j]:=seq(Substitute(Substitute(Substitute("( i Op j )","i",convert(i,string)),"j",convert(j,string)),"Op",Operators[k]), k=1..nops(Operators));

od; od;

L:=convert(L, list);

end proc;

P:=proc(L::list)

local n, K, i, M1, M2, S;

n:=nops(L);

if n=1 then return L else

for i to n-1 do

M1:=P(L[1..i]); M2:=P(L[i+1..n]);

K[i]:=seq(seq(It(M1[j], M2[k]), k=1..nops(M2)), j=1..nops(M1))

od; fi;

K:=convert(K,list);

end proc;

if NumbersOrder="arbitrary order" then S:=permute(Numbers); K:=[seq(op(Flatten([op(P(s))])), s=S)] else  K:=[op(Flatten([op(P(Numbers))]))] fi;

else

if NumbersOrder="strict order" then

K:=[convert(Numbers[1],string)];

for i in Numbers[2..-1] do

K:=[seq(seq(cat(k, Substitute(Substitute(" j i","j",convert(j,string)),"i",convert(i,string))), k in K), j in Operators)]

od;   else

S:=permute(Numbers);

for s in S do

L:=[convert(s[1],string)];

for i in s[2..-1] do

L:=[seq(seq(cat(k, Substitute(Substitute(" j i","j",convert(j,string)),"i",convert(i,string))), k in L), j in Operators)]

od; K[s]:=op(L) od; K:=convert(K,list) fi;

fi;

M:='M'; c:=0;

for i in K do

if parse(i)=Result then c:=c+1; if Parentheses=yes then M[i]:= convert(SubString(i,2..length(i)-1),symbol)=convert(Result,symbol) else M[i]:=convert(i,symbol)=convert(Result,symbol) fi; fi;

od;

if c=0 then M:=[]; return `No solutions` else M:=convert(M,list);  op(M) fi;

end proc:

Examples of use.

Example 1:

NumbersGame(1/20, [\$ 1..9]);

1 * 2 - 3 + 4 / 5 / 6 * 7 / 8 * 9 = 1/20

Example 2. Numbers in the list  Numbers  may be repeated and permitted operations can be reduced:

NumbersGame(15, [3,3,5,5,5], ["+","-"]);

3 - 3 + 5 + 5 + 5 = 15

Example 3.

NumbersGame(10, [1,2,3,4,5]);

1 + 2 + 3 * 4 - 5 = 10

If the order of the number in Numbers is arbitrary, then the number of solutions is greatly increased (10 solutions displayed):

NumbersGame(10, [1,2,3,4,5], "arbitrary order"):

nops(M);

for i to 10 do

M[1+50*(i-1)] od;

If you use the parentheses, the number of solutions will increase significantly more (10 solutions displayed):

NumbersGame(10, [1,2,3,4,5], "arbitrary order", yes):

nops(M);

for i to 10 do

M[1+600*(i-1)] od;

Game.mws

## Maple implementation of "24" game...

Maple 12

The procedure  game24  solves the problem. In the procedure Acer's  procedure  MyHandler is  used, which prevents the program to stop in case of 0 in the denominator.

game24:=proc(a,b,c,d)

local MyHandler,It, K, M, i, P;

uses StringTools, combinat;

MyHandler := proc(operator,operands,default_value)

NumericStatus( division_by_zero = false );

return infinity;

end proc;

NumericEventHandler(division_by_zero=MyHandler);

It:=proc(L1,L2)

local i, j, L;

L:=[];

for i in L1 do

for j in L2 do

L:=[op(L), op([Substitute(Substitute("( i + j )","i",convert(i,string)),"j",convert(j,string)),Substitute(Substitute("( i - j )","i",convert(i,string)),"j",convert(j,string)),Substitute(Substitute("( i * j )","i",convert(i,string)),"j",convert(j,string)),Substitute(Substitute("( i / j )","i",convert(i,string)),"j",convert(j,string))])];

od; od;

L;

end proc;

P:=permute([a,b,c,d]);

K:=[];

for i in P do

K:=[op(K),op(It(It(It([i[1]],[i[2]]),[i[3]]),[i[4]])), op(It(It([i[1]],It([i[2]],[i[3]])),[i[4]])), op(It([i[1]],It(It([i[2]],[i[3]]),[i[4]]))), op(It([i[1]],It([i[2]],It([i[3]],[i[4]])))), op(It(It([i[1]],[i[2]]),It([i[3]],[i[4]])))];

od;

M:=[];

for i in K do

if parse(i)=24 then M:=[op(M), i] fi;

od;

if nops(M)=0 then return `No solutions` else

for i in M do

print(SubString(i,2..length(i)-1));

od; fi;

end proc:

Two examples:

game24(2,3,8,9);

game24(2,3,3,4);

No solutions

24.mws

 5 6 7 8 9 10 11 Page 7 of 11
﻿