递归函数返回重复项

本文关键字：返回 递归函数 | 更新日期: 2023-09-27 18:11:46

我写了下面的代码，返回所有可能的方式来表示一定数量的钱，使用硬币在一种货币中具有一定的硬币值集合:

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

这工作得很好，但例如对于price = 3，它将{1c, 2c}和{2c, 1c}视为两个不同的表示。这个问题可以通过将所有找到的值存储在List中，然后在生成重复的值时删除它们来解决，但是这种方式牺牲了代码的生成器性质。代码可以修改为不包括重复，而仍然是一个生成器使用yield return ?

递归函数返回重复项

你不能允许任何硬币大于数组中的硬币

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

编辑:这有产生排序数组的额外好处。但是，这些列表不是按字典顺序生成的。

3 result in:

  • 2 1

5 result in:

    5
  • 2 1 1 1
  • 1 1 1 1 1
  • 2 2 1

正如前面提到的其他答案，您可以确保只按降序添加硬币。这应该可以工作，但它为最后添加的硬币添加了一个额外的参数，而不是使用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 });
}

问题是，如前所述，您的实现强制执行顺序，因此{1c, 2c}和{2c, 1c}实际上不相等。试图从外部IEnumerable中删除它们可能不起作用/很难使其起作用，相反，您应该首先尝试阻止它们被添加。您可以通过添加检查来实现这一点，这样您只能按降序添加硬币。另一种选择是使用集合操作，我在c#中没有这样做，但是集合没有顺序的概念，所以如果这两个值是集合，它们将被认为是相等的。

您只需要添加硬币，如果它们不大于最后添加的硬币:

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

我认为比DavidN的稍微改进，因为它是自然排序的。(对不起，我喜欢括号)

    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);
                }
            }
        }
    }
相关文章：