Vytvorenie množiny permutácií daných súborom čísel a niektorých podmienok na relatívnych pozíciách prvkov - algoritmus, permutácia, kombinatorika, spätná väzba

Hľadám algoritmus, ktorý, vzhľadom na súborčísel {0, 1, 2, 4, 5 ...} a súbor podmienok na relatívnych pozíciách každého prvku by overil, či existuje platná permutácia. Podmienky sú vždy typu "Prvok v pozícii i v pôvodnom poli musí byť ďalší (susediaci) s elementom v pozícii j alebo z".
Posledný a prvý prvok v permutácii sú považované za priľahlé.

Tu je jednoduchý príklad:

Nech sú čísla {0, 1, 2, 3}
a súbor podmienok: a0 musí byť vedľa a1, a0 musí byť vedľa a2, a3 musí byť vedľa a1
Platné riešenie tohto príkladu by bolo {0,1,3,2}.

Všimnite si, že akékoľvek otáčanie / symetria tohto riešenia je tiež platným riešením. Potrebujem dokázať, že takéto riešenie existuje.

Iný príklad používajúci ten istý súbor:
a0 musí byť vedľa a1, a0 musí byť vedľa a3, a0 musí byť vedľa a2.

Pre tento príklad neexistuje platné riešenie, pretože číslo môže byť priradené len dvom číslam.

Jediný nápad, s ktorým by som mohol prísť práve teraz, bude používať nejaký druh spätného odkráčania.
Ak existuje riešenie, malo by to dosiahnuť tichorýchlo. Ak neexistuje žiadne riešenie, nemôžem si predstaviť žiadny spôsob, ako sa vyhnúť kontrole všetkých možných permutácií. Ako som už uviedol, rotácia alebo symetria nemá vplyv na výsledok pre danú permutaciu, preto by malo byť možné znížiť počet možností.

odpovede:

Formulujte to ako problém s grafmi. Pripojte každú pár čísel, ktoré musia byť vedľa seba. Chystáte sa skončiť s množstvom pripojených komponentov. Každá zložka má niekoľko permutácií (dovoľte im nazvať mini-permutácie) a môžete mať permutaciu komponentov.

Pri vytváraní grafu sa uistite, že každá zložka sleduje množstvo pravidiel: žiadne cykly, žiadne vrcholy s viac ako dvoma vrcholmi atď.

V podstate chcete vedieť, či môžete vytvoriťreťazcov čísel. Každé číslo vložte do reťazca, ktorý sleduje počet a najviac dvoch susedov. Použite pravidlá na spojenie reťazcov. Keď sa pripojíte k dvom reťazcom, skončíte reťazou s dvomi voľnými koncami (susedmi) .Ak môžete dosiahnuť všetky pravidlá bez toho, aby ste mali voľné konce, potom to funguje.

Implementoval som grafické riešenie s miernymi zmenami.

Ak má uzol príliš veľa susedov, algoritmusby poklesol jeden okraj a znova skontrolujte graf. Potom použijem spätnú väzbu, aby som sa vrátil späť a skontrolujte, či je možné spustiť ďalší okraj ... Táto metóda dáva rovnaký výsledok ako metóda hrubej sily, ktorú som napísal.

Z hľadiska zložitosti sa zdá, že toto riešenie jelepšie než hrubej sily, hoci ju nemôžem spustiť na viac ako 20 číslach (iba 8 na hrubou silou). V tomto zmysle je to logické, pretože takýto graf môže skutočne generovať podmnožinu platnej permutácie naraz, plus v najhoršom prípade je ekvivalentom nájdenia niektorých kompozícií nad súpravou okrajov.

Vzhľadom na to, že rotácia nemá žiadny vplyvplatnosť permutácií, premýšľal som o tom, ako sa na prvom mieste nastaví A0 (To sa dá dosiahnuť jednoduchým otočením platnej permutácie, kým a0 sa nenachádza v prvej pozícii) a potom sa pokúsme vybudovať riešenie odtiaľ.

Pomocou DP môžem získať niečo lepšie ako exponenciálnu zložitosť. Musím však povedať, že stále neviem, kde začať :)