VC知识库BLOG-袋鼠的窝-【原创】随机生成一组[1...n]的排列，类似抽签问题的一个解决方法。

【问题】
    随机生成一组[1...n]的排列，类似抽签问题。

【方法1】   
   1、生成一个随机数据iRand=(rand()%n )+1，用iRand与比较a[0] ..a[m-1]比较，均不相同，则{ a[m]=iRand;m++;}
   2、重复步骤1，直到m==n

 【点评】
     这种计算方法无疑是非常费时且低效的。由于产生随机数本身就很难保证产生1...n数据的时间
     再加上产生一个数据还要进行比较，效率就可想而知。

  【改进】  
     试着不用随机数不与a[0]...a[m-1]进行比较，将产生的随机数用一个n长度的数组bool state[0..n-1]保存，每产生一个随机数
     比较state[iRand]是否已经使用(0或1) ,

     if (!state[iRand－1])
       {
         a[m]=iRand;
         m++;
         state[iRand-1]=1;
      }     
  【点评】 
      该方法可以缩小比较时间，时间复杂度大大降低，但与上面方法一样，无法保证生成随机数据1...n数据的时间。
          
【方法2】  
    方法1中，我们均没有对随机数据处理，我们看一个生活中的例子吧。我们看看福彩摇奖吧，每摇出一个数子，该数字肯定不会再放入摇池中，
    即假如要摇出n个数字，只需要摇取n次而已。
   
    由此我们如下处理：
      采用随机数据移动数组下标，每生成一个随机数据后，将随机数据的范围缩小1。 一起来看代码来吧（代码是最好的注解）。
      

#include "stdafx.h"
      #include <stdlib.h>
      #include <stdio.h>
      #include <time.h>
      #include <memory.h>
      
      #define MAX_NUM   8
      
      int main(int argc, char* argv[])
      {
      int a[MAX_NUM]; 
      int nVal,iRand,m,nPos;      
      for(int i=0;i<MAX_NUM;i++)  // 初值1n
         a[i]=i+1;       
      m=MAX_NUM;  // 未生成的数据个数 
      nPos=0;    // 数据位置
      srand( (unsigned)time( NULL ) );  
      do
      { 
        iRand=rand()%m ;        
        
        //交换位置：每次生成的数据都前置换位，保证第nPos+1次生成的数据放置在a[nPos]               
         nVal=a[nPos];
         a[nPos]=a[iRand+nPos];   //iRand+nPos 为数据的实际位置,由于iRand会缩小范围.    
         a[iRand+nPos]=nVal;
         m--;
         nPos++;
      }while (m);
     
      printf("*** [1.%d]的随机排列*** ",MAX_NUM) ;
      for(m=0;m<MAX_NUM;m++)
       {
         printf("%-3d ",a[m]);
       }  
      printf(" ****END***** ");
      
      return 1;
  } 

      
 【点评】   
       该方法利用移动数组下标、缩小随机范围、交换数据位置来减少时间复杂度。
   
【说明】   
    本代码在vc6+win2000运行通过，你可一随意使用上述代码，但如转载文章，请加上出处。
 
 【鸣谢】   
    感谢vckbase上的wgf提供位置交换的思想，以前我用整体前移的方法，效率很低。 
--------------------next---------------------