Что такое оптимальный алгоритм для создания всех возможных комбинаций строки?

Question

Я нахожу другой подобный вопрос слишком сложным.

Я думаю, что это означает, что если мы дали горшок, то комбинации будут горшком неавтоматических верхнего горшок ВОМ горшка

поэтому я написал следующий код:

#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

Эта проблема по своей сути является проблемой О (N!) (Факторной) сложности. Причина в том, что для каждой позиции каждого потенциального слова будет уменьшающееся количество возможностей символов, которые могут заполнить позицию. Пример с четырьмя буквами 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; 
} 

Снаружи, называют это следующим образом: выход

projectName abc 

образца с помощью "ABC"

abc 
acb 
bac 
bca 
cab 
cba 

Если есть повторяющиеся буквы, скажем a, a, b, c

тогда ВСЕГДА будут повторяться слова.

В этих случаях количество УНИКАЛЬНЫХ слов результата должно быть количеством уникальных символов факториалом, поэтому для вышеуказанного случая это будет 3! не 4 !.

Причина этого в том, что не имеет значения, какой из а заполняет данное место, и, таким образом, уникальность дается количеством уникальных букв. Это тоже тяжелая проблема, и я бы сказал, что вы должны генерировать ALL 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; 
       } 
      } 
     } 
    }