Algorithm to print String Permutations - Running Time Analysis

Question

I have the following code to print permutations of a given string. [For simplicity and not to loose focus on what I am trying, lets assume there are not duplicates characters in the string]

public static int count = 0;

public static void permute(String soFar, String strLeft) {

    if(strLeft.length() == 1) {
        soFar += strLeft;
        System.out.println(++count + " :: " + soFar);
    }

    for(int i=0; i<strLeft.length(); i++) {
        permute(soFar + strLeft.charAt(i), strLeft.substring(0,i) + strLeft.substring(i+1));
    }
}

/**
 * @param args
 */
public static void main(String[] args) {
    String input = "abcd";
    permute("",input);
}

I am trying to figure out the running time of this code.

My chain of thoughts so far: Trying to write a recurrence,

T(n) = n * T(n-1) + O(n) for n > 1
     = 1                 for n = 1

There are n! permutations, but the number of recursive calls are greater than n!. In-fact for the example where input string is "abcd" , i.e. 4 characters, the number of calls to the permute function is 65.

Any pointers on how I should go about finding the running time of this code?

What's greater - the number of calls to the method, or the amount of numbers that it will output during its runtime? — Makoto
– Makoto, Commented Mar 5, 2013 at 2:15
Duplicate/Similar question? stackoverflow.com/questions/11425344/… — apnorton
– apnorton, Commented Mar 5, 2013 at 2:16
@anorton - yes, this does look like a duplicate. Thanks! I am going through the answer in the other thread and will mark this as closed. — Anurag Kapur
– Anurag Kapur, Commented Mar 5, 2013 at 2:18
@AnuragKapur No problem. Interestingly enough--I just saw that other question no more than 15 minutes ago while researching one of my questions. I thought I was seeing double when your question popped up... :) — apnorton
– apnorton, Commented Mar 5, 2013 at 2:19
Hmm, so the solution on the other thread uses WolframAlpha solution to the recurrence. Does that mean, there isn't an easy way to calculate this recurrence solution on paper? — Anurag Kapur
– Anurag Kapur, Commented Mar 5, 2013 at 2:29

alzaimar · Accepted Answer · 2013-03-05 07:43:09Z

2

Well, first of all, you make redundant calls. If there is only one character left, you emit a solution. But then you will still call permute with an empty string and spoils the calling count.

My first improvement would be to add an else to the if clause.

public static void permute(String soFar, String strLeft) {

    if(strLeft.length() == 1) {
        soFar += strLeft;
        System.out.println(++count + " :: " + soFar);
    }
    else {
        for(int i=0; i<strLeft.length(); i++) {
            permute(soFar + strLeft.charAt(i), strLeft.substring(0,i) + strLeft.substring(i+1));
        }
    }
}

This cuts down the amount of calls to 41. And to count the number of calls, construct the calling tree and count the nodes. As each call is done by removing one character from the string, there are:
1 calls of length 4,
4 calls of length 3,
12 calls of length 2 and
24 calls of length 1

Which sums up to 41. Voilá.

answered Mar 5, 2013 at 7:43

alzaimar

4,6321 gold badge22 silver badges31 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Anurag Kapur Over a year ago

Thanks. So the general solution for a problem of size n would be: n!/1! + n!/2! + ... + n!/n!

Anurag Kapur Over a year ago

I still don't know how to convert the above general solution into corresponding Big-Oh, but it was more important for me to understand a relation representing how the problem or the recursive calls proliferate. So a +1 to your answer and I have marked it as accepted. Thanks!

Collectives™ on Stack Overflow

Algorithm to print String Permutations - Running Time Analysis

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related