Zliczanie permutacji, których elementy nie mają dokładnie swojego indeksu ± M

Ostatnio zostałem zapytany o ten problem w wywiadzie algorytmicznym i nie udało mi się go rozwiązać.

Biorąc pod uwagę dwie wartości N i M, musisz policzyć liczbę permutacji o długości N (używając liczb od 1 do N), tak aby absolutna różnica między dowolną liczbą w permutacji a jej pozycją w permutacji nie była równa M.

Przykład - jeśli N = 3 i M = 1, wówczas 1 2 3 i 3 2 1 są prawidłowymi permutacjami, ale 1 3 2 jest nieprawidłowy, ponieważ liczba 3 znajduje się w pozycji 2, a ich różnica wynosi = M.

Próbowałem programowania dynamicznego NxM, ale nie udało mi się utworzyć powtarzalności, która nie liczy powtórzeń.

Pierwszą rzeczą, o którą chciałbym zapytać, kiedy otrzyma to pytanie, będzie

Czy chcesz algorytm wielomianowy?

i mam nadzieję, że odpowiedź brzmi „nie”. Podejrzewam, że ten problem jest trudny NP, z następującego powodu:

Naturalnym podejściem do tego problemu jest rozważenie umieszczenia pierwszej liczby i wyprowadzenie rekurencyjnej formuły w celu umieszczenia pozostałych. Działa to dobrze w przypadku (tj. Zliczanie liczby odchyleń), ponieważ nie ma znaczenia, jaką pozycję umieściłeś pierwszy numer, ponieważ jest tylko jedna „nielegalna” pozycja dla każdej liczby. Innymi słowy, takie podejście prowadzi do niezależnych podproblemów.$M=0$

Dla nie jest to takie proste, ponieważ teraz możemy mieć 2 nielegalne pozycje dla niektórych liczb. Która z tych pozycji pozostaje w podproblemie, jest teraz istotna dla rozwiązania podproblemu. Samo wzięcie pod uwagę liczby „nielegalnych” pozycji nie jest wystarczające, ponieważ „łańcuchy” liczb, które dzielą nielegalne pozycje, są wymagane do określenia struktury podproblemów tego podproblemu. Podejście to zasadniczo prowadzi do następującego podproblemu:$M>0$$2$

Biorąc pod uwagę zbiór , zbiór B ⊆ N zarówno wielkości co najwyżej N, jak i liczby naturalnej M , policz liczbę idealnych dopasowań na wykresie dwudzielnym ( A , B , E ) , gdzie ( a , b ) ∈ E jeśli i tylko jeśli | a - b | ≠ M .$A \subseteq \mathbb{N}$$B \subseteq \mathbb{N}$$N$$M$$(A,B,E)$$(a,b)\in E$$|a-b|\neq M$

Ten problem wygląda na trudny. Jedyne podejście do tego problemu, które widzę, to włączenie / wyłączenie, które nie doprowadzi do algorytmu wielomianowego czasu.

Możemy rozważyć podejścia, które nie opierają się na iteracyjnym rozmieszczeniu liczb, ale nie mam pojęcia, jak byś to zrobił. (szczególnie podczas wywiadu!)

Oczywiście wszystko to jest jedynie spekulacją i nadal możliwe jest, że sprytna sztuczka może dać rozwiązanie wielomianowe w czasie, ale mam nadzieję, że przedstawiłem przekonujący argument, że ta sztuczka musi być naprawdę bardzo sprytna.

Być może możliwe jest wykazanie twardości NP poprzez zredukowanie tego problemu do # 2-SAT („łańcuchy” liczb, które dzielą nielegalne pozycje, wydają się być trywialnym wyborem, który można by dopasować do wyboru wartości prawdy), ale Nie widziałem na razie oczywistego sposobu na zrobienie tego.

---

Gdyby osoba przeprowadzająca wywiad faktycznie była zadowolona z algorytmu wykładniczego czasu, po prostu wygenerowałabym wszystkie możliwe rozwiązania, dostosowując rekurencyjny algorytm cofania w celu wygenerowania permutacji wykluczającej ten konkretny przypadek.

Czy to możliwe, że źle zapamiętałeś konkretne dane lub źle zinterpretowałeś pytanie?

W opisie, element w pozycji B jest ograniczony do o - b ≠ ± M . Ale jeśli chodziło tylko o to, że różnica była ograniczona: a - b ≠ M , problem wydaje się możliwy do rozwiązania.$a$$b$$a-b \ne \pm M$
$a-b \ne M$

---

Opracowałem ten prostszy problem i próbowałem uogólnić w sposób, który, jak miałem nadzieję, dałby trochę swobody w rozwiązywaniu większego problemu. Ale to właśnie wyjaśniło mi, dlaczego podejście rekurencyjne jest mało prawdopodobne, co omówię na końcu.

$f(N,M,P)$$N$$a$$b$$a-b \ne M$$b-a \ne P$

$M$$P$

1 2 3 4 5  M=0, restricted values for each position
. . . . .  (positions in list)
1 2 3 4 5  P=0, restricted values for each position

3 4 5      M=2, restricted values for each position
. . . . .  (positions in list)
  1 2 3 4  P=1, restricted values for each position

$P \ge N$$g(N,M) = f(N,M,P)$$g(N,P) = f(N,M,P)$$M \ge N$

$M=P=0$$M$$P$$f$$g$

$$f(N,0,0) = g(N,0).$$

$$f(N,M,P) = f(N,P,M)$$

$g(N,M)$$f(N,M,P)$

$M=0$$i$$j$$N-1$$j$

$j$$(N-2)$$j$

1. $i$$g(N-2,0)$

2. $\ne i$$j$$g(N-1,0)$

$$g(N,0) = (N-1) \left[ g(N-2,0) + g(N-1,0) \right]$$

$$g(1,0) = 0, \ \ g(2,0) = 1$$

Jest to zwykła rekursywna formuła wykroczeń.

Chociaż nie mogę sobie wyobrazić, że ktoś nadchodzi z tym na miejscu, ale również okazuje nie jest zamkniętą formą rozwiązania tego (patrz rozstroju artykuł wiki szczegółów).

$$g(N,0) = \left\lfloor \frac{n!}{e} + \frac{1}{2} \right\rfloor$$

$M \ge N$

$$(M \ge N) \implies g(N,M) = N!$$

$0<M<N$$M$$M$

$i$

1. $i<M$$i$$i$$g(N-1,M-1)$

2. $i>=M$$i$$i$$g(N-1,M)$

$$(0<M<N) \implies g(N,M) = (M-1) g(N-1,M-1) + (N-M+1) g(N-1,M)$$

$g$

$M+P \ge N$$N-M$$N-P$$M+P-N$$g(N,M+P-N)$

$$(M+P)\ge N \implies f(N,M,P) = g(N,M+P-N)$$

$0<M<N$$0<P<N$$M+P<N$$f$$0<M\le P<N$

$P$$N-M-P$$M$

$M$$N-M-P$$P$

Tutaj jednak musimy zakończyć. Ponieważ nie ma możliwości zastosowania tej metody.

---

$a-b \ne \pm M$

$f(N,M,P)$

$2N$$N$$\{A_1,A_2,...,A_N\}$$\{B_1,B_2,...,B_N\}$$(A_i,B_j)$$i - j = M$$(B_j,A_i)$$j - i = M$$M \ne 0$

$A$$B$

Chcemy więc funkcji, która pobiera jako dane wejściowe ten wykres ograniczeń i wyprowadza liczbę permutacji, które spełniają ograniczenia.

$M+P\ge N$

$0<M \le P<N$$N$$N!$

Ponieważ istnieje tyle możliwych podgrafów po dopuszczeniu łańcuchów, naprawdę nie rozumiem, jak można to rozwiązać za pomocą zwykłych metod rekurencyjnych, chyba że istnieje sprytna relacja mówiąca, że ​​nieizomorficzne wykresy ograniczeń są w jakiś sposób równoważne liczbie permutacji.

Myślę, że najprawdopodobniej pytanie zostało źle zinterpretowane. Być może nawet przez ankietera (który mógł sam zapomnieć o szczegółach odpowiedzi).