Gibt es einen effizienten Algorithmus, um die i-te Fehlordnung zu finden?

9

Hier ist der Hintergrund für diese Frage. Freunde und ich spielten ein Spiel, bei dem jeder einem anderen Volk ein Geschenk machen muss. Um zu bestimmen, wer wem ein Geschenk machen soll, beschließen wir, Lose zu ziehen. Aber das Problem ist, dass sich jemand möglicherweise selbst Geschenke macht, was nicht lustig ist. Sie können sehen, dass die erwartete Anzahl solcher unglücklichen Menschen 1 ist, so dass dies ziemlich häufig vorkommt.

Zu diesem Zweck scheint die Entfremdung gut zu passen. Wenn ich eine Entfremdung fair erzeugen kann, kann ich einfach eine Entfremdung auswählen und damit entscheiden, wer wem Geschenke gibt.

Mit der Las Vegas-Methode könnte eine zufällige Erzeugung von Entfremdungen durchgeführt werden. Das Problem ist jedoch, dass nur eine polynomielle Laufzeit erwartet wurde. Also kam ich zu diesem Problem, die i-te Entfremdung zu finden. Wenn ich in [1, D_n] zufällig ein i auswählen und einen (effizienten) Algorithmus für die Polynomzeit im ungünstigsten Fall verwenden kann, um die i-te Fehlanordnung zu erhalten, ist dies erledigt.

permutations Santa Zhang
quelle
1
Könnten Sie bitte die Motivation für die Frage erklären? dh warum interessiert dich diese frage?
Kaveh
2
Vielleicht möchten Sie Secret Santa spielen und sind nicht bereit, ein
Risiko einzugehen
Könnten Sie eine Zeile darüber hinzufügen, was Sie unter Entfremdung verstehen?
Vijay D

Antworten:

9

Eigentlich mag dies eine gute Frage sein, aber sie ist in ihrer aktuellen Form schlecht formuliert. Die bekannten Algorithmen zum Erzeugen zufälliger Störungen haben eine lineare erwartete Zeit, aber vielleicht ist es ein offenes Problem, einen Polynomzeitalgorithmus im ungünstigsten Fall zu finden.

Siehe zum Beispiel: http://www.siam.org/proceedings/analco/2008/anl08_022martinezc.pdf (und Folien: http://www.lsi.upc.edu/~conrado/research/talks/analco08.pdf )

tatest
quelle
Dies scheint mir die richtige Antwort zu sein.
Suresh Venkat
10
Führt die in en.wikipedia.org/wiki/Derangement beschriebene Wiederholung! N = (n - 1) (! (N - 1) +! (N - 2)) nicht sofort zu einem Worst-Case-Polynomalgorithmus für Zufälle Generation?
David Eppstein
Ja, du hast recht. Ich dachte, es gibt einen kleinen Haken, weil man in der Lage sein muss, Zufallszahlen in beliebigen Teilmengen von {1, ..., n} im schlimmsten Fall zu generieren, aber das ist einfach.
Didest
0

Warum nicht für jede Position i zufällig aus allen Elementen außer i auswählen ? Sie können beispielsweise einen Index für das ursprüngliche Array aus [0..n-2] auswählen , und wenn Sie j> = i erhalten, verwenden Sie j + 1 .

klopfen
quelle
3
Macht das alle Störungen gleich wahrscheinlich?
David Eppstein
Oh, guter Punkt - dies würde Elemente später im Array platzieren, vorzugsweise früher im Array. Wenn Sie Slots im Zielarray in zufälliger Reihenfolge füllen würden, wären alle Störungen gleich wahrscheinlich (symmetrisch).
Pat