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.
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.
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!
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]); vCheck.add(money); } // 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]); vSolution.add(money); 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--) { inFirst.add(inLast.elementAt(y)); } return inFirst; } }
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.
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
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
Thanks that’s exactly what I was looking for I would be very interested in seeing how to code this out as I’m not to hot on maths. And I totally forgot about the £2 coin, I don’t see them that often enough to remember about them.
