Wie generiert man alle Permutationen eines Arrays, einschließlich derjenigen mit wiederholten Elementen?

Generieren aller Permutationen eines Arrays

Bei einem Array mit unterschiedlichen Elementen besteht das Ziel darin, alle möglichen Permutationen der Array-Elemente aufzulisten.

Algorithmus

Der folgende Algorithmus generiert alle Permutationen in O(N!)-Zeit Komplexität:

1. Initialisieren: i = 0 setzen.
2. Über Array iterieren: Während i kleiner als die Array-Länge ist:
3. Tauschen: Tauschen Sie das Element am Index i mit jedem der verbleibenden Elemente im aus Array.
4. Rekursiv: Rufen Sie den Algorithmus rekursiv mit i 1 als neuem i-Wert auf.
5. Zurücktauschen: Nach dem rekursiven Aufruf tauschen Das Element kehrt in seine ursprüngliche Position zurück.
6. Inkrementieren i:Inkrementieren i um 1.

Python-Implementierung

def permute(arr, i=0):
    if i == len(arr) - 1:
        print(arr)
        return

    for j in range(i, len(arr)):
        arr[i], arr[j] = arr[j], arr[i]
        permute(arr, i + 1)
        arr[i], arr[j] = arr[j], arr[i]

Jarvis-March-Algorithmus

Für Arrays mit wiederholten Elementen ist der Jarvis-March-Algorithmus ein effizienterer Ansatz:

1. Sortieren: Sortieren Sie das Array aufsteigend Reihenfolge.
2. Während: Während noch nicht erledigt:
3. Pivot finden:Suchen Sie den größten Index, bei dem das Element kleiner als sein Nachfolger ist.
4. Nachbar suchen:Suchen Sie das letzte Element im sortierten Teil, das größer als das Element am Drehpunkt ist Index.
5. Vertauschen: Vertauschen Sie die Elemente am Pivot und angrenzenden Indizes.
6. Umkehren: Kehren Sie die Elemente vom Pivot-Index bis zum Ende um des sortierten Teils.
7. Prüfung erledigt:Überprüfen Sie, ob das Array in absteigender Reihenfolge sortiert ist. Wenn ja, verlassen Sie die Schleife.

Python-Implementierung

def permute_repeated(arr):
    ind = [0] * len(arr)
    for i in range(len(arr)):
        ind[i] = i

    while True:
        yield [arr[i] for i in ind]

        for i in range(len(arr) - 2, -1, -1):
            if ind[i] < ind[i + 1]:
                break

        if i == -1:
            return

        for j in range(len(arr) - 1, -1, -1):
            if arr[j] > arr[i]:
                ind[i], ind[j] = ind[j], ind[i]
                break

        ind[i + 1:] = sorted(ind[i + 1:])

Das obige ist der detaillierte Inhalt vonWie generiert man alle Permutationen eines Arrays, einschließlich derjenigen mit wiederholten Elementen?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!