Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.soft-sys.math.mathematica > #12059 > unrolled thread

sum of coins article in mathematica journal

Started byvon dremel <peweijnitz@gmail.com>
First post2012-10-13 05:06 +0000
Last post2012-10-16 07:25 +0000
Articles 4 — 3 participants

Back to article view | Back to comp.soft-sys.math.mathematica


Contents

  sum of coins article in mathematica journal von dremel <peweijnitz@gmail.com> - 2012-10-13 05:06 +0000
    Re: sum of coins article in mathematica journal daniel.lichtblau0@gmail.com - 2012-10-14 04:22 +0000
    Re: sum of coins article in mathematica journal Bob Hanlon <hanlonr357@gmail.com> - 2012-10-15 03:48 +0000
    Re: sum of coins article in mathematica journal Bob Hanlon <hanlonr357@gmail.com> - 2012-10-16 07:25 +0000

#12059 — sum of coins article in mathematica journal

Fromvon dremel <peweijnitz@gmail.com>
Date2012-10-13 05:06 +0000
Subjectsum of coins article in mathematica journal
Message-ID<k5assc$noo$1@smc.vnet.net>
a long time ago I read a short text in mathematica journal.
A neat little program that calculated the numer of coins needed to reach a certain sum. you put in the coin values e.g. 25 cent 50 cent etc and got the minimum anount of how many coins you need.
I think Allan Hayes wrote it.
does anyone have a pointer to it please?

Peter W

[toc] | [next] | [standalone]


#12071

Fromdaniel.lichtblau0@gmail.com
Date2012-10-14 04:22 +0000
Message-ID<k5demq$sfr$1@smc.vnet.net>
In reply to#12059
On Saturday, October 13, 2012 12:08:01 AM UTC-5, von dremel wrote:
> a long time ago I read a short text in mathematica journal.
>
> A neat little program that calculated the numer of coins needed to reach a certain sum. you put in the coin values e.g. 25 cent 50 cent etc and got the minimum anount of how many coins you need.
>
> I think Allan Hayes wrote it.
>
> does anyone have a pointer to it please?
>
>
> Peter W

You might try looking in library.wolfram.com. I believe (some? many?) back issues of TMJ are archived there.

If I'm not mistaken, the method involves looking at a coefficient of 1/((1-x[1]*t)*(1-x[5]^t^5)*(1-x[10]*t^10)*(1-x[25]*t^25)*(1-x[50]*t^50)) expanded at the origin. Specifically, to make j cents in total change, look at the jth coefficient. Find the summand that uses smallest total powers of x[k]s.

Here is a bit of code for this.

minimalChange[coins_, amount_] := Module[
  {len = Length[coins], mu, mus, x, ratfun, coeff, totals, bestpos},
  mus = Map[mu, coins];
  ratfun = Times @@ (1/Table[1 - mus[[j]]*x^coins[[j]], {j, len}]);
  coeff = (List @@
     Expand[SeriesCoefficient[ratfun, {x, 0, amount}]]);
  coeff = coeff /. Times -> Plus;
  totals = Map[# /. mu[_]^j_. :> j &, coeff];
  bestpos = Ordering[totals, 1];
  coeff[[bestpos]] /. Plus -> List /. mu[k_]^j_. :> {k, j}
  ]

Example:

coins = {1, 5, 10, 25, 50};

In[339]:= minimalChange[coins, 247]

Out[339]= {{{1, 2}, {10, 2}, {25, 1}, {50, 4}}}

So 4 50 cent pieces, 1 quarter, 2 dimes, two pennies. No surprises here.

I think this is a bit slow. There may be a more efficient way to get at the=
 relevant series term.

I should allso note that the "obvious" greedy method does not work on all p=
ossible coin sets.

In[341]:= minimalChange[{4, 7, 11, 23}, 247]

Out[341]= {{{7, 1}, {11, 3}, {23, 9}}}

Also one can have a tie.

In[353]:= minimalChange[{5, 7, 11, 26}, 377]

Out[353]= {{{7, 4}, {11, 1}, {26, 13}}}

Could instead have had {5,2}, {7,1}, {11,2}, {26,13} for that.

Daniel Lichtblau
Wolfram Research

[toc] | [prev] | [next] | [standalone]


#12075

FromBob Hanlon <hanlonr357@gmail.com>
Date2012-10-15 03:48 +0000
Message-ID<k5g132$3op$1@smc.vnet.net>
In reply to#12059
You can just use Minimize and it will also give you the total number of coins

minimalChange[coins_, amount_] := Module[
  {var = r /@ Range[Length[coins]]},
  Minimize[{Total[var],
     coins.var == amount,
     Thread[var >= 0]},
    var, Integers] /.
   {(r[n_] -> 0) :> Sequence[],
    (r[n_] -> m_) :> {coins[[n]], m}}]

coins = {1, 5, 10, 25, 50};

minimalChange[coins, 247]

{9, {{1, 2}, {10, 2}, {25, 1}, {50, 4}}}

minimalChange[{4, 7, 11, 23}, 247]

{13, {{7, 1}, {11, 3}, {23, 9}}}

minimalChange[{5, 7, 11, 26}, 377]

{18, {{7, 4}, {11, 1}, {26, 13}}}


Bob Hanlon


On Sun, Oct 14, 2012 at 12:15 AM,  <daniel.lichtblau0@gmail.com> wrote:
> On Saturday, October 13, 2012 12:08:01 AM UTC-5, von dremel wrote:
>> a long time ago I read a short text in mathematica journal.
>>
>> A neat little program that calculated the numer of coins needed to reach a certain sum. you put in the coin values e.g. 25 cent 50 cent etc and got the minimum anount of how many coins you need.
>>
>> I think Allan Hayes wrote it.
>>
>> does anyone have a pointer to it please?
>>
>>
>> Peter W
>
> You might try looking in library.wolfram.com. I believe (some? many?) back issues of TMJ are archived there.
>
> If I'm not mistaken, the method involves looking at a coefficient of 1/((1-x[1]*t)*(1-x[5]^t^5)*(1-x[10]*t^10)*(1-x[25]*t^25)*(1-x[50]*t^50)) expanded at the origin. Specifically, to make j cents in total change, look at the jth coefficient. Find the summand that uses smallest total powers of x[k]s.
>
> Here is a bit of code for this.
>
> minimalChange[coins_, amount_] := Module[
>   {len = Length[coins], mu, mus, x, ratfun, coeff, totals, bestpos},
>   mus = Map[mu, coins];
>   ratfun = Times @@ (1/Table[1 - mus[[j]]*x^coins[[j]], {j, len}]);
>   coeff = (List @@
>      Expand[SeriesCoefficient[ratfun, {x, 0, amount}]]);
>   coeff = coeff /. Times -> Plus;
>   totals = Map[# /. mu[_]^j_. :> j &, coeff];
>   bestpos = Ordering[totals, 1];
>   coeff[[bestpos]] /. Plus -> List /. mu[k_]^j_. :> {k, j}
>   ]
>
> Example:
>
> coins = {1, 5, 10, 25, 50};
>
> In[339]:= minimalChange[coins, 247]
>
> Out[339]= {{{1, 2}, {10, 2}, {25, 1}, {50, 4}}}
>
> So 4 50 cent pieces, 1 quarter, 2 dimes, two pennies. No surprises here.
>
> I think this is a bit slow. There may be a more efficient way to get at the relevant series term.
>
> I should allso note that the "obvious" greedy method does not work on all possible coin sets.
>
> In[341]:= minimalChange[{4, 7, 11, 23}, 247]
>
> Out[341]= {{{7, 1}, {11, 3}, {23, 9}}}
>
> Also one can have a tie.
>
> In[353]:= minimalChange[{5, 7, 11, 26}, 377]
>
> Out[353]= {{{7, 4}, {11, 1}, {26, 13}}}
>
> Could instead have had {5,2}, {7,1}, {11,2}, {26,13} for that.
>
> Daniel Lichtblau
> Wolfram Research
>

[toc] | [prev] | [next] | [standalone]


#12080

FromBob Hanlon <hanlonr357@gmail.com>
Date2012-10-16 07:25 +0000
Message-ID<k5j24q$8r1$1@smc.vnet.net>
In reply to#12059
You can add the use of Reduce to see multiple equivalent results:

minimalChange[coins_, amount_] :=
 Module[
  {var = r /@ Range[Length[coins]], cnt},
  cnt = Minimize[{Total[var],
      coins.var == amount,
      Thread[var >= 0]},
     var, Integers][[1]];
  {cnt, {Reduce[Flatten[
        {Total[var] == cnt,
         coins.var == amount,
         Thread[var >= 0]}],
       var, Integers] //
      ToRules}} /. {
    (r[n_] -> 0) :> Sequence[],
    (r[n_] -> m_) :> {coins[[n]], m}}]

minimalChange[{5, 7, 11, 26}, 377]

{18, {{{7, 4}, {11, 1}, {26, 13}}, {{5, 2}, {7, 1}, {11, 2}, {26,
    13}}}}

minimalChange[{4, 7, 11, 23}, 499]

{25, {{{7, 1}, {11, 5}, {23, 19}}, {{7, 4}, {11, 1}, {23, 20}}, {{4,
    4}, {23, 21}}}}


Bob Hanlon


On Sun, Oct 14, 2012 at 11:41 PM, Bob Hanlon <hanlonr357@gmail.com> wrote:
> You can just use Minimize and it will also give you the total number of coins
>
> minimalChange[coins_, amount_] := Module[
>   {var = r /@ Range[Length[coins]]},
>   Minimize[{Total[var],
>      coins.var == amount,
>      Thread[var >= 0]},
>     var, Integers] /.
>    {(r[n_] -> 0) :> Sequence[],
>     (r[n_] -> m_) :> {coins[[n]], m}}]
>
> coins = {1, 5, 10, 25, 50};
>
> minimalChange[coins, 247]
>
> {9, {{1, 2}, {10, 2}, {25, 1}, {50, 4}}}
>
> minimalChange[{4, 7, 11, 23}, 247]
>
> {13, {{7, 1}, {11, 3}, {23, 9}}}
>
> minimalChange[{5, 7, 11, 26}, 377]
>
> {18, {{7, 4}, {11, 1}, {26, 13}}}
>
>
> Bob Hanlon
>
>
> On Sun, Oct 14, 2012 at 12:15 AM,  <daniel.lichtblau0@gmail.com> wrote:
>> On Saturday, October 13, 2012 12:08:01 AM UTC-5, von dremel wrote:
>>> a long time ago I read a short text in mathematica journal.
>>>
>>> A neat little program that calculated the numer of coins needed to reac=
h a certain sum. you put in the coin values e.g. 25 cent 50 cent etc and go=
t the minimum anount of how many coins you need.
>>>
>>> I think Allan Hayes wrote it.
>>>
>>> does anyone have a pointer to it please?
>>>
>>>
>>> Peter W
>>
>> You might try looking in library.wolfram.com. I believe (some? many?) back issues of TMJ are archived there.
>>
>> If I'm not mistaken, the method involves looking at a coefficient of 1/((1-x[1]*t)*(1-x[5]^t^5)*(1-x[10]*t^10)*(1-x[25]*t^25)*(1-x[50]*t^50)) expanded at the origin. Specifically, to make j cents in total change, look at the jth coefficient. Find the summand that uses smallest total powers of x[k]s.
>>
>> Here is a bit of code for this.
>>
>> minimalChange[coins_, amount_] := Module[
>>   {len = Length[coins], mu, mus, x, ratfun, coeff, totals, bestpos},
>>   mus = Map[mu, coins];
>>   ratfun = Times @@ (1/Table[1 - mus[[j]]*x^coins[[j]], {j, len}]);
>>   coeff = (List @@
>>      Expand[SeriesCoefficient[ratfun, {x, 0, amount}]]);
>>   coeff = coeff /. Times -> Plus;
>>   totals = Map[# /. mu[_]^j_. :> j &, coeff];
>>   bestpos = Ordering[totals, 1];
>>   coeff[[bestpos]] /. Plus -> List /. mu[k_]^j_. :> {k, j}
>>   ]
>>
>> Example:
>>
>> coins = {1, 5, 10, 25, 50};
>>
>> In[339]:= minimalChange[coins, 247]
>>
>> Out[339]= {{{1, 2}, {10, 2}, {25, 1}, {50, 4}}}
>>
>> So 4 50 cent pieces, 1 quarter, 2 dimes, two pennies. No surprises here.
>>
>> I think this is a bit slow. There may be a more efficient way to get at the relevant series term.
>>
>> I should allso note that the "obvious" greedy method does not work on all possible coin sets.
>>
>> In[341]:= minimalChange[{4, 7, 11, 23}, 247]
>>
>> Out[341]= {{{7, 1}, {11, 3}, {23, 9}}}
>>
>> Also one can have a tie.
>>
>> In[353]:= minimalChange[{5, 7, 11, 26}, 377]
>>
>> Out[353]= {{{7, 4}, {11, 1}, {26, 13}}}
>>
>> Could instead have had {5,2}, {7,1}, {11,2}, {26,13} for that.
>>
>> Daniel Lichtblau
>> Wolfram Research
>>
>

[toc] | [prev] | [standalone]


Back to top | Article view | comp.soft-sys.math.mathematica


csiph-web