洗牌算法

淡淡的烟草味﹌ 2023-12-13 06:18 76阅读 0赞

一、什么是洗牌算法

Fisher–Yates shuffle **洗牌算法** 简单来说Fisher–Yates shuffle **算法是**一个用来将一个有限集合生成一个随机排列的**算法**（数组随机排序）。 这个**算法**生成的随机排列**是**等概率的。

二、实例

要求：给定一个长度为n的有序数组，要求将其完全打乱，每个元素在任何位置出现的概率均为1/n。

随机洗牌算法有好几个，这里讲其中的一个，Fisher-Yates shuffle算法（时间复杂度为O(n)），其思路如下：

（1）从数组中随机选取一个数p。

（2）将p与数组中最后（也可以是最前）的元素交换。（如果随机选中的是最后的元素，则相当于没有发生交换）

（3）去掉最后的元素（这里并没有删除操作，而是缩小索引值范围），即选中的p，缩小选取的数组范围。

（4）重复步骤（1）~（3），直到数组的长度为1时结束。

三、STL algorithm算法shuffle , random\_shuffle

shuffle原型：

template <class RandomAccessIterator, class URNG>  
void shuffle (RandomAccessIterator first, RandomAccessIterator last, URNG&& g);  
该函数是用来打乱范围内元素的顺序的。  
其行为类似：

template <class RandomAccessIterator, class URNG>
      void shuffle (RandomAccessIterator first, RandomAccessIterator last, URNG&& g)
    {
      for (auto i=(last-first)-1; i>0; --i) {
        std::uniform_int_distribution<decltype(i)> d(0,i);
        swap (first[i], first[d(g)]);
      }
    }

// shuffle algorithm example
    #include <iostream>     // std::cout
    #include <algorithm>    // std::shuffle
    #include <array>        // std::array
    #include <random>       // std::default_random_engine
    #include <chrono>       // std::chrono::system_clock
     
    int main () {
      std::array<int,9> foo {1,2,3,4,5,6,7,8,9};
     
      // obtain a time-based seed:
      unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
     
      shuffle (foo.begin(), foo.end(), std::default_random_engine(seed));
     
      std::cout << "shuffled elements:";
      for (int& x: foo) std::cout << ' ' << x;
      std::cout << '\n';
     
      return 0;
    }