1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

Development Permutations

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

  1. ManStrike

    ManStrike What's a Dremel?

    Joined:
    29 Jan 2002
    Posts:
    58
    Likes Received:
    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. DeX

    DeX Mube Codder

    Joined:
    22 Jul 2002
    Posts:
    4,152
    Likes Received:
    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

    Bogomip ... Yo Momma

    Joined:
    15 Jun 2002
    Posts:
    5,161
    Likes Received:
    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 :p

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

    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. ManStrike

    ManStrike What's a Dremel?

    Joined:
    29 Jan 2002
    Posts:
    58
    Likes Received:
    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]);
    						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;
    	}
    }
    
    
    
     
  5. DeX

    DeX Mube Codder

    Joined:
    22 Jul 2002
    Posts:
    4,152
    Likes Received:
    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. MaxWiz

    MaxWiz What's a Dremel?

    Joined:
    1 Oct 2003
    Posts:
    57
    Likes Received:
    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. MaxWiz

    MaxWiz What's a Dremel?

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

    [​IMG]

    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
     
  8. ManStrike

    ManStrike What's a Dremel?

    Joined:
    29 Jan 2002
    Posts:
    58
    Likes Received:
    0
    Thanks that’s exactly what I was looking for :lol:

    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.
     

Share This Page