Найти все перестановки ряда, в которых нет смежных элементов? - PullRequest
0 голосов
/ 03 октября 2019

Нам дан список чисел, в которых каждое число либо встречается само по себе, либо встречается в двух экземплярах. Теперь задача состоит в том, чтобы найти общее число перестановок, в которых мы можем упорядочить этот список чисел так, чтобы никакие два соседних элемента в списке не были одинаковыми. Суть в том, чтобы сделать это эффективно, и поэтому я ищу алгоритм, который использует динамическое программирование. Длина может быть очень большой - до 5000 элементов, поэтому генерировать все случаи и проверять, является ли случай правильным или нет, не очень хорошая идея. Нам нужно только общее количество перестановок, а не фактические перестановки в списке.

Пример Case: [1,1,2,2]

Выход: 2

[1,2,1,2] и [2,1,2,1]

Пример случая: [1,2,3,3]

Выход: 6

[3,1,2,3], [3,2,1,3], [1,3,2,3], [2,3,1,3], [3,1,3,2] и [3,2,3,1]

Пример Case: [1,1,2,2,3,3]

Выход: 30

1 Ответ

3 голосов
/ 03 октября 2019

Эта проблема может быть решена с использованием принципа включения-исключения

Если количество отдельных элементов равно s, а количество пар из двух элементов равно d, то общее количество перестановокis

A0 = (s + 2 * d)! / 2^d

Теперь мы должны вычесть число перестановок, где одна пара смежна. Существует

P1 = (s+2*d-1)! / 2^(d-1)

таких перестановок для каждого удвоенного элемента и

A1 = d *(s+2*d-1)! / 2^(d-1)

таких перестановок для всех удвоенных элементов

Теперь мы должны добавить номер перестановки, где две пары смежны. Существует

P2 = (s+2*d-2)! / 2^(d-2)

таких перестановок для каждой пары удвоенных элементов и

A2 = C(d,2) * (s+2*d-2)! / 2^(d-2)

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

Продолжите эту процедуру, изменив знак, поэтому

A(k){k=1..d} = (-1)^k * C(d, k) * (s+2*d-k)! / 2^(d-k)

и суммируйте эту последовательность, чтобы получить окончательный результат

Для вашего последнего примера (s=0,d=3):

 6!/2^3 - 3*5!/2^2 + 3*4!/2 - 3! = 
 720/8  - 360/4 +    72/2   - 6  = 
  90    - 90     +   36     - 6  = 30 
...