对确定的所有非递归算法从一组数字可以概括 [英] Non-recursive algorithm for determine all sums possible from set of numbers

问题描述

我在寻找一个非递归算法（最好在C＃），这将产生一组正数的可能的所有款项的清单。

I'm looking for a non-recursive algorithm (preferably in C#) which will generate a list of all sums possible from a set of positive numbers.

例如。对于一组三个数字1,2,3以下七个款项是可能的：

E.g. For a set of three numbers "1,2,3" the following seven sums are possible:

1

2

3

1 + 2 = 3

1+2=3

1 + 3 = 4

1+3=4

2 + 3 = 5

2+3=5

1 + 2 + 3 = 6

1+2+3=6

的最大集大小将是我周围50.知道如何递归处理这个问题，但已被处理类似的问题时，在过去的通过调用堆栈限定，所以要避免这一次。

The maximum set size would be around 50. I know how to approach this problem recursively, but have been limited by the call stack in the past when tackling a similar problem, so want to avoid it this time.

推荐答案

如果您只是需要所有可能的总和，那么你可以使用此功能。

If you just need all possible sums then you can use this function.

public static IEnumerable<int> GetSums(List<int> list)
{
    return from m in Enumerable.Range(0, 1 << list.Count)
           select
               (from i in Enumerable.Range(0, list.Count)
               where (m & (1 << i)) != 0
               select list[i]).Sum();
}

和，然后只是把它这样的：

And, then just call it like that:

var result = GetSums(myList).ToList();

其他信息的

Additional information:

您也可以使用这种方法生成的组合（源） ：

You can also use this method for generating combinations(source):

public static IEnumerable<IEnumerable<T>> GetPowerSet<T>(List<T> list)
{
    return from m in Enumerable.Range(0, 1 << list.Count)
           select
               from i in Enumerable.Range(0, list.Count)
               where (m & (1 << i)) != 0
               select list[i];
}

和发现所有组合的总和与总和（）从 System.Linq的命名方式：

And find the sums of all combinations with the help of Sum() method from the System.Linq namespace:

var result = GetPowerSet(myList).Select(x => x.Sum()).ToList();

这篇关于对确定的所有非递归算法从一组数字可以概括的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！