c++ - 字符串与重复字符的排列(访问数组概念)

Question

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
          }
    }
}

上面提到的代码正在为字符串“aab”生成以下排列。

aab
aba
aab
aba
baa
baa

一些置换后的字符串是否重复？我怎样才能减少它？链接到我的 code .

Answer 1

你正在使用 C++，所以 std:next_permutation是你最好的 friend 。

如果您想从头开始实现排列，请使用 algorithm description for the next lexicographic permutation .请注意，该算法适用于重复元素。

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].

任意 c++ implementation