Czy istnieje skuteczny algorytm do znalezienia i-tej drogi?

9

Oto tło tego pytania. Graliśmy z przyjaciółmi w grę, w której każdy musi dać innym ludziom prezent. Aby ustalić, kto powinien komuś dać prezent, decydujemy się na losowanie. Problem w tym, że ktoś może dać sobie prezenty, co nie jest śmieszne. Widać, że oczekiwana liczba takich nieszczęśliwych osób wynosi 1, więc zdarza się to dość często.

W tym celu rozwiązywanie problemów wydaje się doskonale pasować. Jeśli mogę rzetelnie wygenerować porozumienie, mogę wybrać tylko jedno porozumienie i użyć go, aby zdecydować, komu dać komuś prezenty.

Generowanie losowych ustaleń można przeprowadzić metodą Las Vegas. Ale problem polega na tym, że spodziewał się tylko wielomianowego czasu działania. Doszedłem więc do problemu znalezienia i-tej drogi. Jeśli mogę losowo wybrać i w [1, D_n] i użyć jakiegoś najgorszego algorytmu czasu wielomianowego (wydajnego), aby uzyskać i-ty układ, to jest to zrobione.

permutations Santa Zhang
źródło
1
Czy mógłbyś wyjaśnić motywację pytania? tzn. dlaczego jesteś zainteresowany tym pytaniem?
Kaveh,
2
Być może chcesz zagrać w tajemniczego
Świętego
Czy możesz dodać linijkę o tym, co rozumiesz przez złość?
Vijay D

Odpowiedzi:

9

To może być dobre pytanie, ale w obecnej formie jest źle sformułowane. Dobrze znane algorytmy generowania losowych odchyleń mają liniowy oczekiwany czas, ale być może otwartym problemem jest znalezienie najgorszego przypadku algorytmu wielomianowego czasu.

Zobacz na przykład: http://www.siam.org/proceedings/analco/2008/anl08_022martinezc.pdf (i slajdy: http://www.lsi.upc.edu/~conrado/research/talks/analco08.pdf )

didest
źródło
To wydaje mi się właściwą odpowiedzią.
Suresh Venkat,
10
Czy rekurencja! N = (n − 1) (! (N − 1) +! (N − 2)) opisana w en.wikipedia.org/wiki/ Rozbicie natychmiast nie prowadzi do najgorszego przypadku algorytmu wielomianowego losowego Pokolenie?
David Eppstein,
Tak masz rację. Myślałem, że jest mały haczyk, ponieważ musisz być w stanie wygenerować losowe liczby w dowolnych podzbiorach {1, ..., n} w najgorszym przypadku czasu politycznego, ale to łatwe do zrobienia.
didest,
0

Dlaczego nie dla każdej pozycji i losowo wybierać spośród wszystkich elementów innych niż ja ? Na przykład możesz wybrać indeks do oryginalnej tablicy z [0..n-2] , a jeśli otrzymasz j> = i , użyj j + 1 .

poklepać
źródło
3
Czy to sprawia, że ​​wszystkie odstępstwa są jednakowo prawdopodobne?
David Eppstein,
och, dobra uwaga - to umieszczałoby elementy później w tablicy, preferencyjnie wcześniej w tablicy. Gdyby wypełnić pola w tablicy docelowej w losowej kolejności, wszystkie odstępstwa byłyby równie prawdopodobne (symetrycznie).
pat