Finden aller Permutationen, die mit einem Regelsatz übereinstimmen

Ich habe N Nummern und für sie gelten M Regeln über ihre Reihenfolge. Die Regeln sind in einem Paar von Indizes dargestellt und jedes Paar (A, B) sagt, dass die Nummer mit dem Index A (A-te Nummer) NACH der B-ten Nummer sein muss - es muss nicht neben ihm sein .Finden aller Permutationen, die mit einem Regelsatz übereinstimmen

Ex: N = 4 
    1 2 3 4 
    M = 2 
    3 2 
    3 1 

Output: 1234, 4213, 4123, 2134, 2143, 2413, 1423 ...Maybe there are even more:)

Der Algorithmus sollte alle gibt mir die Permutationen zur Verfügung, die in dem Beispiel nicht die Regeln brechen, wie - 3 immer nach 2 und nach dem 1.

ich bruteforcing versucht sein muss, aber es didn‘ t Arbeit (obwohl Bruteforce sollte hier arbeiten, N ist im Bereich (1,8).)

Irgendwelche Ideen?

Quelle

2010-02-27 VaioIsBorn

Könnten Sie erklären, wie die N-Nummern in diese kommen? Was wäre die Antwort, wenn die Ns {1, 2, 3, 4} sind? –

Von dem, was ich sehen kann, sind die N Zahlen, die Sie erhalten, für die Frage, die Sie stellen, irrelevant. Ist das richtig? – sykora

N ist, wie viele Zahlen es gibt, in diesem Fall N = 4, weil es vier Zahlen gibt, 1..4. – VaioIsBorn

Nur als Hinweis.

Sie können Ihr Regelwerk als Diagramm behandeln. Jeder Index ist ein Eckpunkt, jede Regel ist eine gerichtete Kante.

Jede richtige Reihenfolge der Zahlen (d.h. eine Permutation, die die Regeln genügt) entspricht, so topological ordering des obigen Graph aufgerufen. Um alle gültigen Ordnungen Ihrer Zahlen zu generieren, müssen Sie alle möglichen topologischen Ordnungen dieses Graphen generieren.

P.S. Der erste Algorithmus für die topologische Ordnung, der auf der verlinkten Wikipedia-Seite gegeben wird, erlaubt bereits eine ziemlich einfache Lösung, die alle gültigen Permutationen aufzählen würde. Es wird einige Anstrengungen und einige Sorgfalt erfordern, aber es ist keine Hexenwerk.

Quelle

2010-02-27 00:44:59 AnT

Als Schritt vor dem vollständigen topologischen Sortieren können Sie zumindest geordnete Fragmente erstellen, um das Brute-Forcing zu vereinfachen. Zum Beispiel, wenn die Vorrangregeln sind: 3,4 4,5 5,8 Sie wissen, dass Sie [3458] mit wird vorangestellt, Einsätze und anhängt Ihrer ganzen Zahlen ungezwungen von Vorrangregeln (dies natürlich verallgemeinert permutieren kann in die oben genannten) –

Brute Forcing wäre going through every permutation, das ist O (N!), Und für jede Permutation einfach durch jede Regel durchlaufen, um zu bestätigen, dass sie aplpy, die O (M) ist. Dies führt zu O (N! M), was irgendwie lächerlich ist, aber für so ein kleines Set sollte es nicht "nicht funktionieren".

Quelle

2010-02-27 00:49:08 Tanzelax

tatsächlich konnte er die Regeln überprüfen, während Permutationen erstellen. Dies würde die Zeit erheblich verkürzen, und er würde mit einem Ergebnis enden. – Kugel

Ich stimme zu. Wenn N = 8 die höchste ist, die Sie bewältigen müssen, dann ist es wahrscheinlich nicht Ihre Zeit wert, etwas Besseres zu finden als Brute-Force für so etwas. –

Ja, es gibt definitiv eine Menge einfacher Optimierungen für eine Brute-Force-Lösung, aber er erwähnt, dass er selbst damit Probleme hat. – Tanzelax

Ehrlich gesagt ist Ihre beste Wette, zurückzugehen und die Brute-Force-Lösung zum Laufen zu bringen. Sobald das erledigt ist (und wenn Sie noch Zeit haben, usw.) können Sie nach einem besseren Algorithmus suchen.

EDIT zu den Down-Voter. Der Student ist (sollte sein) versuchen, seine Hausaufgaben rechtzeitig zu bekommen. Laut seinen Hausaufgaben ist seine Hausaufgabe eine Programmierübung, bei der eine Brute-Force-Lösung angemessen wäre. Ihm zu helfen, einen effizienten Algorithmus zu finden, adressiert sein REALES Problem nicht.

In diesem Fall hat er versucht, die einfache Brute-Force-Ansatz (der alle einig für kleine Werte N arbeiten sollte) und es vorzeitig aufgegeben, um etwas zu versuchen, das wahrscheinlich schwieriger ist. Jeder erfahrene Entwickler wird Ihnen sagen, dass dies eine schlechte Idee ist. Der Schüler braucht und verdient es, dass ihm das erzählt wird, und wenn er vernünftig ist, wird er aufpassen. Aber offensichtlich, es ist seine Wahl ...

Quelle

2010-02-27 01:14:03

@serial_downvoter: Hat dich abgesagt. Ha ha! –

Finden aller Permutationen, die mit einem Regelsatz übereinstimmen

Antwort

Verwandte Themen