枚举全排列(包括数列中有重复数)的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);
}

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/71b591118a9518718894e8b07751650a.html