全排列问题（非常详细，附带源码）
全排列问题是非常经典的算法问题，它要求罗列出指定集合中全部元素所有可能的排列情况。
例如，集合 {1, 2, 3} 的全排列包括：
集合中也可能存在相同的元素，例如集合 {1, 1, 2} 的全排列包括：
无论集合中是否含有重复的元素，全排列问题都可以用回溯算法解决，接下来给大家做详细地讲解。
回溯算法查找 {1, 2, 3} 全排列的过程是：
下面是采用回溯算法查找 {1, 2, 3} 全排列的 C 语言程序：
运行程序，执行结果为：
注意，此程序只适用于无重复元素的集合。如果将 main() 函数里的 array[] 数组改成：
以 {1, 1, 2} 为例，观察前面的程序查找全排序的过程：
过滤掉飘红的过程，给大家分享一种方法：首先把集合中的元素排好序（升序或者降序），然后开始查找全排序。对于尚未被选中的元素，如果它和前一个元素相等，并且前一个元素处于未选中状态，就跳过这次查找过程。
下面是按照此方法在 {1, 1, 2} 中查找全排序的过程：
下面是修改后的 C 语言程序，它既能满足在无重复元素的集合中查找全排序，也能满足在有重复元素的集合中查找全排序：
下面是解决全排序问题的 Python 程序：
下面是解决全排序问题的 Java 程序：
以上程序的执行结果均为：
例如，集合 {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} 为例，观察前面的程序查找全排序的过程：
从 {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
ICP备案：
公安联网备案：