사이즈 K의 모든 서브 콜렉션을, 그 합계의 오름차순으로 반복하는 방법.

Question

제가

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

등의 정렬 된 배열을 가정하고 I는 합계의 오름차순 크기 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}