Все возможные перестановки слов в листе, не менняя индекса Char`ов

Question

Всем доброго времени суток! Есть List<string> в котором N-ое количество элементов. Надо найти все перестановки элементов по вертикале. Элементы в листе одной длинны. Например, есть элементы на входе:

abc

123

На выходе должно быть:

{
 1. abc
 2. 123
 3. ab3
 4. a23
 5. a2c
 6. 1bc
 7. 12c
 8. 1b3
}

Т.е. Char a всегда будет на 0 элементе, как и char 1. Char b и 2 -- 1-ый элемент в массиве. Char c и 3 -- 2-ой элемент. Найти все перестановки, сохранив условия выше.

Подскажите, пожалуйста, алгоритм для поиска таких перестановок.

edit: попытка решения (но проблемы начинаются если попробовать взять, например, элементы с длинной в 4 символа)

void GenerateAdditionalWords()
{
    string word = string.Empty;

    List<string> list = new List<string>();
    list.Add("abc");
    list.Add("123");

    List<string> newList = new List<string>();
    for (int x = 0; x < list[0].Length; x++)
    {
        for (int y = 0; y < list.Count; y++)
        {
            word = list[y];
            word = ChangeChar(word, list[y][x], x);

            for (int t = 0; t < list.Count; t++)
            {
                word = ChangeChar(word, list[t][x], x);

                if (newList.IndexOf(word) == -1)
                {
                    newList.Add(word);
                }
            }
        }
    }
}

string ChangeChar(string word, char newChar, int index)
{
    tempWord = word.ToCharArray();
    tempWord[index] = newChar;
    return new string(tempWord);
}

Answer 1

Все очень просто. У вас 3 символа. Рассмотрим 3 бита, соответствующие знакоместам. Бит 0 - символ из первого слова, 1 - из второго. Все варианты - от 000 до 111. Все, просто цикл от 0 до 7 включительно, с подстановкой нужного символа...

Или у вас их может быть не 2, исходных слов? Тогда соответственно для каждого символа надо рассматривать число вариантов, равное количеству "слов".

Answer 2

Задача очень похожа на декартово произведение множеств, точнее на его частный случай.

static void Main(string[] args)
{
    List<string> list = new List<string>();
    list.Add("abc");
    list.Add("123");
    Console.WriteLine(string.Join(Environment.NewLine, GetCombinations(list)));
    Console.ReadKey(true);
}

public static IEnumerable<string> GetCombinations(List<string> items)
{
    int length = items[0].Length;
    int[] indexes = new int[length];
    char[] result = new char[length];

    while (true)
    {
        for (int i = 0; i < length; i++)
        {
            result[i] = items[indexes[i]][i];
        }
        yield return new string(result);

        int column = length - 1;
        indexes[column]++;
        while (indexes[column] == items.Count)
        {
            if (column == 0)
                yield break;
            indexes[column] = 0;
            column--;
            indexes[column]++;
        }
    }
}

Вывод в консоль

abc
ab3
a2c
a23
1bc
1b3
12c
123

Более общее решение рассмотрено здесь.

БЛОГ НА HUSL

Все возможные перестановки слов в листе, не менняя индекса Char`ов

Ответы (2 шт):