数据结构与算法解析习题2.7：前N个自然数的一个随机置换
问题描述：假设需要生成前N个自然数的一个随机置换。例如，{4,3,1,5,2} 和 {3,1,4,2,5} 就是合法的置换，但 {5,4,1,2,1} 却不是，因为数1出现了两次而数 3 缺没有。这个程序常常用于模拟一些算法。我们假设存在一个随机数生成器 randInt(i, j) ，它以相同的概率生成 i 和 j 之间的一个整数。
#include <stdio.h>
#include <stdlib.h>
void swap (int *a, int *b) {
int t;
t = *a;
*a = *b;
*b = t;
}
int RandInt(int i, int j) {
if (i == 0) {
return rand() % (j + 1);
} else {
return rand() % (j + 1 - i) + i;
}
}
// 1.如下填入 A[0] 到 A[N-1] 的数组 A；为了填入 A[i] ，生成随机数直到它不同于已经生成的 A[0], A[1], ... , A[i-1] 时，再将其填入 A[i] 。
void fun1(int a[], int n) {
int tmp;
int i = 0;
int j;
while (i < n) {
tmp = RandInt(0, n-1);
for ( j = 0; j < i; j++) {
if (tmp == a[j]) {
break;
}
}
if (j == i) {
a[i] = tmp;
i++;
}
}
}
// 2.同算法1，但是要保存一个附加的数组，称之为 Used（用过的）数组。
// 当一个随机数 Ran 最初被放入数组A的时候，置Used[Ran]=1。
// 这就是说，当用一个随机数填入 A[i] 时，可以用一步来测试是否该随机数已经被使用，而不是像第一个算法那样（可能）进行 i 步测试。
void fun2 (int a[], int n) {
int tmp;
int used[n];
for (int i = 0; i < n; i++) {
used[i] = 0;
}
int i = 0;
while (i < n) {
tmp = RandInt(0, n-1);
if (used[tmp] == 0) {
a[i] = tmp;
used[tmp] = 1;
i++;
}
}
}
// 3.填写该数组使得 A[i] = i + 1。然后
// for(i = 1; i < N; i++)
// swap(&A[i], &A[randInt(0, i)]);
void fun3 (int a[], int n) {
int i;
for (i = 0; i < n; i++) {
a[i] = i;
}
for (i = 0; i < n; i++) {
swap(&a[i], &a[RandInt(0, i)]);
for (int i = 0; i < n; i++) {
printf("%d ", a[i]);
}
printf("\n \n");
}
}
int main() {
int a[5];
fun3(a, 5);
for (int i = 0; i < 5; i++) {
printf("%d \n", a[i]);
}
}