洗牌算法

一、

1.Fisher–Yates shuffle

Fisher–Yates shuffle 的原始版本，最初描述在 1938 年的 Ronald Fisher（上图） 和 Frank Yates 写的书中，书名为《Statistical tables for biological, agricultural and medical research》。他们使用纸和笔去描述了这个算法，并使用了一个随机数表来提供随机数。

2.Knuth-Durstenfeld Shuffle

Fisher–Yates shuffle 算法的现代版本是为计算机设计的。由 Richard Durstenfeld 在1964年 描述。并且是被 Donald E. Knuth 在 《The Art of Computer Programming》 中推广。但是不管是 Durstenfeld 还是 Knuth，都没有在书的第一版中承认这个算法是 Fisher 和 Yates 的研究成果。也许他们并不知道。不过后来出版的 《The Art of Computer Programming》提到了 Fisher 和 Yates 贡献。

现代版本的描述与原始略有不同，因为如果按照原始方法，愚蠢的计算机会花很多无用的时间去计算上述第 3 步的剩余数字。这里的方法是在每次迭代时交换这个被取出的数字到原始列表的最后。这样就将时间复杂度从 O(n^2) 减小到了 O(n)。算法的伪代码如下：

-- To shuffle an array a of n elements (indices 0..n-1):
for i from n−1 downto 1 do
     j ← random integer such that 0 ≤ j ≤ i
     exchange a[j] and a[i]

3.INSIDE-OUT ALGORITHM算法

Knuth-Durstenfeld Shuffle 是一个内部打乱的算法，算法完成后原始数据被直接打乱， 尽管这个方法可以节省空间，但在有些应用中可能需要保留原始数据，所以需要另外开辟一个数组来存储生成的新序列。

Inside-Out Algorithm 算法的基本思想是从前向后扫描数据， 把位置i的数据随机插入到第i个（包括第i个）位置中（假设为k），这个操作是在新数组中进行， 然后把原始数据中位置k的数字替换新数组位置i的数字。其实效果相当于新数组中位置k和位置i的数字进行交互。

4.SATTOLO算法

Sandra Sattolo于1986年发布了一种非常相似的算法 当打算使用普通的Fisher-Yates shuffle时，很容易不经意间就实现了Sattolo算法

核心思想和Fisher–Yates shuffle算法完全一致, 区别在于:在原始数组上对数字进行交互，减小了空间复杂度 每次从未处理的数据中随机取出一个数字， 然后把该数字放在整个数组的尾部，即数组尾部存放的是已经处理过的数字, 具体步骤如下：

• 写下从 1 到 N 的数字
• 取一个从 1 到剩下的数字（包括这个数字）的随机数 k
• 从低位开始，从未处理的数据中得到第 k 个数字（这个数字还没有被取出），把它写在当前列表的最后一位
• 重复第 2 步，直到所有的数字都被取出
• 第 3 步在当前序列的基础上,改造成了一个随机排列的数列

二、golang版本洗牌

1.官方的rand.Shuffle

在1.10版本后，官方在rand包提供了Fisher-Yates的实现

// Shuffle pseudo-randomizes the order of elements.
// n is the number of elements. Shuffle panics if n < 0.
// swap swaps the elements with indexes i and j.
func (r *Rand) Shuffle(n int, swap func(i, j int)) {
    if n < 0 {
        panic("invalid argument to Shuffle")
    }

    // Fisher-Yates shuffle: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
    // Shuffle really ought not be called with n that doesn't fit in 32 bits.
    // Not only will it take a very long time, but with 2³¹! possible permutations,
    // there's no way that any PRNG can have a big enough internal state to
    // generate even a minuscule percentage of the possible permutations.
    // Nevertheless, the right API signature accepts an int n, so handle it as best we can.
    i := n - 1
    for ; i > 1<<31-1-1; i-- {
        j := int(r.Int63n(int64(i + 1)))
        swap(i, j)
    }
    for ; i > 0; i-- {
        j := int(r.int31n(int32(i + 1)))
        swap(i, j)
    }
}

举例如下：

a := []int{1, 2, 3, 4, 5, 6, 7, 8}
rand.Seed(time.Now().UnixNano())
rand.Shuffle(len(a), func(i, j int) { a[i], a[j] = a[j], a[i] })
//警告：如果不调用 rand.Seed，则每次运行程序时，您都会获得相同的伪随机数序列。

2.官方的rand.Perm

参考 go高效洗牌算法

// Perm returns, as a slice of n ints, a pseudo-random permutation of the integers [0,n).
func (r *Rand) Perm(n int) []int {
    m := make([]int, n)
    // In the following loop, the iteration when i=0 always swaps m[0] with m[0].
    // A change to remove this useless iteration is to assign 1 to i in the init
    // statement. But Perm also effects r. Making this change will affect
    // the final state of r. So this change can't be made for compatibility
    // reasons for Go 1.
    for i := 0; i < n; i++ {
        j := r.Intn(i + 1)
        m[i] = m[j]
        m[j] = i
    }
    return m
}

先构造一个有3个元素的Article切片，然后用rand.Perm(3)生成0-2的随机排序数组，然后构造一个新的Article切片，新切片按顺序用随机数组里的下标从老切片取数据，这样就完成了随机重排。

package main

import (
"fmt"
"math/rand"
)

type Articlestruct {
Titlestring
Authorstring
}

var articles =[]Article{
    {Title:"Study golang",Author:"yuanfang"},
    {Title:"Effective golang",Author:"yuanfang"},
    {Title:"Effective python",Author:"yuanfang"},
}

func main() { 
newArticles :=[3]Article{} 
l := rand.Perm(3) 
 for i:=0;i<3;i++ {  
 newArticles[i]=articles[l[i]]  
}
 fmt.Println(l)  
 fmt.Println(newArticles) }
}

3.Knuth-Durstenfeld Shuffle

参考 shuffle 洗牌算法

package shuffle

import (
   "fmt"
   "math/rand"
)

func KnuthDurstenfeldShuffle(array []int) []int {
   for i := len(array) - 1; i >= 0; i-- {
       p := RandInt64(0, int64(i))
       fmt.Printf("每次生成的随机数：%d\n", p)
       a := array[i]
       array[i] = array[p]
       array[p] = a
       fmt.Println("置换后的数组为：", array)
   }
   return array
}

// RandInt64 区间随机数
func RandInt64(min, max int64) int64 {
   if min >= max || max == 0 {
       return max
   }
   return rand.Int63n(max-min) + min
}



package shuffle

import (
   "fmt"
   "testing"
)

func TestKnuthDurstenfeldShuffle(t *testing.T) {
   array := []int{1, 2, 3, 4, 5}
   shuffle := KnuthDurstenfeldShuffle(array)
   fmt.Println(shuffle)
}