1

Всем доброго времени суток! Есть 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);
}
7
  • 1
    @aepot элемент в List`е типа string
    – Pepsi4
    28 мар 2021 в 17:07
  • Если перевести задачу на русский, то правильно ли я расшифровал: найти все возможные перестановки цифр не переставляя буквы?
    – aepot
    28 мар 2021 в 17:12
  • Если бы не ab3 и ac3, я бы понял...
    – Harry
    28 мар 2021 в 17:12
  • Кажется ваш пример неправильный, или задача неправильная, одно из двух.
    – aepot
    28 мар 2021 в 17:14
  • @aepot нет, цифры и буквы тут не при чем. Переменная типа string. Элементы массива мы перемешиваем между собой, но индекс строки не меняем. Т.е. Char a всегда будет на 0 элементе, как и 1. Char b и 2 -- 1-ый элемент в массиве. Char c и 3 -- 2-ой элемент. Найти все перестановки, сохранив условия выше.
    – Pepsi4
    28 мар 2021 в 17:16

2 ответа 2

4

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

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

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

1
  • 1
    Спасибо огромное, работает!
    – Pepsi4
    28 мар 2021 в 18:05
3

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

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

2
  • Слов может быть до 6-7, например. И длинна слова до 7 char'ов.
    – Pepsi4
    28 мар 2021 в 17:55
  • N слов, M символов в слове. Работать с M-значными числами в системе счисления по основанию N.
    – Harry
    28 мар 2021 в 17:58

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.