0

I have written the following code that returns all possible ways to represent a certain amount of money using coins in a currency with a certain set of coin values:

IEnumerable<IEnumerable<int>> getCoins(int price)
{
    int[] coinValues = new int[] { 1, 2, 5, 10, 20, 50, 100, 200 }; // Coin values
    if (coinValues.Contains(price)) yield return new int[] { price }; // If the price can be represented be a single coin

    // For every coin that is smaller than the price, take it away, call the function recursively and concatenate it later
    foreach (int coin in coinValues.Where(x => x < price))
        foreach (IEnumerable<int> match in getCoins(price - coin))
            yield return match.Concat(new int[] { coin });
}

This works fine, but for instance for price = 3 it treats {1c, 2c} and {2c, 1c} as two different representations. That issue can be resolved by storing all found values in a List and then remove duplicates when they are generated, but that way the generator nature of the code is sacrificed. Can the code be modified to not include duplicates while still being a generator using yield return?

Improve this question
2
  • 2
    You should just generate sorted arrays to start with. Commented May 1, 2013 at 16:37
  • Just as a side note, I would recommend moving the coinValues to a static readonly array rather then recreating it in every time getCoins is called. Commented May 1, 2013 at 17:38

5 Answers 5

Reset to default
2

You could not allow any coin that is bigger then one already in the array.

public IEnumerable<IEnumerable<int>> getCoins(int price)
{
   int[] coinValues = new int[] { 1, 2, 5, 10, 20, 50, 100, 200 }; // Coin values
   if (coinValues.Contains(price))
      yield return new int[] { price }; // If the price can be represented be a single coin

   // For every coin that is smaller than the price, take it away, call the function recursively and concatenate it later
   foreach (int coin in coinValues.Where(x => x < price))
      foreach (IEnumerable<int> match in getCoins(price - coin))
         if (match.Min() >= coin)
            yield return match.Concat(new int[] { coin });
}

Edit: This has the added benefit of producing sorted arrays. However, the lists are not generated in lexicographic order.

3 results in:

  • 2 1
  • 1 1 1

5 results in:

  • 5
  • 2 1 1 1
  • 1 1 1 1 1
  • 2 2 1
Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Just pointing out that you missed a 1 at 1111, should be 11111, but we know it works ;).
0

As the other answers mentioned, you can make sure you only add coins in descending order. This should work, but it adds an extra parameter for the last coin added instead of using Min().

IEnumerable<IEnumerable<int>> getCoins(int price, int prev_coin)
{
    int[] coinValues = new int[] { 1, 2, 5, 10, 20, 50, 100, 200 }; // Coin values
    if (coinValues.Contains(price)) yield return new int[] { price }; // If the price can be represented be a single coin

    // For every coin that is smaller than the price, take it away, call the function recursively and concatenate it later
    foreach (int coin in coinValues.Where(x => (x < price && x <= prev_coin)))
        foreach (IEnumerable<int> match in getCoins(price - coin, coin))
            yield return match.Concat(new int[] { coin });
}
Improve this answer

1 Comment

This answer produces the incorrect result of {2,1}, {1,1,1} and {1,2} for getCoins(3, 200). It doesn't have the additional check for price <= prev_coin in the if statement on the second line of the function. See my solution below.
0

The problem is, as noted, your implementation enforces order so {1c, 2c} and {2c, 1c} are in fact not equal. Trying to remove them from the outer IEnumerable will likely not work/will be difficult to make work, instead you should attempt to prevent them from being added in the first place. You could do this by adding a check so that you only add coins in descending order. Another alternative would be use set operation which I haven't done in C# but sets have no notion of order so if those two values were sets they would be considered equal.

Improve this answer

Comments

0

You need to only add coins if they're not greater than the last coin added:

    IEnumerable<IEnumerable<int>> getCoins(int price){
        return getCoins(price, Int32.MaxValue);
    }

    IEnumerable<IEnumerable<int>> getCoins(int price, int lastValue)
    {
        int[] coinValues = new int[] { 1, 2, 5, 10, 20, 50, 100, 200 }; // Coin values
        if (coinValues.Contains(price) && price <= lastValue) yield return new int[] { price }; // If the price can be represented be a single coin

        // For every coin that is smaller than the price, take it away, call the function recursively and concatenate it later  
        foreach (int coin in coinValues.Where(x => x < price && x <= lastValue))
            foreach (IEnumerable<int> match in getCoins(price - coin, coin))
                yield return match.Concat(new int[] { coin });
    }
Improve this answer

Comments

0

Slight improvements over DavidN's in my opinion since it is sorted naturally. (Sorry, I like brackets.) 

    public IEnumerable<IEnumerable<int>> getCoins(int price, int MaxCoin = 200)
    {
        int[] coinValues = new int[] { 1, 2, 5, 10, 20, 50, 100, 200 }.Reverse().ToArray(); // Coin values

        foreach (int coin in coinValues.Where(x => x <= price && x <= MaxCoin))
        {
            if (coin == price)
            {
                yield return new int[] { price }; // If the price can be represented be a single coin
            }
            else
            {
                foreach (IEnumerable<int> match in getCoins(price - coin, coin))
                {
                    yield return new int[] { coin }.Concat(match);
                }
            }
        }
    }
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.