Wie durchlaufen Sie alle Untersammlungen der Größe K in aufsteigender Reihenfolge ihrer Summen.

Question

Angenommen, ich eine sortierte Array wie

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

und ich möchte durchlaufen alle Kombinationen von Größe K in ansteigender Reihenfolge ihrer Summe haben. Zum Beispiel, wenn K=2 dann sind die Kombinationen, um

{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) 
. 
. 
. 

Ich möchte, dies zu tun, ohne zuerst alle Kombinationen zu bekommen, weil ich so schnell aufhören will, wie ich eine gefunden habe, die eine Bedingung Func<int[],bool> cond erfüllt.

Gibt es einen bekannten Weg, dies zu tun?

Answer 1

Ich würde yield return verwenden, um alle Kombinationen, Anordnungen oder Subskollektionen zu beschreiben, die Sie generieren möchten, und dann FirstOrDefault für das Ergebnis verwenden.

Auf diese Weise werden Sie nur alle Untersammlungen erzeugen, wenn Sie nicht die gesuchte suchen oder die, nach der Sie suchen, die letzte ist.

Um sie aufsteigend nach der Summe der Elemente zu erhalten, sortieren Sie die ursprüngliche Sammlung und wählen Sie dann k Elemente von Anfang bis Ende. Sie können sogar Kombinationen generieren und daraus alle möglichen Permutationen generieren und somit erhalten Sie alle Ihre Arrangements.

Eine schnelle Möglichkeit, alle Kombinationen zu bekommen:

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

Der einzige Grund, warum ich mir vorstellen kann, wo man Vorkehrungen benötigen würde (da Sie von Summe zu bestellen) ist, dass die Elemente innerhalb des Subarray sein müssen in einer bestimmten Reihenfolge.

Answer 2

Funktioniert das für Sie?

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

Jetzt, da dies:

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

ich diese erhalten als das Ergebnis:

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