Ich versuche, die ganze Kombination von zwei Arrays zu finden, aber mit einer wichtigen Variation:
Jeder Wert des zweiten Arrays muss über die Werte des ersten verteilt werden. Daher werden immer alle Werte des zweiten Arrays verwendet.
Gegeben diese zwei Arrays:
%Vor%Ich erwarte eine Sammlung der folgenden Ergebnisse:
%Vor%Bearbeiten:
Also nur um klar zu sein. Dies muss für beide Arrays skaliert werden.
Gegebene Arrays:
%Vor%Einige der (viele, viele mögliche) Ergebnisse wären:
%Vor%Lösung für jeden Parameter (solange das Ergebnis zählbar ist)
Bearbeiten : Diese Version vermeidet ein mögliches Problem mit len = Math.pow(left.length, right.length) und das Problem mit der Länge über 36 (cnr!).
Wie es funktioniert:
Beispiel:
%Vor%combine(['A', 'B'], [1, 2, 3])alle möglichen Zeilen sind 2 ^ 3 = 8. Die Verteilung ist in diesem Beispiel binär, aber mit mehr Parametern vonleftändert sie die Basis.Die Verteilung
i = 3von0 1 1wird wie folgt ausgewertet:
- Nimm das erste
0und nimm es als Index des linkenleft[0] = Aund verschiebe den Platzwert von 0 von rechtsright[0] = 1auf A.- Nimm das zweite
1und nimm es als Index des linkenleft[1] = Bund verschiebe den Place-Wert von 1 des rechtenright[1] = 2auf B.- Nimm das dritte
1und nimm es als Index des linkenleft[1] = Bund verschiebe den Platzwert von 2 von rightright[2] = 3auf B.Ein anderes Beispiel:
%Vor%combine(['A', 'B', 'C'], [1, 2])Alle möglichen Zeilen sind 3 ^ 2 = 9.
Ich denke, ich habe eine mögliche Lösung gefunden, aber ich bin mir sicher, dass es bei weitem nicht effizient ist.
Gegeben die Arrays:
%Vor%Erstellen Sie zuerst eine Potenzmenge von rechts :
%Vor%Dann haben Sie für jeden Wert in left verschachtelte Schleifen. Jede Schleife prüft, ob der Wert bereits in der vorherigen Schleife ist und die letzte Schleife prüft auch, ob alle Werte vorhanden sind.
In psuedo würde das ungefähr so aussehen:
%Vor%Bearbeiten
Hier ist diese beschissene ineffiziente Lösung in Javascript. Veröffentlichen Sie es für den Abschluss Willen.
%Vor%Ich glaube, dass Ihr Problem so umformuliert werden kann: Erzeugen Sie alle möglichen Zuweisungen von Labels in left zu den Elementen in right . Dies ist ein Standard-Backtracking-Problem.
Die Anzahl der Lösungen ist l ^ r (da Sie jedem Element unabhängig voneinander beliebige Beschriftungen zuweisen können), wobei l die Anzahl der Elemente in
Ich werde eine rekursive Lösung bereitstellen, die Sie vielleicht auf nicht-rekursive Weise umschreiben können, obwohl dies nicht die Komplexität des Algorithmus (vielleicht die Konstante) verringert. Es gibt eigentlich keine Möglichkeit, die Komplexität zu verringern, da Sie irgendwann jede Lösung generieren müssen. Also teste es nicht für l = 20 und r = 20 , probiere kleinere Zahlen aus: p
%Vor% Nur zur Veranschaulichung, das ist eine Version von @ NinaScholz
Antwort, die toString für die Basiskonvertierung nicht verwendet oder
Zählen manuell durchführen. Ich habe die Struktur der. Behalten
gleich codieren. values.length-i-1 könnte einfach 'ich' sein, aber
Ich wollte auch die Reihenfolge der Ausgabe beibehalten.
Tags und Links javascript algorithm arrays recursion