最佳的随机集合算法？

最佳的随机集合算法？

---

# 背景说明

 随机初始化集合元素。即经过某一随机算法初始化之后，集合元素顺序被打乱，呈现一种新的随机排列状态。

# 算法描述

1. 适用于元素个数大于1的集合 set[1 ... n] （n > 1） ，并初始化随机范围为集合元素个数size。

2. 从集合中随机一个元素与最后的元素交换，swap(set[rand_i], set[size])，rand_i = rand() % size + 1。

3. 缩小集合的随机范围，size = size - 1。

4. 继续步骤2、3，直至随机范围size缩小至1，则随机集合操作完毕。

相比STL随机初始化函数的实现，详见后续random_shuffle说明，这样做的好处为：

     保证每个元素被初始化的次数不超过1，即以上算法随机选出的各元素均不同，各元素被随机次数为1，而STL算法可能超过1次。

两者相同点，即随机次数均为n-1，n为元素个数。

# 示例代码说明

/// 随机派发集合元素
template <typename T>
void RandAssignElement(vector<T>& vecAll, vector<T>& vecRes)
{
    if (vecAll.size() > 1)
    {
        vecRes.assign(vecAll.begin(), vecAll.end());
        for (size_t i = vecRes.size(); i > 1; --i)
        {
            unsigned rand_i = rand() % i;
            std::swap(vecRes[rand_i], vecRes[i-1]);
        }
    }

}
/// 应用于扑克随机发牌情况！
static void TestPokerLicensing()
{
    vector<unsigned> vecAll(54);
    for (size_t i = 0; i < vecAll.size(); ++i)
        vecAll[i] = (i + 1);
    vector<unsigned> vecRes;
    RandAssignElement(vecAll, vecRes);

    printf ("print vecRes:\n");
    for (size_t i = 0; i < vecRes.size(); ++i)
        printf(" %u", vecRes[i]);
    printf ("\n");
}

参见：https://github.com/huangjunkun/practice-for-programming/blob/master/test2/unit2.h

/// 随机派发集合元素

template <typename T>

void RandAssignElement(vector<T>& vecAll, vector<T>& vecRes)

/// 扑克发牌

static void TestPokerLicensing()

# 附STL随机算法

 STL算法random_shuffle（随机初始化集合）的实现。

     1. MS-STL版本（较复杂）

// TEMPLATE FUNCTION random_shuffle

template<class _RanIt, class _Diff>

inline void _Random_shuffle(_RanIt _First, _RanIt _Last, _Diff *)

{     // shuffle [_First, _Last)

const int _RANDOM_BITS = 15;     // minimum random bits from rand()

const int _RANDOM_MAX = (1U << _RANDOM_BITS) - 1;

_RanIt _Next = _First;

for (unsigned long _Index = 2; ++_Next != _Last; ++_Index)

     {     // assume unsigned long big enough for _Diff count

     unsigned long _Rm = _RANDOM_MAX;

     unsigned long _Rn = ::rand() & _RANDOM_MAX;

     for (; _Rm < _Index && _Rm != ~0UL;

          _Rm = _Rm << _RANDOM_BITS | _RANDOM_MAX)

          _Rn = _Rn << _RANDOM_BITS | _RANDOM_MAX;     // build random value

     std::iter_swap(_Next, _First + _Diff(_Rn % _Index));     // swap a pair

     }

}

template<class _RanIt>

inline void random_shuffle(_RanIt _First, _RanIt _Last)

{     // shuffle [_First, _Last)

if (_First != _Last)

     _Random_shuffle(_First, _Last, _Dist_type(_First));

}

     2. SGI-STL版本（较简单）

// Return a random number in the range [0, __n).  This function encapsulates

// whether we're using rand (part of the standard C library) or lrand48

// (not standard, but a much better choice whenever it's available).

template <class _Distance>

inline _Distance __random_number(_Distance __n) {

#ifdef __STL_NO_DRAND48

  return rand() % __n;

#else

  return lrand48() % __n;

#endif

}

// random_shuffle

template <class _RandomAccessIter>

inline void random_shuffle(_RandomAccessIter __first,

                           _RandomAccessIter __last) {

  __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator);

  if (__first == __last) return;

  for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)

    iter_swap(__i, __first + __random_number((__i - __first) + 1));

}

     3. 其他STL版本random_shuffle

      …… （略过）