Komplexität zum Generieren von Permutationen einer Zeichenkette

Question

Ich versuche herauszufinden, wie die Komplexität eines Codes (aus Cracking the Coding Interview Buch) zum Generieren aller Permutationen einer gegebenen Zeichenkette O (n!) Ist.

Ich weiß, dass das die bestmögliche Komplexität ist, wie wir n haben! Permutationen, aber ich würde es gerne codeweise verstehen, denn nicht jeder Algorithmus, der dies tut, wäre O (n!).

Der Code:

import java.util.*; 

public class QuestionA { 

    public static ArrayList<String> getPerms(String str) { 
     if (str == null) { 
      return null; 
     } 
     ArrayList<String> permutations = new ArrayList<String>(); 
     if (str.length() == 0) { // base case 
      permutations.add(""); 
      return permutations; 
     } 

     char first = str.charAt(0); // get the first character 
     String remainder = str.substring(1); // remove the first character 
     ArrayList<String> words = getPerms(remainder); 
     for (String word : words) { 
      for (int j = 0; j <= word.length(); j++) { 
       String s = insertCharAt(word, first, j); 
       permutations.add(s); 
      } 
     } 
     return permutations; 
    } 

    public static String insertCharAt(String word, char c, int i) { 
     String start = word.substring(0, i); 
     String end = word.substring(i); 
     return start + c + end; 
    } 

    public static void main(String[] args) { 
     ArrayList<String> list = getPerms("abcde"); 
     System.out.println("There are " + list.size() + " permutations."); 
     for (String s : list) { 
      System.out.println(s); 
     } 
    } 

} 

Dies ist, was ich jetzt, bis gedacht habe: Zu jedem Funktionsaufruf, die Anzahl der Worte zur Verfügung steht (n-1); Angenommen, wir befinden uns an einem Ort, wo der Rest die Länge hat (n-1). Um nun das n-te Element an allen möglichen Stellen für alle diese (n-1) Wörter einzufügen, braucht man (n-1) * (n-1) Zeit.

so über die Ausführung sollte es sein (n-1)^2 + (n-2)^2 + (n-3)^2 + .... 2^2 + 1^2 Operationen, die Ich denke nicht, ist n !.

Was habe ich hier vermisst?

Answer 1

Ich denke, die Zeit Komplexität von getPerms ist O((n + 1)!).

Wir bezeichnen die Laufzeit von getPerms durch T(n), wobei n die Länge des Eingangs ist.

============================================== ====================

Die beiden if Filialen und die Linie char first = str.charAt(0) dauert O(1) Zeit. Und die folgende Zeile nimmt O(n) Zeit:

String remainder = str.substring(1); // remove the first character 

die nächste Zeile braucht Zeit T(n - 1):

ArrayList<String> words = getPerms(remainder); 

Nun betrachten wir die Laufzeit des verschachtelten for-loops. Die Größe des äußeren for-loop ist (n-1)!:

for (String word : words) { 

und die Größe des inneren for-loop ist n + 1:

for (int j = 0; j <= word.length(); j++) { 

und die Komplexität der insertCharAt ist auch O(n).

Also die Gesamtlaufzeit des verschachtelten for-loops ist (n + 1) * (n - 1)! * O(n) = O((n + 1)!).

Deshalb haben wir die folgende Beziehung:

 
T(n) = T(n - 1) + O(n) + O((n + 1)!) 
    = T(n - 1) + O(n) + O((n + 1)!) 
    = (T(n - 2) + O(n - 1) + O(n!) + O(n) + O((n + 1)!) 
    = T(n - 2) + (O(n - 1) + O(n)) + (O(n!) + O((n + 1)!)) 
    = ... 
    = O(n2) + (1 + ... + O(n!) + O((n + 1)!)) 
    = O((n + 1)!) 

Answer 2

Wenn Sie dies studieren, wäre es besser, die allgemeinen Lösungen und nicht nur die Umsetzung in Ihrem Beispiel präsentiert zu lernen. Sedgewick hat die beste Analyse gemacht, die ich kenne. Ich unterrichte es in meiner Klasse.

https://www.cs.princeton.edu/~rs/talks/perms.pdf

Die Komplexität von jedem Aufruf der Funktion erzeugen, ist O (n). Daher sind die Kosten O (n!).

Der von Ihnen eingegebene Code ist äußerst ineffizient. Es gibt einen großen konstanten Faktor, weil Sie viele String-Objekte und ein Array erstellen und das ist eines der ineffizientesten Dinge, die Sie in Java machen können.

Wenn Sie einfach alle Permutationen durchlaufen möchten, permutieren Sie eine einzelne Entität, erstellen Sie keine Liste. Hier ist eine schnellere Implementierung:

public class Permute { 
    private int[] a; 
    private void swap(int i, int j) { 
     int temp = a[i]; 
     a[i] = a[j]; 
     a[j] = temp; 
    } 
    public Permute(int n) { 
     a = new int[n]; 
     for (int i = 0; i < n; i++) 
      a[i] = i+1; 
     this.generate(n); 
    } 
    public void generate(int N) { 
     //  System.out.println("generate(" + N + ")"); 
     if (N == 0) doit(); 
     for (int c = 0; c < N; c++) { 
      //   System.out.print("Swapping: " + c + "," + N); 
      swap(c, N-1);       //swap(0, 7) 
      generate(N-1); 
      //   System.out.print("Swapping: " + c + "," + N); 
      swap(c, N-1); 
     } 
    } 
    public void doit() { 
     for (int i = 0; i < a.length; i++) 
      System.out.print(a[i] + " "); 
     System.out.println(); 
    } 

    public static void main(String[] args) { 
     Permute p = new Permute(4); 
    } 
} 

andere Methode, die Sedgewick zeigt ist Heaps, die nur eine Swap pro Permutation statt 2. Hier ist eine C++ Implementierung:

#include <vector> 
#include <iostream> 

using namespace std; 
class Heaps { 
private: 
    vector<int> p; 
public: 
    Heaps(int n) { 
     p.reserve(n); 
     for (int i = 0; i < n; i++) 
      p.push_back(i+1); 
     generate(n); 
    } 
    void doit() { 
     cout << "doit size=" << p.size() << '\n'; 
     for (int i = 0; i < p.size(); i++) 
      cout << p[i]; 
     cout << '\n'; 
    } 
    void generate(int N) { 
     //  cout << "generate(" << N << ")\n"; 
    if (N == 0) 
      doit(); 
    for (int c = 0; c < N; c++) { 
      generate(N-1); 
      swap(p[N % 2 != 0 ? 0 : c], p[N-1]); 
     } 
    } 
}; 


int main() { 
    Heaps p(4); 
}