permutations and combinations

Question

I have a program which creates some combinations of strings like if I entered input abc it gives me output as bca cab abc

#include<stdio.h>
#include<string.h>
int main()
{
    char str[15];
    int i,j,n;

    printf("Enter a string");
    scanf("%s",str);
    n=strlen(str);

    for(i=0;i<n;i++)
    {
        str[n]=str[0];

        for(j=0;j<n;j++)    
        {
            str[j]=str[j-1];
        }
    str[n]='\0';
    printf("\n %s \n",str);
    }
    return 0;
}

But I want a program which gives me all possible combinations of a string so what are the changes I need to make?

http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations — President James K. Polk, Aug 22 '10 at 23:41
http://stackoverflow.com/questions/361/generate-list-of-all-possible-permutations-of-a-string — Brandon Horsley, Aug 22 '10 at 23:42
Unless the number of letters in `str` is fixed to a small value (and 14 as in your code is not very small), you'd better use recursion at some point, otherwise it might get tedious. — Pascal Cuoq, Aug 22 '10 at 23:42

score 7 · Answer 1 · answered Aug 23 '10 at 00:15

Use the Exeter algorithm

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

void swap(char *x, char *y){
    char w;
    w = *x;
    *x = *y;
    *y = w;
}

void permute(char *str, int start, int n){
    int i;

    if(start == n-1)
        printf("%s\n", str);
    else
        for(i = start; i < n; i++){
            swap(str+i, str+start);
            permute(str, start+1, n);
            swap(str+i, str+start);
        }
}

int main(){

    char line[10], str[10];
    int n, op;

    printf("Enter a string: ");
    if( fgets(line, 10, stdin) == NULL ){
        printf("Ops! Early stop\n");
        return 1;
    }


    if( sscanf(line, "%s", str) != 1 ){
        printf("Next time put some valid characters\n");
        return 1;
    }

    n = strlen(str);
    permute(str, 0, n);
    return 0;
}

Note: This algorithm generates all the possibles permutations

permutations and combinations

1 Answers1