Генерация всех возможных комбинаций

конечно. Это немного сложно сделать с LINQ, но, безусловно, возможно, используя только стандартные операторы запросов.

обновление: это предмет мой блог в понедельник, 28 июня 2010 года; спасибо за отличный вопрос. Кроме того, комментатор в моем блоге отметил, что есть еще более элегантный запрос, чем тот, который я дал. Я обновлю код здесь, чтобы использовать его.

сложная часть состоит в том, чтобы сделать декартово произведение произвольно многих последовательностей. "Молния" в письмах тривиальна по сравнению с этим. Вы должны изучить это, чтобы убедиться, что вы понимаете, как это работает. Каждая часть достаточно проста, но то, как они объединены вместе, требует некоторого привыкания:

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

чтобы объяснить, как это работает, сначала понять, что делает операция "накапливать". Самая простая операция накопления - "сложить все в этой последовательности вместе". То, как вы это делаете: начните с нуля. Для каждого элемента в последовательности текущий значение аккумулятора равно сумме элемента и предыдущего значения аккумулятора. Мы делаем то же самое, за исключением того, что вместо накопления суммы, основанной на сумме до сих пор и текущем элементе, мы накапливаем декартово произведение по мере продвижения.

мы собираемся сделать это, чтобы воспользоваться тем фактом, что у нас уже есть оператор в 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();
}

легко peasy!

альтернативное решение:

Шаг первый: прочитайте мою серию статей о том, как генерировать все строки, соответствующие контекстно-зависимой грамматике:

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

Шаг второй: определите грамматику, которая генерирует нужный язык. Например, вы можете определить грамматику:

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)

Fon другое решение не 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 элементов).

тогда сделайте это рекурсивно! Напишите метод, который принимает A и B и делает свое дело:

если A и B каждый содержит только один элемент (называется an респ. bn), просто перебирать от 1 до bn обединить an к вашей итерационной переменной.

если A и B каждый из которых содержит более одного элемента, захватить первые элементы (a1 респ b1), повторите от 1 до bn и сделать для каждого шага итерации:

• вызовите метод рекурсивно с подполями A и B начиная со второго элемента, т. е. A'=(a2, a3, ..., an) респ B'=(b2, b3, ..., bn). Для каждого элемента, сгенерированного рекурсивным вызовом, конкатенация a1, итерационная переменная и сгенерированный элемент из рекурсивного вызова.

здесь вы можете найти пример analouge о том, как создавать вещи в C#, вы "просто" должны адаптировать его к вашим потребностям.

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

---

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

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

---

эти статьи могут помочь

• SelectMany

• как использовать LINQ SelectMany

finalResult-это нужный массив. Предполагается, что оба массива имеют одинаковый размер.

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

Я думаю, этого будет достаточно.

вот версия javascript, которую я уверен, что кто-то может конвертировать. Он был тщательно протестирован.

вот скрипка.

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

Я только что обнаружил эту публикацию CodeProject, которая включает в себя фасеты.Combinatorics пространство имен, содержащее некоторый полезный код для обработки перестановок, комбинаций и вариаций в C#.

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

Fon другое решение, не основанное на linq, более эффективное:

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]++;
        }
    }
}