가능한 모든 조합 생성

가능한 모든 조합 생성

---

2 개의 배열이 주어 Array1 = {a,b,c...n}지고 Array2 = {10,20,15....x}가능한 모든 조합을 문자열 a (i) b (j) c (k) n (p) 어디서 생성 할 수 있습니까?

1 <= i <= 10,  1 <= j <= 20 , 1 <= k <= 15,  .... 1 <= p <= x

예 :

a1 b1 c1 .... n1  
a1 b1 c1..... n2  
......  
......  
a10 b20 c15 nx (last combination)

따라서 총 조합 수 = 요소의 곱 array2 = (10 X 20 X 15 X ..X x)

두 번째 배열이 첫 번째 배열의 각 요소에 대한 상한을 정의하는 데카르트 곱과 유사합니다.

고정 숫자의 예,

    Array x =  [a,b,c]
    Array y =  [3,2,4] 

따라서 3 * 2 * 4 = 24 개의 조합이 있습니다. 결과는 다음과 같아야합니다.

    a1 b1 c1  
    a1 b1 c2  
    a1 b1 c3  
    a1 b1 c4  

    a1 b2 c1  
    a1 b2 c2  
    a1 b2 c3  
    a1 b2 c4


    a2 b1 c1  
    a2 b1 c2  
    a2 b1 c3  
    a2 b1 c4  

    a2 b2 c1  
    a2 b2 c2  
    a2 b2 c3  
    a2 b2 c4


    a3 b1 c1  
    a3 b1 c2  
    a3 b1 c3  
    a3 b1 c4  

    a3 b2 c1  
    a3 b2 c2  
    a3 b2 c3  
    a3 b2 c4 (last)

---

using System;
using System.Text;

public static string[] GenerateCombinations(string[] Array1, int[] Array2)
{
    if(Array1 == null) throw new ArgumentNullException("Array1");
    if(Array2 == null) throw new ArgumentNullException("Array2");
    if(Array1.Length != Array2.Length)
        throw new ArgumentException("Must be the same size as Array1.", "Array2");

    if(Array1.Length == 0)
        return new string[0];

    int outputSize = 1;
    var current = new int[Array1.Length];
    for(int i = 0; i < current.Length; ++i)
    {
        if(Array2[i] < 1)
            throw new ArgumentException("Contains invalid values.", "Array2");
        if(Array1[i] == null)
            throw new ArgumentException("Contains null values.", "Array1");
        outputSize *= Array2[i];
        current[i] = 1;
    }

    var result = new string[outputSize];
    for(int i = 0; i < outputSize; ++i)
    {
        var sb = new StringBuilder();
        for(int j = 0; j < current.Length; ++j)
        {
            sb.Append(Array1[j]);
            sb.Append(current[j].ToString());
            if(j != current.Length - 1)
                sb.Append(' ');
        }
        result[i] = sb.ToString();
        int incrementIndex = current.Length - 1;
        while(incrementIndex >= 0 && current[incrementIndex] == Array2[incrementIndex])
        {
                current[incrementIndex] = 1;
                --incrementIndex;
        }
        if(incrementIndex >= 0)
            ++current[incrementIndex];
    }
    return result;
}

---

확실한 것. LINQ로이 작업을 수행하는 것은 약간 까다 롭지 만 표준 쿼리 연산자 만 사용하면 확실히 가능합니다.

업데이트 : 이것은 2010 년 6 월 28 일 월요일 에 내 블로그 의 주제입니다 . 좋은 질문에 감사드립니다. 또한 내 블로그의 댓글 작성자는 내가 제공 한 것보다 훨씬 더 우아한 쿼리가 있다고 언급했습니다. 여기에서 코드를 업데이트하여 사용하겠습니다.

까다로운 부분은 임의로 많은 시퀀스의 데카르트 곱을 만드는 것입니다. 글자의 "Zipping"은 그것에 비해 사소합니다. 어떻게 작동하는지 이해하기 위해 이것을 연구해야합니다. 각 부분은 충분히 간단하지만 함께 결합되는 방식은 다음과 같은 작업에 익숙해 져야합니다.

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

이것이 어떻게 작동하는지 설명하려면 먼저 "누적"작업이 수행하는 작업을 이해하십시오. 가장 간단한 누적 작업은 "이 시퀀스의 모든 항목을 함께 추가"하는 것입니다. 그렇게하는 방법은 0으로 시작하는 것입니다. 시퀀스의 각 항목에 대해 누산기의 현재 값은 항목과 누산기의 이전 값의 합과 같습니다. 우리는 지금까지의 합계와 현재 항목을 기준으로 합계를 누적하는 대신에 우리가 가면서 데카르트 곱을 누적한다는 점을 제외하면 동일한 작업을 수행합니다.

그렇게하는 방법은 두 가지의 데카르트 곱을 계산하는 LINQ에 이미 연산자가 있다는 사실을 활용하는 것입니다.

from x in xs
from y in ys
do something with each possible (x, y)

입력 시퀀스의 다음 항목과 함께 누산기의 데카르트 곱을 반복적으로 취하고 결과를 함께 약간 붙여 넣으면 진행하면서 데카르트 곱을 생성 할 수 있습니다.

따라서 누산기의 가치에 대해 생각하십시오. 설명을 위해 누산기에 포함 된 시퀀스 연산자 의 결과 로 누산기의 값을 표시하겠습니다 . 그것은 누산기에 실제로 포함 된 것이 아닙니다 . 누산기에 실제로 포함되는 것은 이러한 결과를 생성 하는 연산자 입니다. 여기서 전체 작업은 거대한 시퀀스 연산자 트리를 구축하고 그 결과는 데카르트 곱입니다. 그러나 최종 데카르트 곱 자체는 쿼리가 실행될 때까지 실제로 계산되지 않습니다. 설명을 위해 각 단계에서 결과 가 무엇인지 보여 드리지만 실제로 여기에는 연산자 가 포함되어 있습니다. 그 결과를 낳습니다.

시퀀스 시퀀스의 데카르트 곱을 취한다고 가정합니다 {{1, 2}, {3, 4}, {5, 6}}. 누산기는 하나의 빈 시퀀스를 포함하는 시퀀스로 시작합니다.{ { } }

첫 번째 누적에서 누산기는 {{}}이고 항목은 {1, 2}입니다. 우리는 이것을합니다 :

from accseq in accumulator
from item in sequence 
select accseq.Concat(new[] {item})

우리의 직교 제품을 복용 그래서 { { } }과를 {1, 2}, 각 쌍에 대해, 우리는 연결할 : 우리는 한 쌍을 가지고 ({ }, 1), 그래서 우리는 연결할 { }및 {1}얻을 {1}. 우리는 쌍을 가지고 있습니다. ({ }, 2})그래서 우리는 연결 { }하고 {2}얻습니다 {2}. 따라서 우리는 {{1}, {2}}그 결과를 얻었습니다.

따라서 두 번째 누적에서 누산기는 {{1}, {2}}이고 항목은 {3, 4}입니다. 다시,이 두 시퀀스의 데카르트 곱을 계산하여 다음을 얻습니다.

 {({1}, 3), ({1}, 4), ({2}, 3), ({2}, 4)}

그런 다음 해당 항목에서 두 번째 항목을 첫 번째 항목에 연결합니다. 그래서 결과는 {{1, 3}, {1, 4}, {2, 3}, {2, 4}}우리가 원하는 수열 입니다.

이제 우리는 다시 축적됩니다. 우리는 함께 누적의 직교 제품을 {5, 6}얻을 수 있습니다

 {({ 1, 3}, 5), ({1, 3}, 6), ({1, 4}, 5), ...

그런 다음 두 번째 항목을 첫 번째 항목에 연결하여 다음을 얻습니다.

{{1, 3, 5}, {1, 3, 6}, {1, 4, 5}, {1, 4, 6} ... }

그리고 우리는 끝났습니다. 우리는 데카르트 곱을 축적했습니다.

이제 임의로 많은 시퀀스의 데카르트 곱을 취할 수있는 유틸리티 함수가 있으므로 나머지는 비교하기 쉽습니다.

var arr1 = new[] {"a", "b", "c"};
var arr2 = new[] { 3, 2, 4 };
var result = from cpLine in CartesianProduct(
                 from count in arr2 select Enumerable.Range(1, count)) 
             select cpLine.Zip(arr1, (x1, x2) => x2 + x1);

그리고 이제 우리는 한 줄에 하나의 문자열 시퀀스가있는 일련의 문자열을 가지고 있습니다.

foreach (var line in result)
{
    foreach (var s in line)
        Console.Write(s);
    Console.WriteLine();
}

쉬워요!

---

대체 솔루션 :

1 단계 : 문맥 감지 문법과 일치하는 모든 문자열을 생성하는 방법에 대한 일련의 기사를 읽으십시오.

http://blogs.msdn.com/b/ericlippert/archive/tags/grammars/

2 단계 : 원하는 언어를 생성하는 문법을 정의합니다. 예를 들어 문법을 정의 할 수 있습니다.

S: a A b B c C
A: 1 | 2 | 3
B: 1 | 2
C: 1 | 2 | 3 | 4

분명히 두 배열에서 문법 정의 문자열을 쉽게 생성 할 수 있습니다. 그런 다음 주어진 문법에서 모든 문자열을 생성하는 코드에 입력하면 완료됩니다. 당신은 모든 가능성을 얻을 것입니다. (필수적으로 원하는 순서는 아닙니다.)

---

비교를 위해 다음은 Python으로 수행하는 방법입니다.

from itertools import product
X=["a", "b", "c"]
Y=[3, 4, 2]
terms = (["%s%s"%(x,i+1) for i in range(y)] for x,y in zip(X,Y))
for item in product(*terms):
    print " ".join(item)

---

linq 기반이 아닌 다른 솔루션을 사용할 수 있습니다.

public class CartesianProduct<T>
    {
        int[] lengths;
        T[][] arrays;
        public CartesianProduct(params  T[][] arrays)
        {
            lengths = arrays.Select(k => k.Length).ToArray();
            if (lengths.Any(l => l == 0))
                throw new ArgumentException("Zero lenght array unhandled.");
            this.arrays = arrays;
        }
        public IEnumerable<T[]> Get()
        {
            int[] walk = new int[arrays.Length];
            int x = 0;
            yield return walk.Select(k => arrays[x++][k]).ToArray();
            while (Next(walk))
            {
                x = 0;
                yield return walk.Select(k => arrays[x++][k]).ToArray();
            }

        }
        private bool Next(int[] walk)
        {
            int whoIncrement = 0;
            while (whoIncrement < walk.Length)
            {
                if (walk[whoIncrement] < lengths[whoIncrement] - 1)
                {
                    walk[whoIncrement]++;
                    return true;
                }
                else
                {
                    walk[whoIncrement] = 0;
                    whoIncrement++;
                }
            }
            return false;
        }
    }

여기에서 사용 방법에 대한 예를 찾을 수 있습니다 .

---

완전한 소스 코드를 제공하지 않을 것입니다. 그래서 여기에 숨겨진 아이디어가 있습니다.

다음과 같은 방법으로 요소를 생성 할 수 있습니다.

나는 가정 A=(a1, a2, ..., an)하고 B=(b1, b2, ..., bn)(그래서 A그리고 B각각은 n요소를 보유 한다).

Then do it recursively! Write a method that takes an A and a B and does your stuff:

If A and B each contain just one element (called an resp. bn), just iterate from 1 to bn and concatenate an to your iterating variable.

If A and B each contain more then one element, grab the first elements (a1 resp b1), iterate from 1 to bn and do for each iteration step:

• call the method recursively with the subfields of A and B starting at the second element, i.e. A'=(a2, a3, ..., an) resp B'=(b2, b3, ..., bn). For every element generated by the recursive call, concatenate a1, the iterating variable and the generated element from the recursive call.

Here you can find an analouge example of how to generate things in C#, you "just" have to adapt it to your needs.

---

If I am getting it right, you are after something like Cartesian product. If this is the case here is you how you can do this using LINQ. Might not be exact answer but try to get the idea

---

    char[] Array1 = { 'a', 'b', 'c' };
    string[] Array2 = { "10", "20", "15" };

    var result = from i in Array1
                 from j in Array2
                   select i + j;

---

These Articles might help

• SelectMany

• How to Use LINQ SelectMany

---

The finalResult is the desired array. Assumed the both arrays are of same size.

char[] Array1 = { 'a', 'b', 'c' };
int[] Array2 = { 3, 2, 4 };

var finalResult = new List<string>();
finalResult.Add(String.Empty);
for(int i=0; i<Array1.Length; i++)
{
    var tmp = from a in finalResult
              from b in Enumerable.Range(1,Array2[i])
              select String.Format("{0} {1}{2}",a,Array1[i],b).Trim();
    finalResult = tmp.ToList();
}

I think this will suffice.

---

Here's is a javascript version, which I'm sure someone can convert. It has been tested thoroughly.

Here's the fiddle.

function combinations (Asource){

    var combos = [];
    var temp = [];

    var picker = function (arr, temp_string, collect) {
        if (temp_string.length) {
           collect.push(temp_string);
        }

        for (var i=0; i<arr.length; i++) {
            var arrcopy = arr.slice(0, arr.length);
            var elem = arrcopy.splice(i, 1);

            if (arrcopy.length > 0) {
                picker(arrcopy, temp_string.concat(elem), collect);
            } else {
                collect.push(temp_string.concat(elem));
            }   
        }   
    }

    picker(Asource, temp, combos);

    return combos;

}

var todo = ["a", "b", "c", "d"]; // 5 in this set
var resultingCombos = combinations (todo);
console.log(resultingCombos);

---

Fon another solution not linq based, more effective:

static IEnumerable<T[]> CartesianProduct<T>(T[][] arrays) {
    int[] lengths;
    lengths = arrays.Select(a => a.Length).ToArray();
    int Len = arrays.Length;
    int[] inds = new int[Len];
    int Len1 = Len - 1;
    while (inds[0] != lengths[0]) {
        T[] res = new T[Len];
        for (int i = 0; i != Len; i++) {
            res[i] = arrays[i][inds[i]];
        }
        yield return res;
        int j = Len1;
        inds[j]++;
        while (j > 0 && inds[j] == lengths[j]) {
            inds[j--] = 0;
            inds[j]++;
        }
    }
}

---

I just discovered this CodeProject posting that includes a Facets.Combinatorics namespace containing some useful code to handle Permuations, Combinations and Variations in C#.

http://www.codeproject.com/Articles/26050/Permutations-Combinations-and-Variations-using-C-G

참고URL : https://stackoverflow.com/questions/3093622/generating-all-possible-combinations