Последовательность Лэнгфорда - использование симметрии / удаление симметрии

Question

Я написал программу, которая может вычислить количество возможных последовательностей Лэнгфорда (https://en.wikipedia.org/wiki/Langford_pairing).

---

TL; DR Последовательности Лэнгфорда определяются L (s, n) где s - количество вхождений определенного числа

, а n - количество возможных чисел / цветов, числа определяют, сколько позиций они должны соответствовать друг другу

Картинка будет L (2, 4) ==> каждый номер имеет 2 вхождения и есть 4 разных номера. Количество | L (2,4) | будет 1, потому что существует только одна возможная перестановка, которая удовлетворяет ограничениям

---

Идея вычисления количества возможных перестановок следующая. L (2,4) Мы начинаем с Bitset [s * n] из всех 0, как Root

на каждой глубине, мы получаем все возможные перестановки, где все вхождения номера curret (= n-глубина) отличные позиции глубины n друг от друга.

в глубине 1 мы получаем все возможные позиции для 4 =>

10000100

01000010

00100001

Возможная перестановка я проверяю если есть столкновение (если одна из используемых позиций уже используется другим номером). Я сделал это, подсчитав количество битов, равных 1, и сравнил их с родительскими битами. if (currentPos xor Parent) .count () == Parent.count () + s, тогда столкновения не было, и я могу попасть на одну глубину глубже. (проверьте все возможные перестановки для 3, которые соответствуют ie ограничениям)

если все биты равны единице [(currentPos xor Parent) .count () == s * n], мы достигли возможной перестановки, где каждое Число - это его значение отдельно друг от друга для каждого числа.

Это работает до сих пор, но ive удвоил каждый номер по сравнению с тем, что я должно получиться в результате, потому что я не учел симметрию. (для L (s, n) я всегда получаю 2 * L (s, n))

Мне было интересно, как использовать симметрию дерева для получения правильных результатов.

---

Моя первоначальная идея заключалась в том, чтобы просто использовать first to ceil (len (Permutation) / 2) Permutations (Red-Selection на следующем изображении). Но это приводило к худшим результатам.

---

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

Ty in advcanded

---

Answer 1

L(s, n) - «до отмены заказа», см. Например, https://oeis.org/A014552. Это означает, например, что для |L(2, 4)| у нас есть

4 1 3 1 2 4 3 2

и

2 3 4 2 1 3 1 4

оба удовлетворяют свойству, но одно является обратным для другого, поэтому |L(2, 4)| = 1.

Чтобы учесть это в своем алгоритме, вы можете проверить, например, на самом первом уровне, что слева больше свободных бит, чем справа.

NB: ваш алгоритм перечисляет все решения , значит сложность > L(2, n) а для n = 20 это уже больше 2^41. Вы, вероятно, этого не достигнете. Как упоминалось на странице Википедии:

для больших n количество решений может быть вычислено более эффективно алгебраическими c методами

Answer 2

Вы можете удалить половину перестановок на уровне / глубине 1, если N нечетное. Если N четное, удалите половину перестановки на уровне / глубине 2.

Надеюсь, я смогу вам помочь.