


Wie kann ich alle Permutationen eines Arrays mithilfe rekursiver und nicht rekursiver Algorithmen generieren?
Permutation eines Arrays: Eine ausführliche Erklärung
Um Permutationen eines Arrays zu generieren, ist es wichtig zu verstehen, wie die Elemente angeordnet sind. Bei einer Permutation werden die Array-Elemente neu angeordnet, um neue Sequenzen zu erstellen. Die Anzahl der möglichen Permutationen für ein Array mit n Elementen wird durch n! angegeben.
Rekursiver Algorithmus
Eine Möglichkeit, Permutationen zu generieren, ist die Verwendung eines rekursiven Ansatzes, bei dem Sie Tauschen Sie Elemente iterativ aus und wenden Sie Permutationen auf die verbleibenden Array-Elemente an.
public static void permute(java.util.List<Integer> arr, int k) { for (int i = k; i < arr.size(); i++) { java.util.Collections.swap(arr, i, k); permute(arr, k + 1); java.util.Collections.swap(arr, k, i); } if (k == arr.size() - 1) { System.out.println(java.util.Arrays.toString(arr.toArray())); } }
Dieser Algorithmus beginnt mit Austauschen des ersten Elements mit jedem der verbleibenden Elemente. Anschließend wird dieselbe Operation rekursiv auf die verbleibenden Elemente angewendet. Nach jedem rekursiven Aufruf werden die Elemente wieder an ihre ursprünglichen Positionen vertauscht.
Nicht-rekursiver Algorithmus
Berücksichtigen Sie für einen iterativen Ansatz die folgenden Schritte:
- Beginnen Sie mit dem in aufsteigender Reihenfolge sortierten Array.
- Suchen Sie das erste Index, bei dem die Sequenz nicht absteigend ist (d. h. wenn a[i] < a[i-1]).
- Suchen Sie den letzten Index, bei dem der Wert größer oder gleich a[i-1] ist ].
- Tauschen Sie a[i-1] mit dem Element am letzten Index.
- Kehren Sie die Reihenfolge der Elemente am Ende des Arrays um (nach dem Index). i-1).
Beispiel: Permutieren eines Arrays [3, 4, 6, 2, 1]
Rekursiver Algorithmus:
- Tausch 3 mit 4: [4, 3, 6, 2, 1]
- Rekursiv permutieren [4, 3, 6, 2, 1]
- Tausch 3 mit 6: [4, 6, 3, 2, 1]
- Rekursiv permutieren [4, 6, 3, 2, 1]
- Fahren Sie fort, bis alle Permutationen generiert sind
Nicht-rekursiver Algorithmus:
- Beginnen Sie mit [1, 2, 3, 4, 6] (aufsteigend sortiert)
- Die Reihenfolge ist absteigend, also Fahren Sie mit Schritt 3 fort
- Suchen Sie den ersten Index, bei dem a[i] < a[i-1]: i = 4, da 3 < 4
- Finden Sie den letzten Index, bei dem a[j] >= a[i-1]: j = 5, da 6 >= 3
- Vertauschen Sie a[i-1] mit a[j]: [1, 2, 6, 3, 4, 5]
- Kehren Sie das Ende des Arrays um: [1, 2, 3, 4, 5, 6]
- Wiederholen Sie die Schritte 3-6, bis das Array in absteigender Reihenfolge vorliegt (was anzeigt, dass alle Permutationen generiert wurden)
Das Ergebnis für beide Algorithmen ist dasselbe: alle möglichen Permutationen werden generiert und gedruckt.
Das obige ist der detaillierte Inhalt vonWie kann ich alle Permutationen eines Arrays mithilfe rekursiver und nicht rekursiver Algorithmen generieren?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Heiße KI -Werkzeuge

Undresser.AI Undress
KI-gestützte App zum Erstellen realistischer Aktfotos

AI Clothes Remover
Online-KI-Tool zum Entfernen von Kleidung aus Fotos.

Undress AI Tool
Ausziehbilder kostenlos

Clothoff.io
KI-Kleiderentferner

Video Face Swap
Tauschen Sie Gesichter in jedem Video mühelos mit unserem völlig kostenlosen KI-Gesichtstausch-Tool aus!

Heißer Artikel

Heiße Werkzeuge

Notepad++7.3.1
Einfach zu bedienender und kostenloser Code-Editor

SublimeText3 chinesische Version
Chinesische Version, sehr einfach zu bedienen

Senden Sie Studio 13.0.1
Leistungsstarke integrierte PHP-Entwicklungsumgebung

Dreamweaver CS6
Visuelle Webentwicklungstools

SublimeText3 Mac-Version
Codebearbeitungssoftware auf Gottesniveau (SublimeText3)

Heiße Themen











Fehlerbehebung und Lösungen für die Sicherheitssoftware des Unternehmens, die dazu führt, dass einige Anwendungen nicht ordnungsgemäß funktionieren. Viele Unternehmen werden Sicherheitssoftware bereitstellen, um die interne Netzwerksicherheit zu gewährleisten. ...

Lösungen zum Umwandeln von Namen in Zahlen zur Implementierung der Sortierung in vielen Anwendungsszenarien müssen Benutzer möglicherweise in Gruppen sortieren, insbesondere in einem ...

Die Verarbeitung von Feldzuordnungen im Systemdocken stößt häufig auf ein schwieriges Problem bei der Durchführung von Systemdocken: So kartieren Sie die Schnittstellenfelder des Systems und ...

Bei Verwendung von MyBatis-Plus oder anderen ORM-Frameworks für Datenbankvorgänge müssen häufig Abfragebedingungen basierend auf dem Attributnamen der Entitätsklasse erstellt werden. Wenn Sie jedes Mal manuell ...

Beginnen Sie den Frühling mit der Intellijideaultimate -Version ...

Konvertierung von Java-Objekten und -Arrays: Eingehende Diskussion der Risiken und korrekten Methoden zur Konvertierung des Guss-Typs Viele Java-Anfänger werden auf die Umwandlung eines Objekts in ein Array stoßen ...

Detaillierte Erläuterung des Designs von SKU- und SPU-Tabellen auf E-Commerce-Plattformen In diesem Artikel werden die Datenbankdesignprobleme von SKU und SPU in E-Commerce-Plattformen erörtert, insbesondere wie man mit benutzerdefinierten Verkäufen umgeht ...

Wie erkennt die Redis -Caching -Lösung die Anforderungen der Produktranking -Liste? Während des Entwicklungsprozesses müssen wir uns häufig mit den Anforderungen der Ranglisten befassen, z. B. das Anzeigen eines ...
