# Development Permutations

Discussion in 'Software' started by ManStrike, 23 Mar 2004.

1. ### ManStrikeWhat's a Dremel?

Joined:
29 Jan 2002
Posts:
58
0
I have made a programme that uses backtracking to find the optimal solution to calculate the change for a given amount using 1, 2, 5, 10, 20, 50, 100 denominations.

So for 9 pence it would return 5, 2, and 2.
And for 51 it would be 50 and 1.

What I need to know is how to calculate the number of different permutations there are for say 9 or 51 pence using the denominations above.

2. ### DeXMube Codder

Joined:
22 Jul 2002
Posts:
4,152
3
Use recursion.

Loop through each demonination smaller than or equal to the given amount and print them on the screen somehow. Then subtract the denomination from the amount and repeat the process until the amount is zero.

Here's some pseudo code. It assmues the denominations are stored in an array called denominations:

Code:
```
function printPermutations(int amount) {
for each denominations as coin {
if (coin <= amount) {
print coin;
printPermutations(amount - coin);
}
}
}

```
I'm not certain this algorithm will work as I have no way to test it. Let me know how you get on.

3. ### Bogomip... Yo Momma

Joined:
15 Jun 2002
Posts:
5,161
39
very nice algorthm there dex. I tryed it, itworks, with an exception that the foreach wont work, as when it breaks back it will still have the old amount, and carry on, then it spills out lots of garbage, you need to set a variable to tell it to stop when it has a value...

http://www.sweeto.co.uk/perms.php

PHP:
``` <h1>Bogopimps Currencyerator using DeX's hybrid recursion algorithm!</h1> <form name="amount" action="perms.php" method="post"> <input type="text" name="amount" value="76"> <input type="submit" name="submit" value="Numberate!"> </form> <BR><BR> <?PHP     money(\$amount+1,0);     function money(\$amount,\$total) {         \$denomination[0] = 200;         \$denomination[1] = 100;         \$denomination[2] = 50;         \$denomination[3] = 20;         \$denomination[4] = 10;         \$denomination[5] = 5;         \$denomination[6] = 2;         \$denomination[7] = 1;         \$number = 0;         \$pie = "nooo";         while (\$pie != "yeah") {             if(\$denomination[\$number] < \$amount) {                 if((\$total + \$denomination[\$number]) == \$total) {                     die;                 }                 else {                     print \$denomination[\$number]." pence - Total: ".(\$total + \$denomination[\$number])." pence<BR>";                     money((\$amount - \$denomination[\$number]),(\$total + \$denomination[\$number]));                     \$pie = "yeah";                 }             }             \$number++;         }     } ?> ```
It may be a bit sloppy

edit: oh wait, but he needs to know the number of possible denominations!? sorry

hmmmmm, im pretty sure this would be a binomial expansion of some sort but i cannot think of how. You need to normalise the data somehow, make it straight numbers NOT currency! :-/

or for example if you had 1p,2p,3p,4p coints etc you could use a factorial thing to find it, nice n easy, but its the coins denominations which screw it up.

I may even edge toward there being no mathematical formula for it, and that its only numerical methods (clever guessing basically) which could do it. http://www.numerical-methods.com/ looks pretty hopeful for info on some numerical data!

Hope any of this has helped!

Last edited: 5 Apr 2004
4. ### ManStrikeWhat's a Dremel?

Joined:
29 Jan 2002
Posts:
58
0
Thanks I’m thinking there is also no mathematical formula for it, its stumped every one I have asked but I will look into this numerical methods.

This is my implementation

Code:
```
/*
* Created on 18-Mar-2004
*
*/

/**
* @author Ross Merrigan
*
*/
import java.util.Vector;

public class Backtracking {

private int iPurchase, iLength, iValue[], iComp;

// Constructor
public Backtracking(int inValue[])
{
iPurchase = 0;
iValue = inValue;
}

// Set's ==================================================================
public void setChange(int inChange)
{
iPurchase = inChange;
}

public void setCoins(int inValue[])
{
iValue = inValue;
}

// Get's ==================================================================
public Vector getChange()
{
iComp = 0;
iLength = iPurchase;
return change(iPurchase, iLength);
}

public int[] getCoins()
{
return iValue;
}

public int getComp()
{
return iComp;
}

// ========================================================================

// Recursion Backtracking
private Vector change(int inPurchase, int inLength)
{
// Holds the current solution to check agenst
Vector vCheck = new Vector();
// Holds the shortest solution found
Vector vSolution = new Vector();
// Stops it if this permutations is longer or equal then the best found yet
if (inLength > 1)
{
// No match so use recursion to reduce the problem
for (int x = iValue.length-1; x > -1; x--)
{
if (iValue[x] < inPurchase)
{
// Stop a memory error and some bug in recursion
vCheck.clear();
// Finds a new possible solution and returns it
vCheck = newVector(vCheck, change(inPurchase - iValue[x], inLength-1));
iComp++;
// Checks to make shore that it did return data
if (vCheck.size() > 0)
{
// Adds the current coin to the possible solution
Change money = new Change(iValue[x]);
}
// Does a check at the start to make shore vSolution has data
if (vSolution.isEmpty())
{
// Best permutations found yet
vSolution = newVector(vSolution, vCheck);
inLength = vSolution.size();
}
// If vSolution has coins in it compares it to vCheck's coins
if (vCheck.isEmpty() == false)
{
// If the vCheck coins are shortest in length make vSolution equal to vCheck
if (vCheck.size() < vSolution.size())
{
vSolution.clear();
// Best permutations found yet
vSolution = newVector(vSolution, vCheck);
inLength = vSolution.size();
}
}
}
if (iValue[x] == inPurchase)
{
Change money = new Change(iValue[x]);
iComp++;
break;
}
}
}
return vSolution;
}

// Makes two vectors into one
private Vector newVector(Vector inFirst, Vector inLast)
{
for (int y = inLast.size()-1; y > -1; y--)
{
}
return inFirst;
}
}

```

5. ### DeXMube Codder

Joined:
22 Jul 2002
Posts:
4,152
3
Yeah ok, I just tested my algorithm with javascript and it doesn't work. If only I had java or vb at hand I might be able to figure out what it's doing/not doing.

6. ### MaxWizWhat's a Dremel?

Joined:
1 Oct 2003
Posts:
57
1
Your original question asked for a way to calculate ALL possible permutations.

I made this crude recursive algorithm just to pump out a list so I could have a look for patterns etc.

I can't find any obvious patterns or quick ways to calculate this, so I figured you might find the code useful Its written in Maple (should read almost like pseudo code).

Code:
```>pennys:=proc(x)
return 1;
end:
>twos:=proc(x)
if x >= 0 then return twos(x-2) + pennys(x);
else return 0;
end if;
end:
>fives:=proc(x)
if x >= 0 then return fives(x-5) + twos(x);
else return 0;
end if;
end:
>tens:=proc(x)
if x >= 0 then return tens(x-10) + fives(x);
else return 0;
end if;
end:
>twentys:=proc(x)
if x >= 0 then return twentys(x-20) + tens(x);
else return 0;
end if;
end:
>fiftys:=proc(x)
if x >= 0 then return fiftys(x-50) + twentys(x);
else return 0;
end if;
end:
>change:=proc(x)
if x >= 0 then return change(x-100) + fiftys(x);
else return 0;
end if;
end:```
So the command change(x) calls fiftys which calls twentys which calls tens etc.

e.g. change(9) returns 8, thats eight ways to make 9 pence using those coins. It counts them in the following order

Code:
```522
5211
51111
22221
222111
2211111
21111111
111111111```
I then iterated the change(x) command to get my list

Code:
```>listchange:=proc(n)
local i;
for i to n do print(i,change(i))
end do;
end:
>listchange(100)
1, 1
2, 2
3, 2
4, 3
5, 4
6, 5
7, 6
8, 7
9, 8
10, 11
11, 12
12, 15
13, 16
14, 19
15, 22
16, 25
17, 28
18, 31
19, 34
20, 41
21, 44
22, 51
23, 54
24, 61
25, 68
26, 75
27, 82
28, 89
29, 96
30, 109
31, 116
32, 129
33, 136
34, 149
35, 162
36, 175
37, 188
38, 201
39, 214
40, 236
41, 249
42, 271
43, 284
44, 306
45, 328
46, 350
47, 372
48, 394
49, 416
50, 451
51, 473
52, 508
53, 530
54, 565
55, 600
56, 635
57, 670
58, 705
59, 740
60, 793
61, 828
62, 881
63, 916
64, 969
65, 1022
66, 1075
67, 1128
68, 1181
69, 1234
70, 1311
71, 1364
72, 1441
73, 1494
74, 1571
75, 1648
76, 1725
77, 1802
78, 1879
79, 1956
80, 2064
81, 2141
82, 2249
83, 2326
84, 2434
85, 2542
86, 2650
87, 2758
88, 2866
89, 2974
90, 3121
91, 3229
92, 3376
93, 3484
94, 3631
95, 3778
96, 3925
97, 4072
98, 4219
99, 4366
100, 4563```
Quite a big number that, 4563 ways to make a quid! If you are interested these are the values for £1, £2, £3, £4 & £5.
Code:
```change(100) = 4563
change(200) = 73681
change(300) = 466800
change(400) = 1886815
change(500) = 5824071```
Why didn't you want to include the £2 coin?

Max

7. ### MaxWizWhat's a Dremel?

Joined:
1 Oct 2003
Posts:
57
1
If you want a function to generate these numbers you can try this

Notice that the coefficients of the expanded polynomial ARE the number of ways of making the required change!

So if you want to know how many ways to make £1, you need to calculate 100 terms of the expansion. This is quite easy to program, let me know if your interested in this approach.

It is easy to explain how to program this method, but difficult to explain how the method works (mathematically it is quite sophisticated).

I am working on another even simpler approach

Max

Joined:
29 Jan 2002
Posts:
58