Da się (wywoływać procedurę next_permutation
aż do momentu uzyskania prawidłowego wzorca - bo, jak mi się zdaje, istnieje pewna ilość prawidłowych permutacji). Jednak oczekiwanie na poprawną permutację już dla niewielkich wartości n
staje się zbyt długie.
Edit: mam jednak pewien pomysł: mamy ciąg liczb [0..n] (np. [0, 1, 2, 3].
- Bierzemy dwa pierwsze elementy, z których pierwszy jest na pozycji i - tutaj elementy to [0, 1] oraz i=0 (przyjmijmy, że pozycje liczymy od 0).
- Jeżeli te dwa elementy nie mogą istnieć obok siebie (jeden różni się o 1 od drugiego, jak tutaj [0, 1]), to robimy następną permutację wszystkich elementów od początku aż do elementu za naszą sprawdzaną parą - u nas by to było
next_permutation(tab, tab+n+3)
. Jedynym wyjątkiem jest to, gdy nie zgadzają się dwa ostatnie elementy - wtedy permutujemy cały ciąg. Potem wracamy do punktu 1. Inaczej bierzemy dwa następne elementy.
- Kończymy, jeśli cały ciąg jest OK.
Przykład dla n=6:
0123456 <=== ciąg
!! <=== elementy o pozycjach 0 i 1 nie zgadzają się
::: <=== w takim razie permutujemy pozycje od 0 do 2
0213456 <=== ciąg; potem liczymy od nowa
++ <=== OK
!! <=== elementy o pozycjach 1 i 2 nie zgadzają się
:::: <=== permutujemy pozycje od początku (0) do 2+1=3
0231456
++
!! <=== elementy o pozycjach 1 i 2 nie zgadzają się
:::: <=== permutujemy od początku do 3
0312456
++
++
!! <=== złe elementy 2 oraz 3
::::: <=== czyli permutujemy od początku aż do 3+1=4
0314256 <=== kolejny ciąg; teraz pokazuję tylko pierwszy błąd
!! <=== elementy o pozycjach 5 i 6 nie zgadzają się
::::::: <=== to dwa ostatnie elementy, więc permutujemy cały ciąg
0314265
!!
:::::::
0314526
!!
::::::
0315246 <=== CIĄG JEST OK