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

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