怎么生成m个1-n的不重复的随机序列

如何生成m个1-n的不重复的随机序列
比如数字1-50，生成100个有50个数字组成的随机序列，要求不能不能有重复。
就是遗传算法的旅行商问题产生初始城市序列号的问题，

------解决方案--------------------
50个数的全排列有50!=3.0414093201713378043612608166065e+64多种情况，楼主要随机抽取其中不重复的100种情况，我觉得可以把100种情况分散开。
取50个数的一种排列，分步来做：第1次取数有50种情况，第2次取还剩下49种，第3次48种……最后一次只有1种。那么，将第1次抽取的50种情况分开，然后第2次取分别将0~25和26~50分开，后面的数完全随机，这样抽取的100个排列就即不会重复，分布也比较均匀。
代码如下：

C/C++ code


#include <ctime>
#include <cstdlib>
#include <iostream>
#include <algorithm>

using namespace std;
int main()
{
    int iDat[50], i, j, t;

    srand ((unsigned)time(NULL));    // 初始化随机数种子

    for (i=1; i<=25; i++)        // 先计算第1次取值在1~25范围的50种情况
    {
        iDat[0] = i;        // 确定第1个数
        t = rand()%24 + 1;    // 随机抽取一个1~24范围的数
        // 让第2个数在1~25范围中排除第1个已抽取的数
        iDat[1] = (t>=i? t+1: t);
        t = 2;            // 下标从2开始
        // 循环将其余48个数补满，1~50范围排除前面已选2数
        for (j=1; j<=50; j++)
            if (j!=iDat[0] && j!=iDat[1])
                iDat[t++] = j;
        random_shuffle(iDat+2, iDat+50);  // STL算法，随机排列

        // 输出前25个结果
        copy(iDat, iDat+25, ostream_iterator<int>(cout, " "));
        cout << endl;
        // 输出后25个结果
        copy(iDat+25, iDat+50, ostream_iterator<int>(cout, " "));
        cout << endl << endl;
        
        // 意思大致同上，唯一第2个数的取值范围不一样是26~50
        iDat[1] = rand()%25 + 26;    
        t = 2;
        for (j=1; j<=50; j++)
            if (j!=iDat[0] && j!=iDat[1])
                iDat[t++] = j;
        random_shuffle(iDat+2, iDat+50);
        copy(iDat, iDat+25, ostream_iterator<int>(cout, " "));
        cout << endl;
        copy(iDat+25, iDat+50, ostream_iterator<int>(cout, " "));
        cout << endl << endl;
    }

    // 第1次取值在26~50范围的50种情况
    for (i=26; i<=50; i++)
    {
        iDat[0] = i;
        iDat[1] = rand()%25 + 1;
        t = 2;
        for (j=1; j<=50; j++)
            if (j!=iDat[0] && j!=iDat[1])
                iDat[t++] = j;
        random_shuffle(iDat+2, iDat+50);
        copy(iDat, iDat+25, ostream_iterator<int>(cout, " "));
        cout << endl;
        copy(iDat+25, iDat+50, ostream_iterator<int>(cout, " "));
        cout << endl << endl;

        t = rand()%24 + 26;
        iDat[1] = (t>=i? t+1: t);
        t = 2;
        for (j=1; j<=50; j++)
            if (j!=iDat[0] && j!=iDat[1])
                iDat[t++] = j;
        random_shuffle(iDat+2, iDat+50);
        copy(iDat, iDat+25, ostream_iterator<int>(cout, " "));
        cout << endl;
        copy(iDat+25, iDat+50, ostream_iterator<int>(cout, " "));
        cout << endl << endl;
    }

    return 0;
}

------解决方案--------------------
ytfhwfnh给出的想法确实不错。

但我觉得还是有一点值得讨论的情况，即关两个数是“刻意的均匀”，而“刻意”就意味着不“随机”。因为如果是真正的随机，那么产生第一个数完全相同的100组序列也是可能的。而在ytfhwfnh把给出的算法中，产生第一个数完全相同的100组序列已定注定成为“不可能”。既然有此情况成为“不可能”那就不能算是随机的了。
当然，要完全随机，要么需要一些折衷的办法，要么代价就太高了。

所以，我在想，遗传算法中所需的起始基因组，难道真的就必须“100组绝对两两不重复”么？以非常非常小概率允许一定程度的重复就有问题么？

怎么生成m个1-n的不重复的随机序列

相关推荐