可重集的排列

permutation_with_repeated_item.c

#include <stdio.h>                                                                                                                    
#include <stdlib.h>                                                                                                                                 
static void print_permutation_r(char S[], int n, int cur, char P[])                                                      
{                                                                                                                                     
    int i, j;                                                                                                                         
    if (cur == n) { // 收敛条件                                                                                                       
        for (i = 0; i < n; i++)                                                                                                       
            printf("%c ", P[i]);          
        printf("\n");                                                                                                                 
    }                                                                                                       
    for (i = 0; i < n; i++) {                                                                                                         
        if( i == 0 || S[i] != S[i-1] )                                                                                                
        {                                                                                                                             
            int c1 = 0;                                                                                                               
            int c2 = 0;                                                                                                               
            int j;                                                                                                                    
            for( j = 0; j < cur; ++j ){                                                                                               
                if( P[j] == S[i] )                                                                                                    
                    c1++;                                                                                                             
            }                                                                                                                         
            for(j = 0; j < n; ++j ){                                                                                                  
                if( S[j] == S[i] )                                                                                                    
                    c2++;                                                                                                             
            }                                                                                                                 
            if( c1 < c2 ){                                                                                                            
                P[cur] = S[i];                                                                                                     
                print_permutation_r(S, n, cur+1, P);                                                                          
            }                                                                                                                         
        }                                                                                                                             
    }                                                                                                                                 
}
void print_permutation(char S[], int n) {                                                                                             
    char *P = (char*)malloc(n * sizeof(char));                                                                                        
    print_permutation_r(S, n, 0, P); 
    free(P);                                                                                                                          
    return;                                                                          
}                                                                                                                              
int main() {                                                                                                                          
    char* S="AAA";                                                                                                                    
    print_permutation(S, 3);                                                                                                          
    return 0;                                                                                                                         
}