如何按总和的升序遍历所有大小为 K 的子集合。

Question

假设我有一个排序数组，例如

int[] sarr = new int[] { 0, 1, 3, 5 };

我想按总和的升序遍历大小 K 的所有组合。例如，如果 K=2 那么组合的顺序是

{0, 1} (sum = 1)
{1, 0} (sum = 1)
{0, 3} (sum = 3)
{3, 0} (sum = 3)
{3, 1} (sum = 4)
{1, 3} (sum = 4)
{5, 0} (sum = 5)
.
.
.

我想在不先获取所有组合的情况下执行此操作，因为我想在找到满足条件 Func<int[],bool> cond 的组合后立即停止。

有没有已知的方法可以做到这一点？

Answer 1

我会使用 yield return 来描述所有组合、排列或您想要生成的任何子集合，然后对结果使用 FirstOrDefault。

这样一来，如果没有您正在寻找的子集，或者您正在寻找的子集是最后一个，您将只生成所有子集。

关于让它们按元素总和升序排列，对初始集合进行排序，然后从头到尾选择 k 个元素。您甚至可以生成组合，并从中生成所有可能的排列，因此您将获得所有安排。

获取所有组合的快速方法：

class Program
{
    static void Main(string[] args)
    {
        var initialArray = new[] { 0, 1, 3, 5 };
        var subArrayLength = 2;

        foreach (var subArray in GetSubArrays(initialArray, subArrayLength))
            Console.WriteLine($"[{string.Join(", ", subArray)}]");

        Console.WriteLine("Searching for array that contains both 1 and 5.");
        var arrayFulfillingCriteria = GetSubArrays(initialArray, subArrayLength).FirstOrDefault(array => array.Contains(1) && array.Contains(5));
        if (arrayFulfillingCriteria != null)
            Console.WriteLine($"[{string.Join(", ", arrayFulfillingCriteria)}]");
        else
            Console.WriteLine("No array found.");
    }

    static IEnumerable<int[]> GetSubArrays(int[] initialArray, int subArrayLength)
    {
        var indexStack = new Stack<int>(Enumerable.Range(0, subArrayLength));

        do
        {
            var subArray = indexStack.Select(i => initialArray[i]).Reverse().ToArray();
            yield return subArray;

            var index = indexStack.Pop();
            while (indexStack.Count != 0 && indexStack.Count < subArrayLength && index == initialArray.Length - (subArrayLength - indexStack.Count))
                index = indexStack.Pop();

            while (indexStack.Count < subArrayLength && index < initialArray.Length - (subArrayLength - indexStack.Count))
            {
                index++;
                indexStack.Push(index);
            }
        }
        while (indexStack.Count != 0);
    }
}

我能想到你需要安排的唯一原因（当你按总和排序时）是子数组中的项目需要按特定顺序排列。

Answer 2

这对你有用吗？

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

现在，鉴于此：

Func<int[],bool> cond = xs => true;

int[] sarr = new int[] { 0, 1, 3, 5, }; 

var result =
    getAllSubsets(sarr)
        .Where(xs => xs.Count() == 2)
        .Where(xs => cond(xs.ToArray()));

我得到的结果是：

{0, 1} 
{0, 3} 
{1, 3} 
{0, 5} 
{1, 5} 
{3, 5}

如何按总和的升序遍历所有大小为 K 的子集合。

How to iterate through all subcollections of size K, in ascending order of their sums.

c#

sorting

algorithm

performance

complexity-theory