Generowanie permutacji z ograniczeniami

Question

Cześć, chciałem was zapytać jaki znacie najszybszy algorytm na generowanie permutacji z ograniczeniami (np. mamy liczby 1 6 2 9 3 i następujące pary {2,6}, {9,3}, {1,6} muszą być koło siebie). Da się inaczej niż po prostu wygenerować permutację i sprawdzić, czy jest poprawna? Czy można już na etapie ich tworzenia unikać niewłaściwych?

Comments

Czy chodzi o to, że dla jakiejś tablicy 1 6 2 mają być wypisane wszystkie różne ciągi 2-członowe: {1 6} {6 1} {6 2} {2 6} {1 2} {2 1} Nie jestem pewien czy "koło siebie" oznacza sposób wypisywania.

---

No nie do końca, powiedzmy dla tej tablicy (1, 6, 2) mamy ograniczenie, że 6 i 2 mają być koło siebie, wówczas program powinien wygenerować wszystkie permutacje oprócz (6, 1, 2) i (2, 1, 6) - bo dla tych przypadków warunek o bliskości 2 i 6 nie jest spełniony. Właściwie zaczynam natrafiać na pewien trop - można by takie pary traktować jako pojedyncze elementy, aczkolwiek problem jest taki, że mogą też być trójki, czwórki, które muszą być koło siebie (wtedy ich kolejność między sobą jest dowolna, ale muszą tworzyć zwarty człon w permutacji), chociaż tutaj też można się pokusić o taką samą analogię... No tak to widzę póki co, może da się inaczej.