Как перебрать все подколлекции размера K в порядке возрастания их сумм.

Предположим, у меня есть отсортированный массив, такой как

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.

Есть ли известный способ сделать это?


c# performance sorting algorithm complexity-theory
person user6048670    schedule 31.07.2016    source источник
comment
Просто быть придирчивым, видя, как появляются {0, 1} и {1, 0}, похоже, что вы ищете аранжировки, а не комбинации.   -  person Andrei15193    schedule 31.07.2016

Ответы (2)


arrow_upward
1
arrow_downward

Я бы использовал 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);
    }
}

Единственная причина, по которой я могу придумать, где вам понадобятся договоренности (учитывая, что вы упорядочиваете по сумме), заключается в том, что элементы в подмассиве должны быть в определенном порядке.

person Andrei15193    schedule 31.07.2016

arrow_upward
0
arrow_downward

Это работает для вас?

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}
person Enigmativity    schedule 31.07.2016