C语言中实现随机排列 (randperm 函数) 的多种方法106

在C语言中，并没有直接提供像MATLAB中的randperm函数那样，可以方便地生成一个随机排列的整数序列的内置函数。然而，我们可以通过多种方法来实现类似的功能。本文将介绍几种常见的实现方法，并分析其优缺点，帮助读者根据实际需求选择最合适的方案。

所谓的随机排列，指的是将一个给定的整数序列随机打乱顺序。例如，对于序列{1, 2, 3, 4, 5}，一个可能的随机排列是{3, 1, 5, 2, 4}。实现随机排列的关键在于使用随机数生成器和合适的算法来避免重复和保证每个元素都有相同的概率出现在任何位置。

方法一：使用Fisher-Yates洗牌算法

Fisher-Yates洗牌算法（也称为Knuth洗牌算法）是一种高效且广泛使用的随机排列算法。其核心思想是从序列的末尾开始，逐步地将每个元素与序列中前面某个随机位置的元素交换。这种方法能够保证每个排列出现的概率相等。#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void randperm(int arr[], int n) {
srand(time(NULL)); // 初始化随机数种子
for (int i = n - 1; i > 0; i--) {
int j = rand() % (i + 1); // 生成0到i之间的随机数
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int main() {
int arr[] = {1, 2, 3, 4, 5};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("");
randperm(arr, n);
printf("Shuffled array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("");
return 0;
}

这段代码首先初始化随机数种子，这非常重要，因为它确保每次运行程序时都能得到不同的随机排列。然后，算法从最后一个元素开始迭代，每次随机选择一个之前的元素进行交换。 `rand() % (i + 1)` 保证了随机选择的索引在当前元素之前。

方法二：使用数组和随机索引

另一种方法是创建一个新的数组来存储随机排列的结果。我们首先创建一个与原数组大小相同的数组，然后随机选择原数组的索引，并将对应的元素复制到新数组中，同时标记已选择的索引以避免重复。#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>
void randperm2(int arr[], int n, int result[]) {
srand(time(NULL));
bool used[n];
for (int i = 0; i < n; i++) used[i] = false;
for (int i = 0; i < n; i++) {
int j;
do {
j = rand() % n;
} while (used[j]);
result[i] = arr[j];
used[j] = true;
}
}
int main() {
int arr[] = {1, 2, 3, 4, 5};
int n = sizeof(arr) / sizeof(arr[0]);
int result[n];
randperm2(arr, n, result);
printf("Shuffled array: ");
for (int i = 0; i < n; i++) {
printf("%d ", result[i]);
}
printf("");
return 0;
}