순열 문자

Question

2 문자 P 및 C와 N- 가감 번호 (짝수) 예. 만약 N = 4 => CCPP, PPCC, CPPC, PCCP, CPCP, PCPC (아이디어는 단지 Ps의 no = Cs = no의 이런 종류의 해결책을 보여 주어야한다)

Answer 1

순열 C에서

Live example here

int N; 
cin >> N; 
string str = string(N/2, 'C') + string(N/2, 'P'); 
do { 
    cout << str << endl; 
} while(next_permutation(str.begin(), str.end())); 

, 당신은 permutation function 자신을 작성해야합니다.

typedef int bool; 
bool true = 1; 
bool false = 0; 

int compare (const void *a, const void * b) 
{ return (*(char *)a - *(char *)b); } 

void swap (char* a, char* b) 
{ 
    char t = *a; 
    *a = *b; 
    *b = t; 
} 

// This function finds the index of the smallest character 
// which is greater than 'first' and is present in str[l..h] 
int findCeil (char str[], char first, int l, int h) 
{ 
    // initialize index of ceiling element 
    int ceilIndex = l, i; 

    // Now iterate through rest of the elements and find 
    // the smallest character greater than 'first' 
    for (i = l+1; i <= h; i++) 
     if (str[i] > first && str[i] < str[ceilIndex]) 
      ceilIndex = i; 

    return ceilIndex; 
} 
// Print all permutations of str in sorted order 
void permute (char str[]) 
{ 
    // Get size of string 
    int size = strlen(str); 

    // Print permutations one by one 
    bool isFinished = false; 
    while (! isFinished) 
    { 
     int i; 
     // print this permutation 
     printf ("%s \n", str); 

     // Find the rightmost character which is smaller than its next 
     // character. Let us call it 'first char' 
     for (i = size - 2; i >= 0; --i) 
      if (str[i] < str[i+1]) 
       break; 

     // If there is no such chracter, all are sorted in decreasing order, 
     // means we just printed the last permutation and we are done. 
     if (i == -1) 
      isFinished = true; 
     else 
     { 
      // Find the ceil of 'first char' in right of first character. 
      // Ceil of a character is the smallest character greater than it 
      int ceilIndex = findCeil(str, str[i], i + 1, size - 1); 

      // Swap first and second characters 
      swap(&str[i], &str[ceilIndex]); 

      // Sort the string on right of 'first char' 
      qsort(str + i + 1, size - i - 1, sizeof(str[0]), compare); 
     } 
    } 
} 

int main(void) { 
    int N; 
    char *a = NULL; 
    if(1 != scanf("%d\n", &N)) { 
     fprintf(stderr, "Can not read the value of N\n"); 
     return 1; 
    } 
    a = malloc(N + 1); 
    if(!a) { 
     fprintf(stderr, "Out of mem\n"); 
     return 1; 
    } 
    memset(a, 'C', N/2); 
    memset(a + N/2, 'P', N/2); 
    a[N] = '\0'; 
    permute(a, 0, strlen(a) - 1); 
    free(a); 
    return 0; 
} 

Live Example here