Создание всех возможных комбинаций

Ответ 1

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

Ответ 2

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

ОБНОВЛЕНИЕ: Это тема моего блога в понедельник 28 июня 2010 года; спасибо за большой вопрос. Кроме того, комментатор моего блога отметил, что есть еще более элегантный запрос, чем тот, который я дал. Я буду обновлять код здесь, чтобы использовать его.

Сложная часть состоит в том, чтобы сделать декартово произведение произвольно многих последовательностей. "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})                          
        );
 }

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

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

Ответ 3

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

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

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

Очевидно, вы можете легко сгенерировать эту строку определения грамматики из ваших двух массивов. Затем подайте это в код, который генерирует все строки в данной грамматике, и вы закончите; вы получите все возможности. (Не обязательно в том порядке, в котором вы их хотите, заметьте.)

Ответ 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)

Ответ 5

Еще одно решение, не основанное на 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;
        }
    }

Вы можете найти пример как его использовать здесь.

Ответ 6

Я не хочу давать вам полный исходный код. Так вот идея.

Вы можете сгенерировать элементы следующим образом:

Я предполагаю A=(a1, a2, ..., an) и B=(b1, b2, ..., bn) (поэтому A и B каждый элемент n).

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

Если A и B содержат только один элемент (называемый an resp. bn), просто перейдите от 1 в bn и соедините an с вашей итерирующей переменной.

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

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

Здесь вы можете найти аналогичный пример того, как генерировать вещи на С#, вам просто нужно адаптировать его к вашим потребностям.

Ответ 7

Если я правильно понял, вы после чего-то вроде декартова продукта. Если это так, вот как это сделать, используя 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

Ответ 8

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

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

Ответ 9

Вот версия 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);

Ответ 10

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

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

Ответ 11

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