c语言全排列算法_五大常见算法策略之——递归与分治策略

在C语言中，全排列算法可以使用递归和分治策略来实现。下面是一种使用递归策略的算法实现：

#include <stdio.h>
#include <string.h>

void swap(char *x, char *y)
{
    char temp = *x;
    *x = *y;
    *y = temp;
}

void permute(char *str, int start, int end)
{
    if (start == end)
        printf("%s\n", str);
    else
    {
        for (int i = start; i <= end; i++)
        {
            swap(str + start, str + i);
            permute(str, start + 1, end);
            swap(str + start, str + i);
        }
    }
}

int main()
{
    char str[] = "ABC";
    int n = strlen(str);
    permute(str, 0, n - 1);
    return 0;
}

该算法的基本思路是将字符串中的每个字符依次与它后面的字符交换，然后对每个交换后的字符串递归执行相同的操作。

具体实现时，使用一个函数`swap`来交换两个字符，另一个函数`permute`则用来生成所有的排列。在`permute`函数中，首先判断当前是否已经排列到了最后一个字符，如果是，则输出当前排列的字符串。否则，从当前字符开始，依次将它与后面的字符交换，并对交换后的字符串递归调用`permute`函数，直至排列到最后一个字符。

使用分治策略实现全排列算法的思路与递归策略相似，只不过在分治策略中，将问题划分为若干个子问题，并对每个子问题递归求解。这里不再赘述。