What is optimal algorithm to make all possible combinations of a string?

Question

I find other similar question too complicated.

I think it means if we are given pot then combinations will be pot opt top pot pto pot

so I wrote the following code:

#include<iostream>
#include<string.h>
using namespace std;

int main(){

    char s[10];
    char temp;
    cin>>s;
    char t[10];
    for(int i=0;i<3;i++)
    {
        for(int j=i;j<3;j++)
        {

            strcpy(t,s);
            temp=s[i];
            s[i]=s[j];
            s[j]=temp;

            cout<<s<<"\n";
            strcpy(s,t);
        }
    }

Is there a better way ?

Your code works only for three-letter words. You cannot make it do a four-letter word without adding an extra loop. That should explain all the extra complexity of the "other algorithms" that you have seen. — Sergey Kalinichenko, Jul 13 '12 at 14:33
Do u mean other similar questions or answers since there are common variants to this question . — Rndm, Jul 13 '12 at 14:37
In your example `otp` and `tpo` are missing, `pot` is given three times. Did not check your code, but if that is its output and you mean to generate all permutations of the letters in a string, it might be wrong. — Wolfram, Jul 13 '12 at 14:37
okay I admit I messed up the code algorithm, please give the correct code. — Anubha, Jul 13 '12 at 14:47
I am pretty sure the code I have provided below will work, it uses C malloc and free instead of C++ new and delete though. — trumpetlicks, Jul 13 '12 at 15:16
Possible duplicate: http://stackoverflow.com/q/4240080/1071136 — user1071136, Jul 13 '12 at 15:34

trumpetlicks · Accepted Answer · 2012-07-13T16:19:50.137

This problem is inherently an O(N!) (factorial) complexity problem. The reason is that for each position of each potential word, there will be a decrementing amount of possibilities of characters that can fill the position, An example with 4 letters a, b, c, and d.

           -----------------
Positions: | 0 | 1 | 2 | 3 |
           -----------------

In position 0, there are 4 possibilities, a, b, c, or d

Lets fill with a

        -----------------
String: | a |   |   |   |
        -----------------

Now Position 1 has 3 possibilities of fill letters b, c, or d

Lets fill with b

        -----------------
String: | a | b |   |   |
        -----------------

Now Position 2 has 2 possibilities of fill letters c, or d

Lets fill with c

        -----------------
String: | a | b | c |   |
        -----------------

Now Position 1 has only 1 possibility for a fill letter: d

        -----------------
String: | a | b | c | d |
        -----------------

This is only for 1 string, the complexity comes from (in this case) the potential possibilities that can fill a character location for a given output word, thus:

4 * 3 * 2 * 1 = 4!

This can be extended to any amount of input letters and is exactly N! if there are no repeat letters. This also represents the AMOUNT OF WORDS you should result with.

Code to perform something like this could be (TESTED AND WORKING IN C):

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

#define TRUE  1
#define FALSE 0

void printPermutations(int level, const char * inString, char * outString){

    unsigned int len = strlen(inString);
    char * unusedLetter;
    int j;

    if( 1 == len ){
        printf("%s%s\n", outString, inString);
    }else{
        unusedLetters = (char *)malloc(sizeof(char) * (len - 1));

        for(int startLetter = 0; startLetter < len; startLetter++){

            outString[level] = inString[startLetter];

            // setup the "rest of string" string
            j = 0;
            for(int i = 0; i < len; i++){ 
                if( i != startLetter ){        
                    unusedLetter[j] = inString[i];
                    j++;
                }
            }

            // recursive call to THIS routine
            printPermutations(level+1, unusedLetters, outString);
        }
    }
}

int main(int argc, char * argv[]){
    unsigned int len;
    char * outString;

    if(argc != 2) return 0;

    len = strlen(argv[1]);
    outString      = (char *)malloc(sizeof(char) * (len + 1));
    outstring[len] = '\0';

    printPermutations(0, argv[1], outString);

    return 0;
}

From outside, call this as follows:

projectName abc

sample output from using "abc"

abc
acb
bac
bca
cab
cba

If there are repeat letters lets say a, a, b, c

then there will ALWAYS be repeat words.

With these cases, the amount of UNIQUE result words should be the amount of unique characters factorial, so for the above case it would be 3! not 4!.

The reason for this is that it does not matter WHICH of the a's fills a given spot and thus the uniqueness is given be the amount of unique letters provided. This is also a hard problem, and in ways I would say you should generate ALL N! words first, then run a second algorithm to search for the repeat words and delete. There may be smarter ways of generating the unique words on the fly.

So does this mean O(n!) is the only possible solution and no optimization possible? — Ayusman, Aug 15 '13 at 02:53

score 3 · Answer 2 · answered Jul 13 '12 at 20:04

The following solution is O(N!).This takes repetitions into account too :

    #include<stdio.h>
    void permute(char s[10],char *p);
    int count=0;

    main(){
        char s[10];
        int i;
        scanf("%s",s);
        permute(s,s);
        }

    //takes into account repetetion
    void permute(char s[10],char *p){
        char *swap,temp;
        if(*(p+1)==0) {
            count++;
            printf("%4d] %s\n",count,s);
        }
        else{
            for(swap=p;*swap;++swap){
                char *same;
                for(same=p;*same!=*swap;++same){};
                if(same==swap){
                temp=*swap;
                *swap=*p;
                *p=temp;
                permute(s,p+1);
                *p=*swap;/*restoring the original string*/
                *swap=temp;
                }
            }
        }
    }

What is optimal algorithm to make all possible combinations of a string?

2 Answers2

Linked