Complexity for generating permutations of a string

Question

I am trying to figure out how the complexity of a code(from Cracking the Coding Interview book) for generating all the permutations of a given string is O(n!).

I know that that's the best possible complexity as we have n! permutations but I would like to understand it codewise, because not every algorithm that does this would be O(n!).

The 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); } } }

This is what I have thought untill now : At any function call , the number of words available is (n-1) ; assuming we are at a place where remainder is of length (n-1). Now to insert the nth element in all possible places for all of these (n-1) words takes (n-1)*(n-1) time.

so across the execution , it should be (n-1)^2+(n-2)^2+(n-3)^2+....2^2+1^2 operations, which I don't think is n!.

What did I miss here?

I don't know if I am right but I think it is O((N+1)!) ?

shole
– shole

2016-11-24 03:53:03 +00:00
Commented Nov 24, 2016 at 3:53 — shole
– shole, Commented Nov 24, 2016 at 3:53

chiwangc · Accepted Answer · 2016-11-24 04:00:09Z

I think the time complexity of getPerms is O((n + 1)!).

We denote the running time of getPerms by T(n), where n is the length of the input.

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

The two if branches and the line char first = str.charAt(0) takes O(1) time. And the following line takes O(n) time:

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

the next line takes time T(n - 1):

ArrayList<String> words = getPerms(remainder);

Now we consider the running time of the nested for-loops. The size of the outer for-loop is (n-1)!:

for (String word : words) {

and the size of the inner for-loop is n + 1:

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

and the complexity of insertCharAt is also O(n).

So the total running time of the nested for-loops is (n + 1) * (n - 1)! * O(n) = O((n + 1)!).

Therefore we have the following relationship:

 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(n²) + (1 + ... + O(n!) + O((n + 1)!) ) = O((n + 1)!)

@Down Voter, please explain the reason for down-voting so that I can improve my answer

Dov · Accepted Answer · 2016-11-24 04:52:39Z

If you are studying this, it would be better to learn the general solutions rather than just the implementation presented in your example. Sedgewick did the best analysis I know. I teach it in my class.

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

The complexity of each invocation of the generate function is O(n). Therefore the cost is O(n!).

The code you present is extremely inefficient. There is a huge constant factor because you are creating lots of string objects an array and that is one of the most inefficient things you can do in Java.

If you simply want to go through all permutations, permute a single entity, don't generate a list. Here is a faster implementation:

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); } }

Another method that Sedgewick shows is Heaps, which is only one swap per permutation instead of 2. Here is a C++ implementation:

#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); }

Collectives™ on Stack Overflow

Complexity for generating permutations of a string

2 Answers 2

1 Comment

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Related