CODEWITHSUNDEEP
c#recursion
user2037593
user2037593

Reputation:

Recursive function returns duplicates

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?

Upvotes: 0

Views: 537

Answers (5)

K Kimble
K Kimble

Reputation: 249

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);
                }
            }
        }
    }

Upvotes: 0

Cemafor
Cemafor

Reputation: 1653

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

Upvotes: 2

DavidN
DavidN

Reputation: 5197

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 });
    }

Upvotes: 0

tylert
tylert

Reputation: 301

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 });
}

Upvotes: 0

evanmcdonnal
evanmcdonnal

Reputation: 48134

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.

Upvotes: 0

Related Questions