一种生成不重复数的算法-阿里云开发者社区

一种生成不重复数的算法

2017-11-15 1091

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介：

在编程中经常遇到一些类似的问题，比如做一个双色球选号软件，其中6个双色球是从1到33之间选出6个数来，这6个数是不能重复的，这个问题就是我们今天要说的生成不重复数算法。
算法描述如下：从M个数中选出N个数来(0<N<=M)，要求N个数之间不能有重复。
这个问题我以前用J2SE实现过，使用了ArrayList，每次随机在指定范围内选定一个数，然后查看结果集合中是否存在该数，如果存在继续下一轮循环，如果不存在，就将该数保存到结果集合中去。使用这种算法虽然也能实现要求，缺点是判断结果集合中是否存在该数时，需要通过一个循环来判断，这会增加算法运行的时间，虽然时间复杂度为n，但多次重复，还是一笔不小的开销。

下面要介绍的算法是，每次随机取出一个数，之后将该数放置到集合的末尾去，这样下次取随机数的时候，只从1到目标集合个数-1个中随机抽取，如此循环，这样就避免了判断在结果集合中判断是否存在相冲突的数的过程。

算法代码如下：

using System;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;
using System.Management;

namespace ConsoleApplication
{
     class Program
    {
         static void Main( string [] args)
        {
             int [] range = new int [ 33 ];
             for ( int i = 0 ; i < 33 ; i ++ ) // 初始化范围集合，从1到33
            {
                range[i] = i + 1 ;
            }
             int [] result = CreateNumbers(range, 6 );
             for ( int i = 0 ;i < result.Length;i ++ )
            {
                Console.WriteLine( " result[{0}]={1} " , i, result[i]);
            }
            Console.ReadKey();
        }

         // 取出不重复的6个数
     static int [] CreateNumbers( int [] range, int count)
        {
             int [] result = new int [count];
            Random random = new Random();
             int index = 0 ;
             int temp = 0 ;
             for ( int i = 0 ; i < count; i ++ )
            {
                index = random.Next() % (range.Length - i);
                result[i] = range[index];
                 // 将当前已使用过的数移至集合末尾，并且将末尾原来没有使用的数放到当前位置
                temp = range[range.Length - 1 - i];
                range[range.Length - 1 - i] = range[index];
                range[index] = temp;
            }
             return result;
        }

    }
}

结果如下：

补充一下，另外一种不使用数组而使用可变集合的办法，这种算法的做法是使用了之后马上从源集合中清除掉（数组是

没有办法这么做的），因而也是可以做到生成不重复的随机数的。具体代码如下：

// 取出不重复的6个数
         static List < int > CreateNumbers(List < int > range, int count)
        {
            List < int > result = new List < int > (count);
            Random random = new Random();
             int index = 0 ;
             for ( int i = 0 ; i < count; i ++ )
            {
                index = random.Next() % range.Count;
                result.Add(range[index]);
                range.RemoveAt(index);
            }
             return result;
        }

至于用法，也很简单：

List < int > range = new List < int > ( 33 );
             for ( int i = 0 ; i < 33 ; i ++ ) // 初始化范围集合，从1到33
            {
                range.Add(i + 1 );
            }
            List < int > result = CreateNumbers(range, 6 );
             for ( int i = 0 ; i < result.Count; i ++ )
            {
                Console.WriteLine( " result[{0}]={1} " , i, result[i]);
            }

经万次测试，使用数组方法性能比使用List<int>范型集合高1/4。