CODEWITHSUNDEEP
c++stringmathpermutation
DCoder
DCoder

Reputation: 137

Permutation of string with repeated characters(visited array concept)

void per(int count){

    if(count==l){
       printf("%s\n", p);
       return;
    }

    for(int i=0;i<l;i++){
          if(visit[i]==0 ){
          visit[i]=1;
          p[count]=arr[i];
          per(count+1);
          visit[i]=0;   //backtrack
          }
    }
}

Above mentioned code is generating for string "aab", the following permutation.

aab
aba
aab
aba
baa
baa

Some permuted string are repeated? How can I reduce it? Link to my code.

Upvotes: 0

Views: 166

Answers (1)

MBo
MBo

Reputation: 80187

You are using C++, so std:next_permutation is your best friend.

If you want to implement permutations from scratch, use algorithm description for the next lexicographic permutation. Note that algorithm works well with repeated elements.

Find the largest index k such that a[k] < a[k + 1]. If no such index exists, 
   the permutation is the last permutation.

Find the largest index l greater than k such that a[k] < a[l].

Swap the value of a[k] with that of a[l].

Reverse the sequence from a[k + 1] up to and including the final element a[n].

Arbitrary c++ implementation

Upvotes: 1

Related Questions