가능한 모든 문자열 조합을 만들기위한 최적의 알고리즘은 무엇입니까?

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!) (계승) 복잡성 문제입니다. 그 이유는 각 잠재적 단어의 각 위치마다 위치를 채울 수있는 문자의 감소 가능성이 있기 때문입니다. 예를 들어 a, b, c 및 d 4자를 사용할 수 있습니다.

4 * 3 * 2 * 1 = 4! 

것은이 될 수

  ----------------- 
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 문자열위한 복잡성 때문에, 소정의 출력 단어의 문자 위치를 채울 수있는 잠재적 인 가능성 (이 경우)로부터 온다 입력 문자의 어떤 금액으로 확장하고 정확하게 N입니다! 반복 문자가없는 경우. 이것은 또한 귀하가 결과로 가져야하는 단어의 금액을 나타냅니다.

projectName abc 

샘플 출력을 "ABC"

를 사용 :

코드는이 (테스트 일하는 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 
acb 
bac 
bca 
cab 
cba 

반복되는 문자가 있으면 a, a, b, c라고 말하십시오.

다음 반복 단어가 항상있을 것입니다.

이러한 경우 UNIQUE 결과 단어의 양은 고유 한 문자의 계승 값이어야합니다. 위의 경우 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; 
       } 
      } 
     } 
    }