숫자와 특정 숫자 세트의 모든 추가 결합을 찾는 알고리즘?

Question

숫자 조합에 관한 문제가 있습니다.

예를 들어, 나는 2 개의 정수 매개 변수를 사용하여 주어진 매개 변수의 모든 추가 조합을 찾는 함수를 가지고 있습니다.

는 설명하기 :

public List<List<int>> getcombinations(int numbercount, int target){ 
.... 
return List; 
} 

가의가함으로써 인수를 결정하자

함수의 출력은이 방법으로 가정된다

numbercount=3 //it will be calculated with 3 integers 
target=9 // final number to find 

:

{{1,1,7},{1,2,6},{1,3,5},{1,4,4},{2,2,5},{2,3,4},{3,3,3}} 

우리 3 개의 정수가 추가로 사용될 때 대상 번호는 7 가지 가능성으로 발견 될 수 있습니다.

하나 더 예 :

numbercount=2 
target=7 
//Output should be like this: 
{{1,6},{2,5},{3,4}} // 3 possibilities when 2 integers is used in addition. 

나는이 문제에 대한 해결책을 찾기 위해 노력했다. 그러나 나는 그것을 해결할 방법을 찾지 못했습니다. 문제를 해결하거나 검색하는 방법에 대해 무엇을 조언합니까?

Answer 1

이것은 출발점이어야하며 필요한 경우 수정하여 조합 생성에 대한 훌륭한 설명을 읽어보십시오.

class Program 
{ 
    static void Main(string[] args) 
    { 
     foreach (var set in GetCombinations(3, 9)) 
     { 
      Console.WriteLine("{{{0}}}", string.Join(",", set)); 
     } 
     Console.ReadKey(); 
    } 


    public static IEnumerable<IEnumerable<int>> GetCombinations(int length, int targetSum) 
    { 
     var combinations = Enumerable.Range(1, length) 
      .Select(x => Enumerable.Range(1, targetSum - length+1)).CartesianProduct(); 
     combinations=combinations 
      .Where(x => x.Sum(y => y) == targetSum); 

     return combinations.Distinct(new Comparer()).ToList(); 
    } 

} 

public class Comparer : IEqualityComparer<IEnumerable<int>> 
{ 

    public bool Equals(IEnumerable<int> x, IEnumerable<int> y) 
    { 
     var isEqual= x.OrderBy(a => a).SequenceEqual(y.OrderBy(b => b)); 
     return isEqual; 
    } 

    public int GetHashCode(IEnumerable<int> obj) 
    { 
     return obj.Sum(); //lazy me, just indicate collection is same if their sum is same. 
    } 
} 

public static class Extensions 
{ 
    public static IEnumerable<IEnumerable<T>> CartesianProduct<T>(this IEnumerable<IEnumerable<T>> sequences) 
    { 
     IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>() }; 
     return sequences.Aggregate(
      emptyProduct, 
      (accumulator, sequence) => 
       from accseq in accumulator 
       from item in sequence 
       select accseq.Concat(new[] { item })); 
    } 
} 

조합을 생성하기위한 확장 방법 Eric Lippert에서 famous masterpiece이다.

Answer 2

이 코드는 특히 빠른 :

using System; 
using System.Collections.Generic; 


namespace konsol 
{ 
class Program 
{ 

    private static List<List<int>> combinations = new List<List<int>>(); 

    private static void Main(string[] args) 
    { 

     int length = 4 
     Generate(length , 10, 0, 1, 0, new int[length]); 


     foreach (var varibles in combinations) 
     { 
      Console.WriteLine(String.Join(",", variables)); 
     } 

     Console.ReadKey(); 
    } 



    private static void Generate(int length, int target, int k, int last, int sum, int[] a) 
    { 

     if (k == length- 1) 
     { 

      a[k] = target - sum; 
      combinations.Add(new List<int>(a)); 

     } 
     else 
     { 

      for (int i = last; i < target - sum - i + 1; i++) 
      { 

       a[k] = i; 
       Generate(length, target, k + 1, i, sum + i, a); 

      } 

     } 

    } 

} 

}