[C++知识库]C语言学习-19-全排列

一、测试环境

二、个人理解

假设数据：{1，2，3}进行全排列。
我们可以先分为三种情况：

（1）以1为开头的组合

{1，{剩下元素进行全排列}}

（2）以2为开头的组合

{2，{剩下元素进行全排列}}

（3）以3为开头的组合

{3，{剩下元素进行全排列}}

也就是说每个元素都要放到首位，剩余的元素进行全排列，有没有感觉规律很明显，可以用递归的方式尝试解决，编写递归函数时，
一：我们需要找到规律。
二：我们需要找到结束点。
一我们已经找到我们来开始找二。

中间剩下元素进行全排列，又可以分为两种情况（这里以第一组为例）：

（1）以2为开头的组合

{2，{剩下元素进行全排列}}

（2）以3为开头的组合

{3，{剩下元素进行全排列}}

最后就剩下一个元素了，说明数组已经遍历完，可以结束，这样我们就找到了结束条件。

三、源码

#include <stdio.h>
#include <time.h>

void PrintArray(int Array[], int ArraySize);
void SwapArrayElement(int Array[], int index_1, int index_2);
void AllPermutaion(int Array[], int top, int end);
void ComputeProcedureTime(void(*Func)(int*, int, int), int Array[], int index_1, int index_2);

int main() 
{
    int Array[] = { 1 ,2 ,3 };
    int ArraySize = sizeof(Array) / sizeof(int);
    ComputeProcedureTime(AllPermutaion, Array, 0, ArraySize - 1);
}

void ComputeProcedureTime(void (*Func)(int[], int, int), int Array[], int index_1, int index_2)
{
    printf("++++++++++++++++++++++++\n");
    clock_t start, finish;
    clock_t Total_time;
    start = clock();

    Func(Array, index_1, index_2);

    finish = clock();
    Total_time = finish - start;
    printf("Elapsed Time : %ld ms\n", Total_time);
}

void PrintArray(int Array[], int ArraySize)
{
    int i;
    for ( i = 0; i < ArraySize; i++)
    {
        printf("%d ",Array[i]);
    }
    printf("\n");
}

void SwapArrayElement(int Array[], int index_1, int index_2)
{
    //如果位置相等，说明是同一个元素，不用进行交换，可以稍微提升一点效率。
    if (index_1 != index_2)
    {
        int temp = Array[index_1];
        Array[index_1] = Array[index_2];
        Array[index_2] = temp;
    }
}

void AllPermutaion(int Array[], int top, int end)
{
    //如果位置相等，说明数组里的元素已经遍历完，我们可以打印一下数组结果。
    if (top == end)
    {
        PrintArray(Array, end + 1);
    }
    else
    {
        int i;
        for ( i = top; i <= end; i++)
        {
            SwapArrayElement(Array, i, top);
            AllPermutaion(Array, top + 1, end);
            SwapArrayElement(Array, i, top);
            //交换两次元素，是为了避免出现重复结果。
        }
    }
}

四、测试结果

++++++++++++++++++++++++
1 2 3
1 3 2
2 1 3
2 3 1
3 2 1
3 1 2
Elapsed Time : 3 ms