Перестановки списков с переменной длиной и альтернативным содержимым списка

Question

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

Допустим, у нас есть 2 переменные A и B, но мне нужно их использоватьс индексом А1, А2 и В1, В2.Чтобы сделать его еще более сложным, индекс «1» может встречаться один и не допускается с другим «1», индекс «2» не может встречаться один.Так что мне нужно было бы:

---

• A1
• B1
• A1 B2
• B1 A2

---

Использование 3 переменных A1, A2, B1, B2, C1, C2:

• A1
• A1 B2
• A1 C2
• A1 B2 C2
• B1
• B1 A2
• B1 C2
• B1 A2 C2
• C1
• C1 A2
• C1 B2
• C1 A2 B2

---

И мне это понадобится для n переменных (n1, n2).Я нашел этот, но он мне не очень помог: длина переменной перестановок , но он не совсем подходит.На самом деле, я сейчас понятия не имею, как с этим справиться.

Answer 1

Я не уверен, правильно ли я понял вашу проблему, но позвольте мне попробовать.Для создания этого конкретного набора я использовал метод разделения проблемы на первые записи, такие как A1, и вторые записи, такие как A2.Я создал следующий алгоритм:

1. Создать список всех первых записей в соответствии с вводом n (для n == 3 это будет {A1, B1, C1})

2. СоздатьСписок всех вторых записей в соответствии с вводом n (для n == 3 это будет {A2, B2, C2})

3. Для каждого первого ввода, как A1

   1. Для каждого набора в powerset вторых записей
   2. Если нет столкновений, таких как A1 и A2
      1. Объединить набор, например, {B2, C2}создать конкатенацию, например B2C2
      2. Добавить новый элемент = firstEntry + concatenated set в список моего пользовательского набора
4. Вернуться пользовательский набор

Для реализации я использовал this для шага алгоритма 3.1.приводя к следующей реализации:

    private List<string> GetCustomPermutations(int count)
    {
        if(count < 1)
        {
            return new List<string>();
        }

        List<string> firstEntries = new List<string>();
        List<string> secondEntries = new List<string>();

        // Create list of firstEntries = {A1, B1, ...} and secondEntries = {A2, B2, ...} from count
        for (int i = 0; i < count; i++)
        {
            firstEntries.Add((char)('A' + i) + "1");
            secondEntries.Add((char)('A' + i) + "2");
        }

        // Get Powerset of second Entries
        string[][] FullPowerSet = FastPowerSet(secondEntries.ToArray());

        List<string> CustomSet = new List<string>();
        foreach (string firstEntry in firstEntries)
        {
            for (int i = 0; i < FullPowerSet.Length; i++)
            {
                // join the second array dimension to create the appended entry
                string appendedEntry = string.Join("", FullPowerSet[i]);

                // Avoid adding the firstentry char to the appended aswell
                if (appendedEntry.Contains(firstEntry[0]))
                {
                    continue;
                }
                CustomSet.Add(firstEntry + appendedEntry);
            }
        }
        return CustomSet;
    }

    // Create a powerset of every input array, see https://stackoverflow.com/questions/19890781/creating-a-power-set-of-a-sequence
    public static T[][] FastPowerSet<T>(T[] seq)
    {
        var powerSet = new T[1 << seq.Length][];
        powerSet[0] = new T[0]; // starting only with empty set
        for (int i = 0; i < seq.Length; i++)
        {
            var cur = seq[i];
            int count = 1 << i; // doubling list each time
            for (int j = 0; j < count; j++)
            {
                var source = powerSet[j];
                var destination = powerSet[count + j] = new T[source.Length + 1];
                for (int q = 0; q < source.Length; q++)
                    destination[q] = source[q];
                destination[source.Length] = cur;
            }
        }
        return powerSet;
    }