Making Change

Making Change with Coins
(%i1) load(basic)$

(%i2) powerdisp:true$
Number of terms to count down to in increments of five.
(%i3) Number_of_Terms:50;

Define coins as list of lists with coin name, denomination, and additonal format character for plurals.
(%i4) Coins:[[Quarter,25,""],[Dime,10,""],[Nickel,5,""],[Penn,1,"@"]];

Form formats for string output:
(%i5) fmts:makelist(sconcat("~d ",Coins[j][1],"~:",Coins[j][3],"P~% "),j,1,length(Coins));

Form the generating function.
(%i6) FD:1$
(%i7) for c in Coins do FD:FD/(1-c[1]*x^c[2])$
(%i8) display(FD);

(%i9) FT:taylor(FD,x,0,Number_of_Terms)$
Taylor series expansion of the generating function, e.g.,
(%i10) taylor(FD,x,0,11);

(%i11) C(n):=expand(coeff(taylor(FD,x,0,n),x,n))$
Grab the n-th coefficient, e.g.,
(%i12) display(C(10));

Create list of terms in reverse order
(%i13) terms(lst):=reverse(maplist(lambda([item],item),lst))$
(%i14) trms:terms((C(10)));

Grab the power of each Coins
(%i15) pwrs(t):=makelist(hipow(t,Coins[l][1]),l,1,length(Coins))$
(%i16) makelist(pwrs(trms[i]),i,1,length(trms));

(%i17) asum(lst):=block(sout:"",for k:1 thru length(Coins) do if lst[k]>0 then sout:sconcat(sout,printf(false,fmts[k],lst[k])),return(sout))$
(%i18) asum([1,0,2,10]);

(%i19) for j:Number_of_Terms step -5 thru Number_of_Terms do
(scoins:[],
tmp:terms(C(j)),
print("There are ",length(tmp)," ways to make change for ",j," cents, namely: "),
for i:1 thru length(tmp) do (
    tmp2:pwrs(tmp[i]),
    push([apply("+",tmp2),asum(tmp2)],scoins)
),
scoins:sort(scoins),
for s in scoins do print(s[2],"")
);

---

Created with wxMaxima.