查找可以从数组中按升序排列的数字之和形成的数字

Question

我试图找到所有可能的值，这些值是给定数组值之和的结果。例如，如果给定数组是a=[50,100,120,260,360]，那么结果将是[0,50,100,120,150,170,200,220,240,250,260，......]。如何实现它？

我找到了一篇与之相关的文章，但这篇文章即将找到无法使用给定数组形成的值。

查找不能由给定数组的值形成的最小数

我发现还有一个讨论与此相关，但都是关于数学的，我仍然无法理解如何实现它。你可以看一看，找到所有可能的值，这些值可以使用一些值形成

C#中的任何算法或任何代码都可以提供帮助。

编辑

我们可以多次使用单个值。

更多结果可能是270（50*1100*1120）、300（100*3）、310（50*1260*1）等。

Answer 1

 var repeat = 8;
 int[] source = new int[] {
     50, 100, 120, 260, 360
 };
 List < int > results = new List < int > ();
 for (int i = 0; i < Math.Pow(repeat, source.Length); i++) {
     var sum = 0;
     var bin = Convert.ToString(i, repeat);
     for (var j = 0; j < bin.Length; j++) {
         var pos = int.Parse(bin[j].ToString());
         if (0 < pos) {
             sum += source[j] * pos;
         }
     }
     results.Add(sum);
 }
 Console.WriteLine(results.Union(source).Distinct().OrderBy(x = > x));

Answer 2

使用类似这样的方法找到数组的所有子集，然后求和，如果不需要重复的值，则可以得到所有可能的值。

 int[] source = new int[] { 50,100,120,260,360 };
 for (int i = 0; i < Math.Pow(2, source.Length); i++)
 {
     int[] combination = new int[source.Length];
     for (int j = 0; j < source.Length; j++)
     {
         if ((i & (1 << (source.Length - j - 1))) != 0)
         {
             combination[j] = source[j];
         }
    }
    Console.WriteLine("[{0}, {1}, {2}]", combination[0], combination[1], combination[2]);
}

Answer 3

这是我使用的：

Func<IEnumerable<int>, IEnumerable<IEnumerable<int>>> getAllSubsets = null;
getAllSubsets = xs =>
    (xs == null || !xs.Any())
        ? Enumerable.Empty<IEnumerable<int>>()
        : xs.Skip(1).Any()
            ? getAllSubsets(xs.Skip(1))
                .SelectMany(ys => new[] { ys, xs.Take(1).Concat(ys) })
            : new[] { Enumerable.Empty<int>(), xs.Take(1) };

然后你可以这样做：

var a = new [] { 50, 100, 120, 260, 360 };

Console.WriteLine(String.Join(", ", getAllSubsets(a).Select(x => x.Sum()).OrderBy(x => x)));

我得到这个：

0, 50, 100, 120, 150, 170, 220, 260, 270, 310, 360, 360, 380, 410, 410, 430, 460, 480, 480, 510, 530, 530, 580, 620, 630, 670, 720, 740, 770, 790, 840, 890

知道价值观可以重复，那么这就是一条路：

public IEnumerable<int> GenerateAllSums(int[] array)
{
    var buffer = new LinkedList<int>();
    buffer.AddFirst(0);
    while (true)
    {
        var first = buffer.First;
        var nexts = array.Select(a => first.Value + a);
        foreach (var next in nexts)
        {
            var x = buffer.First;
            while (x.Value < next)
            {
                x = x.Next;
                if (x == null)
                {
                    break;
                }
            }
            if (x == null)
            {
                buffer.AddLast(next);
            }
            else if (x.Value != next)
            {
                buffer.AddBefore(x, next);
            }
        }
        buffer.RemoveFirst();
        yield return first.Value;
    }
}

我可以这样称呼它：

var a = new [] { 50, 100, 120, 260, 360, };

Console.WriteLine(String.Join(", ", GenerateAllSums(a).Take(100)));

重要的是要注意。采取（...）现在至关重要，因为序列是无限的。

给定。取（100）我得到这个结果：

0, 50, 100, 120, 150, 170, 200, 220, 240, 250, 260, 270, 290, 300, 310, 320, 340, 350, 360, 370, 380, 390, 400, 410, 420, 430, 440, 450, 460, 470, 480, 490, 500, 510, 520, 530, 540, 550, 560, 570, 580, 590, 600, 610, 620, 630, 640, 650, 660, 670, 680, 690, 700, 710, 720, 730, 740, 750, 760, 770, 780, 790, 800, 810, 820, 830, 840, 850, 860, 870, 880, 890, 900, 910, 920, 930, 940, 950, 960, 970, 980, 990, 1000, 1010, 1020, 1030, 1040, 1050, 1060, 1070, 1080, 1090, 1100, 1110, 1120, 1130, 1140, 1150, 1160, 1170