什么是最佳算法，使所有可能的字符串组合？

Question

我发现其他类似的问题太复杂了。

我认为，这意味着，如果我们给出锅然后组合将 锅 选择 顶部 锅 PTO 锅

所以我写了下面的代码：

#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); 
     } 
    } 

是否有更好的方法 ？

Answer 1

这个问题本质上是O（N！）（因子）复杂性问题。原因在于，对于每个潜在单词的每个位置，会有一个递减的可能性填充该位置的字符，这个例子有4个字母a，b，c和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 | 
     ----------------- 

这仅是1串，所述复杂性来自（在这种情况下），可以填充一个字符位置对于给定的输出字，从而潜在可能性：

4 * 3 * 2 * 1 = 4! 

这可以是扩展到任意数量的输入字母，并且正好是N！如果没有重复的字母。这也代表了你应该得到的数量的话。像这样，可以（经测试和工作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; 
} 

从外部调用此如下：使用 “ABC”

projectName abc 

样本输出

abc 
acb 
bac 
bca 
cab 
cba 

如果有重复的字母可以说a，a，b，c

那么总会有重复的话。

在这些情况下，UNIQUE结果字的数量应该是唯一字符factorial的数量，因此对于上述情况，它应该是3！不是4 !.

其原因在于，a的哪一个填满给定的位置并不重要，因此唯一性是给定的唯一字母的数量。这也是一个难题，而且我会说你应该生成所有N！先运行单词，然后运行第二个算法搜索重复单词并删除。在飞行中产生独特的词语可能有更聪明的方法。 。

Answer 2

下面的解决方案是O（N！）这需要反复考虑过：

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