Quoting Alex Walker to All, 03 Nov 97
about WTD Coin algorithm ideas:
 AW>     I've looked at Permutations and combinations math wise but this
 AW>     method just gives me the number of permutations, not what they
 AW> are.
 AW>     I'm not asking for code, just an idea of how to attack the
 AW> question.
 You could do it by recursing on all possible values. The central function 
would be something like this:
 
#define NUM_COINS 2
int coins[NUM_COINS] = {1,5,10};
char *coinstr[NUM_COINS] = { "1", "5", "10"};
 void permute_change (int amount_left, int last_coin, char *string) {
   int iterator;
   for (iterator = 0 ; iterator < NUM_COINS ; iterator++)
     if (coins[iterator] >= last_coin) {
       int tmp_strlen = strlen (string);
       strcat (string, " + ");
       strcat (string, coinstr[iterator]);
       permute_change (amount_left - coins[iterator], coins[iterator], 
string);
       string[tmp_strlen] = '\0'; /* Restore old string */
     }
   if (amount_left == 0)
     printf ("One way of doing it: %s\n", string)
 }
 
 This approach, however, has two flaws:
 1) The stack usage would be pretty excessive. Thus  if one were to expand
    $100 into onecents (Does such a thing exist?), this would require
    10000 function calls, with a stack usage of at least 24 bytes for each
    call, using something like 234 Kb worth of stack.
 2) This example assumes that the smallest possible coin has the value 1.
    If that's not the case, some care should be taken that the function
    eventually terminates, as it will otherwise go on forever.
 Apart from that, you'll need to make sure that the string is big enough to 
hold the entire expansion.
 Another possible way of doing this, might be a function for each different 
coin, that calls the next in line with all the different amounts of this 
(including 0). An example call-sequence could be (with the 3 smallest Danish 
coins):
 permute_1( 3 )
   -> permute_dot_50 ( 0 )
     -> permute_dot_25 ( 0 ) This is the terminal function, which need to 
print 
                             this: 3 * 1 + 0 * .50 + 0 * .25
   -> permute_dot_50 ( 2 )
     -> permute_dot_25 ( 0 ) => 2 * 1 + 2 * .50 + 0 * .25
     -> permute_dot_25 ( 2 ) => 2 * 1 + 1 * .50 + 2 * .25
     -> permute_dot_25 ( 4 ) => 2 * 1 + 0 * .50 + 4 * .25
   -> permute_dot_50 ( 4 )
     -> permute_dot_25 ( 0 ) => 1 * 1 + 4 * .50 + 0 * .25
     -> permute_dot_25 ( 2 ) => 1 * 1 + 3 * .50 + 2 * .25
     -> permute_dot_25 ( 4 ) => 1 * 1 + 2 * .50 + 4 * .25
     -> permute_dot_25 ( 6 ) => 1 * 1 + 1 * .50 + 6 * .25
     -> permute_dot_25 ( 8 ) => 1 * 1 + 0 * .50 + 8 * .25
   -> permute_dot_50 ( 6 )
     -> permute_dot_25 ( 0 ) => 0 * 1 + 6 * .50 + 0 * .25
     -> permute_dot_25 ( 2 ) => 0 * 1 + 5 * .50 + 2 * .25
     -> permute_dot_25 ( 4 ) => 0 * 1 + 4 * .50 + 4 * .25
     -> permute_dot_25 ( 6 ) => 0 * 1 + 3 * .50 + 6 * .25
     -> permute_dot_25 ( 8 ) => 0 * 1 + 2 * .50 + 8 * .25
     -> permute_dot_25 (10 ) => 0 * 1 + 1 * .50 +10 * .25
     -> permute_dot_25 (12 ) => 0 * 1 + 0 * .50 +12 * .25
 This will lead to a drastic reduction of stack usage, but will need some 
sort of global variable to track the number of different coins.
MVH, 
 Anders Wegge Jakobsen
--- Mail Manager 1.22x/n #1096
---------------