Time complexity of this code to list all permutations?

Question

For example, if the input string is “ABC”, then output should be “ABC, ACB, BAC, BCA, CAB, CBA”.

Here is my approach :

#include<stdio.h>
#include<conio.h>
#include<string.h>

void print(char str[],int visited[],int index,char temp[],int len)
{



    if(index==len)
    {
        temp[index]='\0';
        printf("\n%s",temp);
        return;
    }


    for(int i=0;i<len;i++)
    {
        if(!visited[str[i]-'A'])
        {
            visited[str[i]-'A']=1;
            temp[index]=str[i];
            print(str,visited,index+1,temp,len);
            visited[str[i]-'A']=0;
        }
    }


}

int main()
{
    int visited[20]={0};
    char temp[20];
    char str[] = "ABCD";
    int len=strlen(str);
    print(str,visited,0,temp,len);

    getch();
    return 0;
}

I have made use of a visited array to avoid repetition of characters. What will be the complexity of this code?

@Rapptz i am aware of that function. But i wanted to know what the running time of this code is. — nikola, Oct 11 '13 at 05:23
Are you sure you want to tag this as C++? This looks like C to me. — Rapptz, Oct 11 '13 at 05:30
Normally, the complexity of this problem will be n!/(a!)*(b!) ... with a , b, .. is the number of appearances of a specific character in the string. — Pham Trung, Oct 11 '13 at 08:11

templatetypedef · Accepted Answer · 2013-10-11T20:58:54.193

If you let n be the total number of characters available and k be the number of characters not yet picked, then you can see that each function call does Θ(n) work (either by iterating over the array of length len or by printing out a string of length len), then spawns off k recursive calls. The total work done per call is always Θ(n), so we can count the total work done by looking at how many total calls are made.

Notice that there will be

1 call with k = n,
n calls with k = n - 1,
n(n-1) calls with k = n - 2,
n(n-1)(n-2) calls with k = n - 3,
...
n! / k! calls for arbitrary k

So the total number of calls is given by the sum

sum from k = 0 to n (n! / k!)

= n! (sum from k = 0 to n (1 / k!))

An interesting observation is that the summation here is the Taylor expansion for e (1/0! + 1/1! + 1/2! + 1/3! + ... ), truncated a bit early. Therefore, as n gets large, the number of calls made asymptotically approaches e n!. It's also lower-bounded by n!, so this summation is Θ(n!). Since you're done Θ(n) work per call, the total amount of work done is therefore Θ(n · n!).

Hope this helps!

@user2549925- Think about the amount of time required to send each character to the screen. The more characters you have, the more time is required to display them. — templatetypedef, Oct 16 '13 at 17:36

Axel Kemper · Answer 2 · 2013-10-11T09:39:09.873

1

Running your code and listing the number of print() calls depending on the length of the string to permute, I've got:

n=1 calls=2
n=2 calls=5
n=3 calls=16
n=4 calls=65
n=5 calls=326
n=6 calls=1957
n=7 calls=13700
n=8 calls=109601
n=9 calls=986410
n=10 calls=9864101
n=11 calls=108505112

That looks like "e * n!".

edited Oct 11 '13 at 09:39

answered Oct 11 '13 at 09:06

Axel Kemper

10,544
2
31
54

Have you try String with duplicate characters? like aabbbccc? – Pham Trung Oct 11 '13 at 09:09
No, I always started with a sorted alphabet string like "ABCDEF". 'No repetition' is mentioned in the question title. – Axel Kemper Oct 11 '13 at 09:13
The visited array is for that purpose , I think :) I guess that the no repetition here means that there is no string that appear twice :) – Pham Trung Oct 11 '13 at 09:16
1

I have tried "AAB" without success (no output). The procedure seams to be restricted to strings without repeated characters. – Axel Kemper Oct 11 '13 at 10:34
Oh yes, because of his final check index==len, so your answer is correct :D – Pham Trung Oct 11 '13 at 11:04

Time complexity of this code to list all permutations?

2 Answers2

Linked