gpt4 book ai didi

algorithm - 纯 Knuth/Fisher-Yates 在 haskell 中洗牌

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:29:08 25 4
gpt4 key购买 nike

在 go 中,我可以编写这样的函数:

func pureFisherYates(s []int, swaps []int) []int {
newS := copy(s)
for i, _ := range newS {
for _, j := range swaps {
newS[i], newS[j] = newS[j], newS[i]
}
}
}

对我来说,这似乎是一个纯函数。它总是在给定相同输入的情况下返回相同的输出,并且它不会改变世界的状态(除了在某种严格意义上与任何其他功能相同的方式,占用 cpu 资源,产生热能等)。然而,每当我寻找如何进行纯洗牌时,我都会找到像 this 这样的东西。 ,每当我寻找具体的 Haskell 实现 Fisher-Yates 时,我要么得到一个 0^2 用列表实现的 Fisher-Yates,要么得到一个 [a] -> IO [a] 实现。是否存在 [a] -> [a] O(n) shuffle,如果不存在,为什么我上面的 go 实现不纯。

最佳答案

ST monad 允许这种封装的可变性,并且 Data.Array.ST包含可以在 ST 中改变的数组,然后在外部返回一个不可变的版本。

https://wiki.haskell.org/Random_shuffle使用 ST 给出了 Fisher-Yates shuffle 的两种实现。它们不是字面上的 [a] -> [a],但那是因为还需要处理随机数生成:

import System.Random
import Data.Array.ST
import Control.Monad
import Control.Monad.ST
import Data.STRef

-- | Randomly shuffle a list without the IO Monad
-- /O(N)/
shuffle' :: [a] -> StdGen -> ([a],StdGen)
shuffle' xs gen = runST (do
g <- newSTRef gen
let randomRST lohi = do
(a,s') <- liftM (randomR lohi) (readSTRef g)
writeSTRef g s'
return a
ar <- newArray n xs
xs' <- forM [1..n] $ \i -> do
j <- randomRST (i,n)
vi <- readArray ar i
vj <- readArray ar j
writeArray ar j vi
return vj
gen' <- readSTRef g
return (xs',gen'))
where
n = length xs
newArray :: Int -> [a] -> ST s (STArray s Int a)
newArray n xs = newListArray (1,n) xs

import Control.Monad
import Control.Monad.ST
import Control.Monad.Random
import System.Random
import Data.Array.ST
import GHC.Arr

shuffle :: RandomGen g => [a] -> Rand g [a]
shuffle xs = do
let l = length xs
rands <- forM [0..(l-2)] $ \i -> getRandomR (i, l-1)
let ar = runSTArray $ do
ar <- thawSTArray $ listArray (0, l-1) xs
forM_ (zip [0..] rands) $ \(i, j) -> do
vi <- readSTArray ar i
vj <- readSTArray ar j
writeSTArray ar j vi
writeSTArray ar i vj
return ar
return (elems ar)

*Main> evalRandIO (shuffle [1..10])
[6,5,1,7,10,4,9,2,8,3]

编辑:在您的 Go 代码中使用固定的 swaps 参数,代码非常简单

{-# LANGUAGE ScopedTypeVariables #-}

import Data.Array.ST
import Data.Foldable
import Control.Monad.ST

shuffle :: forall a. [a] -> [Int] -> [a]
shuffle xs swaps = runST $ do
let n = length xs
ar <- newListArray (1,n) xs :: ST s (STArray s Int a)
for_ [1..n] $ \i ->
for_ swaps $ \j -> do
vi <- readArray ar i
vj <- readArray ar j
writeArray ar j vi
writeArray ar i vj
getElems ar

但我不确定您是否可以合理地将其称为 Fisher-Yates 洗牌。

关于algorithm - 纯 Knuth/Fisher-Yates 在 haskell 中洗牌,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56660901/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com