数据结构与算法解析习题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]);
   }
}