CareerCup

This code is on the same logic by which anyone will permute manually. Its intuitive !
Hold one character and permute others, proceed recursively.

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

void doPermuteString(char in[], char out[], int used[], int length,  int recurselev){

        int i;

        if(recurselev == length){
                printf("%s\n", out);
                return;
        }

        for(i=0;i<length;i++){

                if(used[i])     continue;

                out[recurselev] = in[i];
                used[i] = 1;
                doPermuteString(in, out, used, length, recurselev + 1);
                used[i] = 0;
        }
}

int permuteString(char string[]){

        int i, length, *used;
        char *out;

        length = strlen(string);

        out = (char *)malloc(sizeof(char) * (length + 1));
        out[length] = '\0';

        used = (int *)malloc(sizeof(int) * length);
        for(i=0;i<length;i++){
                used[i] = 0;
        }

        doPermuteString(string, out, used, length, 0);

        free(out);
        free(used);
        return 1;
}

int main(){

        char string[100];
        scanf("%s", string);
        permuteString(string);
        return 0;
}

#include<iostream>
#include<string>
using namespace std;
void permute(string s, int i = 0) {
    if (i == s.size()) cout << s << endl;
    else for (int j = i; j < s.size(); ++j) swap(s[i], s[j]), permute(s, i + 1), swap(s[i], s[j]);
}

Sorry for the extra newlines...

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

void doPermuteString(char in[], char out[], int used[], int length,  int recurselev){

        int i;

        if(recurselev == length){
                printf("%s\n", out);
                return;
        }

        for(i=0;i<length;i++){

                if(used[i])     continue;

                out[recurselev] = in[i];
                used[i] = 1;
                doPermuteString(in, out, used, length, recurselev + 1);
                used[i] = 0;
        }
}

int permuteString(char string[]){

        int i, length, *used;
        char *out;

        length = strlen(string);

        out = (char *)malloc(sizeof(char) * (length + 1));
        out[length] = '\0';

        used = (int *)malloc(sizeof(int) * length);
        for(i=0;i<length;i++){
                used[i] = 0;
        }

        doPermuteString(string, out, used, length, 0);

        free(out);
        free(used);
        return 1;
}

int main(){

        char string[100];
        scanf("%s", string);
        permuteString(string);
        return 0;
}

why doesn't the formatting works properly ?? huh

what's the time complexity ?

@anonymous ...your solution is the best/smartest one...rest sucks..why the hell people like writing pages and pages of stuffs when it can be done in just 2 lines.... anony, u rock buddy. thanks for the nice solution!

String can contains repeat chars.

Mr Ankit Gupta has plaigarised the code from programming interviews exposed.. i hope no one catches him:

@arh are u an asshole ? no one ever said that whatever code you write has got to be a unique code in the world. You learn things from somewhere and if you like, you will reproduce it somewhere else...

the 2 line is a extra ordinary code.r u in adobe ;)

I don't know but 2 line code doesn't seem to work :( I tried with swap pass by value.

May be its duplicate...but its tested

void swap(int *ar, int pos1, int pos2);
void permute(int *ar, int start, int ar_len);
main()
{
int ar[]={1,2,3,4,5,6,7,8}; /*Just as an example */
int len = 8;
permute(ar, 0, len);
return 0;
}


void swap(int *ar, int pos1, int pos2)
{
int temp = 0;
temp = ar[pos1];
ar[pos1]= ar[pos2];
ar[pos2] = temp;
}

void permute(int *ar, int start, int ar_len)
{
int i = 0, j = 0;
if (start == (ar_len-1)) {
while(i<ar_len){
printf("%d",ar[i++]);
}
printf("\n");
}
for (i=start; i<=(ar_len-1);i++) {
swap(ar, start, i);
j = 0;
permute(ar, start+1, ar_len);
swap(ar, start, i);
}
}

what if the original string has duplicate characters? how do you generate/print out unique strings without caching previous string in memory?