PHP : X 문자 26 자의 순열

Question

26 자 A..Z의 알파벳 배열이 있습니다.

반복되는 문자없이 길이가 X 인 배열을 채우는 모든 순열을 나열하는 실행 알고리즘을 찾고 있습니다.

예 :

X = 3. 대상 배열 : _ _ _

순열은 Z Y X까지 A B C입니다.

X = 4. 대상 배열 : _ _ _ _

순열은 Z X Y W

X = 5까지의 B의 C D이다. 대상 배열 : _ _ _ _ _

순열은 A B C 형 D의 E 될 때까지 Z Y X W V

(미안 해요, 난 알고리즘 이런 종류의 이름은 방법을 모른다) 미리

감사합니다.

C, Delphi 또는 Java의 코드도 쉽게 번역 할 수 있기 때문에 OK입니다.

Answer 1

숫자가 26이므로 순열의 수를 이해할 수 있지만 간단한 무차별 대입 방식을 택할 것입니다!/(26-x)! 3은 15,600 순열이고, 5는 7,893,600 순열이며, 그 크기는 작지 않습니다. 기본적으로 당신은 불행하게도 O (n^x)가되는 루프의 루프를 가지고 모든 값을 반복 할 수 있습니다. 여기서 x는 복잡성을 유발하는 루프의 중첩 이후 문자 수입니다.

---

여기서 고려해야 할 사항은 복잡성을 얼마나 정밀하게 검토하고 있는지입니다. 예를 들어, 중복을 피하기 위해 루프의 첫 번째 쌍에서 영리 해지는 방법을 고려할 수 있지만 26 번째 글자로 시작하여 이전 목록을 제거하면 세 번째 루프가 조금 더 까다로워집니다. 마지막 루프는 외부 루프에서 각 패스의 목록을 복사해야하는 데 소모되는 메모리 측면에서 비용이 많이 들지만 중복이 없다는 것을 알기 때문에 단순히 반복적으로 수행해야합니다. 따라서 처음으로 AB_를 거친 다음 AC_ 등을 거치지 만 목록을 복사하면 목록이 복사되어 수천 번에 걸쳐 작업이 고비용이 될 수 있습니다. 그것이 비교를하는 것보다 더 효율적이라면.

Answer 2

모든 순열을 확인 하시겠습니까? X = 3 인 경우 26 * 25 * 24 조합 = 15600이됩니다. X = 5이면 조합 수는 7893600입니다.

임의로 문자 하나 (또는 ​​배열 색인)를 선택하고 저장해야합니다 어딘가에 그리고 각 반복마다 이전 반복 중 하나에서이 문자 (또는 색인)가 이미 선택되었는지 확인해야합니다. 이 후에 길이가 X자인 무작위 순서가 생깁니다. 당신도 그것을 저장해야합니다. 그런 다음 이전 단계에서 수행 한 모든 작업을 다시 작성해야하며 현재 생성 한 하위 순서가 무작위로 반복되는지 확인해야합니다.

직접 열거 형을 사용할 수도 있습니다.

죄송합니다. 영어는 만족스럽지 않습니다. 나는 분명히하려고 노력했다.

유용하게 사용되기를 바랍니다.

Answer 3

간단한 해결책 함수가 상기 계산하는 문자와 조합하여 총 문자 수 n (코드 i<n 가정)의 인덱스 i를 수용 재귀 하나

char current_combination[27]; 
int char_used[26]; 

void enumerate(int i, int n) 
{ 
    for (int j=0; j<26; j++) 
    { 
     if (!char_used[j]) 
     { 
      char_used[j] = 1; 
      current_combination[i] = 'A' + j; 
      if (i+1 == n) 
      { 
       puts(current_combination); 
      } 
      else 
      { 
       enumerate(i+1, n); 
      } 
      char_used[j] = 0; 
     } 
    } 
} 

이다. 전역 변수에서 이미 사용 된 변수에 대한 플래그의 배열과 배열을 복사하지 않도록합니다.

예를 들어 길이 5의 모든 조합을 생성하려면 enumerate(0, 5)을 호출하십시오.

조합의 총 수는 이됩니다. 예를 들어 n=6의 경우 165,765,600 개의 조합이 있으며 1Gb 이상의 출력이 있습니다.