有序数组变乱序

需求：将一个长度为n的有序数组变为一个随机乱序数组

（答案在文末）

 

方法一：

//伪代码    
for (int i = 0;i < n; ++i)
{
    srand((unsigned)time(NULL));
    swap(arr[i],arr[rand()%n]);
}

问题：

1、产生了n^2方种情况，显然不是排列组合中n!的整数倍，所以这种乱序方法是有问题的

如果不理解，我们下面进行实践

    srand((unsigned)time(NULL));
    vector<int> arr = {4,10,3,5,7,1,6,9,2,8};
//    vector<int> arr = {1,2,3};
    long result[10][10] = {0};
    for (int q=0;q<THOUSAND*THOUSAND;++q)
    {
        for (int i=0;i<arr.size();++i)
        {
            swap(arr[i],arr[rand()%arr.size()]);
        }
        for (int i = 0;i<arr.size();++i)
        {
            for (int j = 0; j<arr.size(); ++j)
            {
                if (arr[i] == j+1)
                {
                    ++result[i][j];
                    break;
                }
            }
        }

    }
    cout<<" p | ";
    for (int i = 0;i<arr.size();++i)
    {
        cout<<setw(6)<<i+1<<" | ";
    }
    cout<<endl;
    for (int i = 0;i<arr.size();++i)
    {
        cout <<setw(2)<< i+1<<" | ";
        for (int j = 0; j<arr.size(); ++j)
        {
            cout<<setw(8)<<result[i][j]*1.0/(THOUSAND*THOUSAND) << " ";
        }
        cout<<endl;
    }
    return 0;

 

显然概率是有规律的

如果觉得不明显，可以打印长度为3的数组

 

方法二：

因为排列组合有n!种情况，所以产生一个随机数rand()%(n的阶乘)，根据产生的随机数确定排列组合

 

问题：

1、如果n很大，n!必然更大，产生的随机数可能没那么大

2、根据随机数确定排列组合是一个时间复杂度为O(n^2),且涉及到n!的不优雅的算法

 

方法三：

遍历n次，每次选择随机两个或一个数交换。

int main()
{
    long long num=0;
    srand((unsigned)time(NULL));
    vector<int> arr = {4,10,3,5,7,7,6,4,2,8};
    for (int q=0;q<THOUSAND*THOUSAND;++q)
    {
        sortByBubbing1_0(arr);//排序
        for (int i=0;i<arr.size();++i)
        {
            swap(arr[rand()%arr.size()],arr[rand()%arr.size()]);
        }
        if (arr[0]==2) ++num;

    }
    cout<<num*1.0/(THOUSAND*THOUSAND)<<endl;
    return 0;
}

 

产生n^3种情况，错误和方法一类似，输出结果大概为0.2，显然是不对的

 

方法四：

与第二种方法思路类似，但用的是链表实现，且有n个随机数

int main()
{
    long long num=0;
    vector<int> arr = {4,10,3,5,7,1,6,9,2,8};
    long result[10][10] = {0};
    srand((unsigned)time(NULL));  
    for (int q=0;q<THOUSAND*THOUSAND;++q)
    {   
        list<int>::iterator iter;
        list<int> dataListCopy;
        list<int> dataList = {0,1,2,3,4,5,6,7,8,9};
        // 进行乱序
        for (int i=dataList.size();i>0;--i)
        {
            int n = rand()%i;
            int j = 0;
            for (iter = dataList.begin(); iter != dataList.end(); ++iter)
            {
                if (j==n)
                {
                    dataListCopy.push_back(*iter);
                    dataList.erase(iter);
                    break;
                }
                ++j;
            }
        }
        // 统计结果
        int k = 0;
        for (iter = dataListCopy.begin(); iter != dataListCopy.end(); ++iter)
        {
            for (int j = 0; j<arr.size(); ++j)
            {
                if (*iter == j)
                {
                    ++result[k][j];
                    break;
                }
            }
            ++k;
        }
    }
    // 输出结果
    cout<<" p | ";
    for (int i = 0;i<arr.size();++i)
    {
        cout<<setw(6)<<i+1<<" | ";
    }
    cout<<endl;
    for (int i = 0;i<arr.size();++i)
    {
        cout <<setw(2)<< i+1<<" | ";
        for (int j = 0; j<arr.size(); ++j)
        {
            cout<<setw(8)<<result[i][j]*1.0/(THOUSAND*THOUSAND) << " ";
        }
        cout<<endl;
    }
    return 0;
}

 

方法五：

通过思考方法一与方法四，我们发现只要小小的修改一下方法一就能达到方法四的目的（后来我才了解到这是knuth洗牌算法）

// 将数组的头部看成是长度为i+1的原链表，将数组的尾部看成是长度为n-i-1的一个链表，
// 每次从头部中随机选一个元素插入到尾部链表的头部，
for (int i=arr.size()-1; i > 0 ;--i)
{
    swap(arr[i],arr[rand()%(i+1)]);
}

 

答案虽然重要，但更重要的是思考的过程，它能让我们成长。

 

 

 

点击关注，持续推送质量好文；如有不当，欢迎指出；转载请注明出处。