歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

枚舉全排列(包括數列中有重復數)的C語言實現

據說是用了DFS的思想……然鵝並不知道這是DFS。

主要就是選取一個數放到數組相應位置上,然後遞歸的排列剩下的數組,將剩下的數組遞歸排列完了之後再把數放回去,然後這一層遞歸就返回了……

有重復數的話遇到重復的不要重復放置就好了……

//
//  main.c
//  Full Permutation
//
//  Created by 余南龍 on 2016/12/13.
//  Copyright © 2016年 余南龍. All rights reserved.
//

#include <stdio.h>

void Swap(int *a, int *b){
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

void Output(int A[], int size){
    int i;
   
    for(i = 0; i < size; i++){
        printf("%d ", A[i]);
    }
    putchar('\n');
}

void Full_Permutation(int A[], int begin, int end, int p_size){
    int i;
   
    if(begin >= p_size){
        Output(A, p_size);
    }
    else{
        for(i = begin; i <= end; i++){
            Swap(A + begin, A + i);
            Full_Permutation(A, begin + 1, end, p_size);
            Swap(A + begin, A + i);
        }
    }
}

void Full_Permutation_Duplicate(int A[], int begin, int end, int p_size){
    int i, j;
   
    if(begin >= p_size){
        Output(A, p_size);
    }
    else{
        for(i = begin; i <= end; i++){
            for(j = begin; j < i; j++){
                if(A[j] == A[i]){
                    break;
                }
            }
            if(i == j){
                Swap(A + begin, A + i);
                Full_Permutation_Duplicate(A, begin + 1, end, p_size);
                Swap(A + begin, A + i);
            }
        }
    }
}

int main() {
    int A[6] = {1, 2, 3, 4, 5, 6};
    int B[5] = {1, 1, 2, 2, 3};
   
    Full_Permutation(A, 0, 5, 3);
    Full_Permutation_Duplicate(B, 0, 4, 5);
}

Copyright © Linux教程網 All Rights Reserved