首页 > 算法

全排列问题（非常详细，附带源码）

 
全排列问题是非常经典的算法问题，它要求罗列出指定集合中全部元素所有可能的排列情况。

例如，集合 {1, 2, 3} 的全排列包括： 
{1, 2, 3}
{1, 3, 2}
{2, 1, 3}
{2, 3, 1}
{3, 1, 2}
{3, 2, 1}

集合中也可能存在相同的元素，例如集合 {1, 1, 2} 的全排列包括： 
{1, 1, 2}
{1, 2, 1}
{2, 1, 1}

无论集合中是否含有重复的元素，全排列问题都可以用回溯算法解决，接下来给大家做详细地讲解。

无重复元素集合的全排列

这里以查找 {1, 2, 3} 的全排列为例，带大家理解回溯算法解决全排列问题的过程。

回溯算法查找 {1, 2, 3} 全排列的过程是： 
从 {1, 2, 3} 开始，选择元素 1：
    从 {2, 3} 中选择元素 2：
        从 {3} 中选择元素 3，找到了 {1, 2, 3} 排列；
    回溯到 {2,3}，选择元素 3：
        从 {2} 中选择元素 2，找到了 {1, 3, 2} 排列；
    回溯到 {2, 3}，无可选元素，再次回溯；
回到 {1, 2, 3}，选择元素 2：
    从 {1, 3} 中选择元素 1：
        从 {3} 中选择元素 3，找到了 {2, 1, 3} 排列；
    回溯到 {1,3}，选择元素 3：
        从 {1} 中选择元素 1，找到了 {2, 3, 1} 排列；
    回溯到 {1, 3}，无可选元素，再次回溯；
回到 {1, 2, 3}，选择元素 3：
    从 {1, 2} 中选择元素 1：
        从 {2} 中选择元素 2，找到了 {3, 1, 2} 排列；
    回溯到 {1,2}，选择元素 2：
        从 {1} 中选择元素 1，找到了 {3, 2, 1} 排列；
    回溯到 {1, 2}，无可选元素，再次回溯；
回到 {1, 2, 3}，无可选元素，回溯算法结束。
整个过程中，为了确保集合中的元素不被重复选择，需要记录各个元素的选中状态。如果集合中的元素全部被选中了，表明成功找到了一种排列。

下面是采用回溯算法查找 {1, 2, 3} 全排列的 C 语言程序： 
#include <stdio.h>
#define SIZE 3

// 用于跟踪哪些数字已被使用的标记数组
int used[SIZE] = { 0 };
// 存储当前排列结果的数组
int result[SIZE] = { 0 };
// 当前已选择数字的数量
int selNums = 0;

// 打印当前排列的函数
void printArr(int result[SIZE]) {
    for (int i = 0; i < SIZE; i++) {
        printf("%d ", result[i]);
    }
    printf("\n");
}

// 生成排列的函数
void permute(int arr[SIZE]) {
    // 检查是否所有数字都已被选择
    if (selNums == SIZE) {
        printArr(result);
        return;
    }
    // 遍历所有可能的选择
    for (int i = 0; i < SIZE; i++) {
        // 如果数字已被使用，跳过
        if (used[i]) {
            continue;
        }
        // 选择当前数字，并标记为已使用
        used[i] = 1;
        result[selNums++] = arr[i];
        // 递归调用，继续选择下一个数字
        permute(arr);
        // 回溯：撤销选择，并将数字标记为未使用
        selNums--;
        used[i] = 0;
    }
}

int main() {
    int array[] = { 1, 2, 3 };
    // 调用排列函数
    permute(array);
    return 0;
}
used[] 数组用来记录集合里各个元素的选中状态，值为 1 代表选中，值为 0 代表没有选中。result[] 数组用来存储选中的元素，当集合的所有元素都被选中时（数组的元素个数等于集合的元素总数量），表明成功找到了一种排列。

运行程序，执行结果为：

1 1 3
1 3 1
1 1 3
1 3 1
3 1 1
3 1 1


注意，此程序只适用于无重复元素的集合。如果将 main() 函数里的 array[] 数组改成： 
int array[] = { 1, 1, 2 };
再次执行程序，结果为：

1 1 2
1 2 1
1 1 2
1 2 1
2 1 1
2 1 1

原本 {1, 1, 2} 的全排列情况只有 3 种，现在却出现了 6 种，每种情况输出了两次。也就是说，对于存在相同元素的集合，程序中缺少查重的机制。

有重复元素集合的全排列

对于有重复元素的集合，前面的程序也能找到全排列，只不过缺少查重的机制，每种排列可以找到多次。接下来，带大家尝试修改前面的程序，让它也适用于有重复元素的集合。

以 {1, 1, 2} 为例，观察前面的程序查找全排序的过程： 
从 {1, 1, 2} 开始，选择第一个元素 1：
    从 {1, 2} 中选择第二个元素 1：
        从 {2} 中选择元素 2，找到了 {1, 1, 2} 排列；
    回溯到 {1,2}，选择元素 2：
        从 {1} 中选择第二个元素 1，找到了 {1, 2, 1} 排列；
    回溯到 {1, 2}，无可选元素，再次回溯；
回到 {1, 1, 2}，选择第二个元素 1：
    从 {1, 2} 中选择第一个元素 1：
        从 {2} 中选择元素 2，找到了 {1, 1, 2} 排列；
    回溯到 {1,2}，选择元素 2：
        从 {1} 中选择第一个元素 1，找到了 {1, 2, 1} 排列；
    回溯到 {1, 2}，无可选元素，再次回溯；
回到 {1, 1, 2}，选择元素 2：
    从 {1, 1} 中选择第一个元素 1：
        从 {1} 中选择第二个元素 1，找到了 {2, 1, 1} 排列；
    回溯到 {1,1}，选择第二个元素 1：
        从 {1} 中选择第一个元素 1，找到了 {2, 1, 1} 排列；
    回溯到 {1, 1}，无可选元素，再次回溯；
回到 {1, 1, 2}，无可选元素，回溯算法结束。
其中，飘红部分是没必要执行的，正因为程序中没有过滤掉这些飘红的过程，才导致每种排列多找到了一次。

过滤掉飘红的过程，给大家分享一种方法：首先把集合中的元素排好序（升序或者降序），然后开始查找全排序。对于尚未被选中的元素，如果它和前一个元素相等，并且前一个元素处于未选中状态，就跳过这次查找过程。

下面是按照此方法在 {1, 1, 2} 中查找全排序的过程： 
对 {1, 1, 2} 进行升序排序；
从 {1, 1, 2} 开始，选择第一个元素 1：
    从 {1, 2} 中选择第二个元素 1，由于前一个元素 1 处于选中状态，所以继续执行：
        从 {2} 中选择元素 2，找到了 {1, 1, 2} 排列；
    回溯到 {1,2}，选择元素 2：
        从 {1} 中选择第二个元素 1，由于前一个元素 1 处于选中状态，所以继续执行，找到了 {1, 2, 1} 排列；
    回溯到 {1, 2}，无可选元素，再次回溯；
回到 {1, 1, 2}，选择第二个元素 1，由于它和前一个元素 1 相等，并且前一个元素 1 处于未选中状态，所以跳过此过程；  
回到 {1, 1, 2}，选择元素 2：
    从 {1, 1} 中选择第一个元素 1：
        从 {1} 中选择第二个元素 1，由于前一个元素 1 处于选中状态，所以继续执行，找到了 {2, 1, 1} 排列；
    回溯到 {1,1}，选择第二个元素 1，由于它和前一个元素 1 相等，并且前一个元素 1 处于未选中状态，所以跳过此过程；
    {1, 1}中无可选元素，再次回溯；
回到 {1, 1, 2}，无可选元素，回溯算法结束。
由此，就成功过滤掉了所有飘红的过程。

下面是修改后的 C 语言程序，它既能满足在无重复元素的集合中查找全排序，也能满足在有重复元素的集合中查找全排序：
#include <stdio.h>
#include <stdlib.h>
#define SIZE 3

// 用于跟踪哪些数字已被使用的标记数组
int used[SIZE] = { 0 };
// 存储当前排列结果的数组
int result[SIZE] = { 0 };
// 当前已选择数字的数量
int selNums = 0;

// 打印当前排列的函数
void printArr(int result[SIZE]) {
    for (int i = 0; i < SIZE; i++) {
        printf("%d ", result[i]);
    }
    printf("\n");
}

// 生成排列的函数
void permute(int arr[SIZE]) {
    // 检查是否所有数字都已被选择
    if (selNums == SIZE) {
        printArr(result);
        return;
    }
    // 遍历所有可能的选择
    for (int i = 0; i < SIZE; i++) {
        // 如果当前数字已使用，或者当前数字与前一个数字相同并且前一个数字未被使用，则跳过
        if (used[i] || (i != 0 && arr[i] == arr[i - 1] && used[i - 1] == 0)) {
            continue;
        }
        // 选择当前数字，并标记为已使用
        used[i] = 1;
        result[selNums++] = arr[i];
        // 递归调用，继续选择下一个数字
        permute(arr);
        // 回溯：撤销选择，并将数字标记为未使用
        selNums--;
        used[i] = 0;
    }
}

int cmp(void* elem1, void* elem2) {
    return *((int*)elem1) - *((int*)elem2);
}

int main() {
    int array[] = { 1,2, 1 };
    // 对集合进行排序
    qsort(array, SIZE, sizeof(int), cmp);
    // 调用排列函数
    permute(array);
    return 0;
}
和前面的程序相比，此程序只做了两处改动：
  • 调用 permute() 函数之前，对 array[] 数组中的元素进行了排序；
  • 在 permute() 函数中，为 for 循环内的 if 语句增加了一种判断条件，就是(i != 0 && arr[i] == arr[i - 1] && used[i - 1] == 0)。

下面是解决全排序问题的 Python 程序： 
SIZE = 3
used = [False] * SIZE
result = [0] * SIZE
selNums = 0

# 打印当前排列的函数
def print_arr(result):
    for i in result:
        print(i, end=" ")
    print()

# 生成排列的函数
def permute(arr):
    global selNums  # 将 selNums 声明为全局变量

    # 检查是否所有数字都已被选择
    if selNums == SIZE:
        print_arr(result)
        return

    # 遍历所有可能的选择
    for i in range(SIZE):
        # 如果当前数字已使用，或者当前数字与前一个数字相同并且前一个数字未被使用，则跳过
        if used[i] or (i > 0 and arr[i] == arr[i-1] and not used[i-1]):
            continue

        # 选择当前数字，并标记为已使用
        used[i] = True
        result[selNums] = arr[i]
        selNums += 1  # selNums 增加

        # 递归调用，继续选择下一个数字
        permute(arr)

        # 回溯：撤销选择，并将数字标记为未使用
        selNums -= 1  # selNums 减少
        used[i] = False

if __name__ == "__main__":
    array = [1, 2, 1]
    array.sort()  # 对数组进行排序
    # 调用排列函数
    permute(array)

下面是解决全排序问题的 Java 程序：
import java.util.Arrays;

public class Permutation {
    private static final int SIZE = 3;
    private boolean[] used = new boolean[SIZE];
    private int[] result = new int[SIZE];
    private int selNums = 0;

    // 打印当前排列的函数
    private void printArr() {
        for (int i = 0; i < SIZE; i++) {
            System.out.print(result[i] + " ");
        }
        System.out.println();
    }

    // 生成排列的函数
    private void permute(int[] arr) {
        // 检查是否所有数字都已被选择
        if (selNums == SIZE) {
            printArr();
            return;
        }

        // 遍历所有可能的选择
        for (int i = 0; i < SIZE; i++) {
            // 如果当前数字已使用，或者当前数字与前一个数字相同并且前一个数字未被使用，则跳过
            if (used[i] || (i != 0 && arr[i] == arr[i - 1] && !used[i - 1])) {
                continue;
            }

            // 选择当前数字，并标记为已使用
            used[i] = true;
            result[selNums++] = arr[i];

            // 递归调用，继续选择下一个数字
            permute(arr);

            // 回溯：撤销选择，并将数字标记为未使用
            used[i] = false;
            selNums--;
        }
    }

    public static void main(String[] args) {
        Permutation permutation = new Permutation();
        int[] array = { 1, 2, 1 };
       
        // 对数组进行排序
        Arrays.sort(array);

        // 调用排列函数
        permutation.permute(array);
    }
}

以上程序的执行结果均为：

1 1 2
1 2 1
2 1 1