受堆栈溢出问题的启发,我决定通过研究Google Code Jam的最小标量积问题来练习Haskell:


给定两个向量\ $ \ mathbf {v_1} = (x_1,x_2,\ ldots,x_n)\ $和\ $ \ mathbf {v_2} =(y_1,y_2,\ ldots,y_n)\ $。如果可以置换每个矢量的坐标,则最小标量积\ $ \ mathbf {v_1} \ cdot \ mathbf {v_2} \ $?

约束:
\ $ 100 \ le n \ le 800 \ $
\ $-100000 \ le x_i,y_i \ le 100000 \ $


我并没有要求任何算法上的出色(这只是一个参考实现,以便稍后检查正确性。 m使用正确的工具进行作业。

module MinimumScalarProduct where

import Control.Monad (replicateM, forM_, (>=>))
import Control.Monad.ST (runST, ST)
import Data.Vector (thaw, fromList, MVector, Vector, zipWith, foldl', length, (!))
import Data.Vector.Generic.Mutable (read, swap)
import Prelude hiding (read, zipWith, length)

-- sequnce of transpoitions to yield all permutations of n elts
-- http://en.wikipedia.org/wiki/Steinhaus-Johnson-Trotter_algorithm
transpositions :: Int -> [(Int, Int)]
transpositions n = runST $ do
          -- p maps index to element
          p <- thaw $ fromList [0 .. n-1]
          -- q maps element to index
          q <- thaw $ fromList [0 .. n-1]
          -- let the prefixes define themselves recursively
          foldr ((>=>) . extend p q) return [2..n] [] 

extend :: MVector s Int -> MVector s Int -> Int -> [(Int,Int)] -> ST s [(Int,Int)]
extend p q n ts = fmap ((ts++) . concat) . replicateM (n-1) $ do
  -- replace the element in the (n-1)'th position with its predecessor
  a <- read p (n-1)
  i <- read q (a-1)
  swap p (n-1) i
  swap q a (a-1)
  -- replay the earlier transpositions
  forM_ ts $ \(m,j) -> do
    b <- read p m
    c <- read p j
    swap p m j
    swap q b c
  return $ (n-1,i) : ts

-- reference implementation, takes O(n!)
msp :: Vector Int -> Vector Int -> Int
msp u v | length u /= length v = 0
msp u v = runST $ do
  let x = foldl' (+) 0 $ zipWith (*) u v
  let n = length u
  u' <- thaw u
  -- check each permutation of u'
  let steps = map (adjust u' v) $ transpositions n
  fmap minimum . sequence $ scanl (>>=) (return x) steps

-- adjust the current scalar product for the transposition of u
adjust :: MVector s Int -> Vector Int -> (Int, Int) -> Int -> ST s Int
adjust u v (i,j) x = do
  a <- read u i
  b <- read u j
  let c = v ! i
  let d = v ! j
  swap u i j
  return $ x - (a*c + b*d) + (a*d + b*c)


评论

您知道仅通过对向量排序即可解决此问题吗?为什么当它只是参考实现时,为什么要以这种复杂的方式进行操作,Data.List.permutations有什么问题?
Hjulle:已经三年了,但是我想我试图通过以换位顺序遍历所有排列来最小化为所有排列计算乘积的工作。因此,每个向量乘积的工作量为O(1),而不是O(n),因此总算法为O(n!),而不是O(n * n!)。回想起来,也许节省不了多少。

@Hjulle对于这样的公开挑战,我建议您更新您的评论,不要透露解决方案,因为它破坏了其他人以及OP的挑战。最好回顾一下OP所表达的想法的代码,也许只是提到“注意,有一种渐近有效的算法”之类的东西,并给OP(和其他人)一个找到它的机会。靠自己。

#1 楼

有点老的问题,但仍然很可惜,它还没有被回答:)。抛开注释中建议的渐近更好的解决方案,只关注代码:

加号:所有函数的顶级类型以及注释。该代码对Haskell的各种函数和惯用法有很好的理解。通常,更复杂的代码应更冗长且更具描述性。在视觉上,大多数代码只是简单的读/写/交换ST操作,但重要的部分被压缩为不太容易理解和不常见的折叠/扫描/序列组合等。我可能会将简单的部分(读/交换)分离为辅助函数,并稍微扩展/简化了复杂的部分。当它改变其第一个参数时,它将保持标量积纯净,并将其作为参数传入和传出。这有些令人困惑,并使最小值的计算(adjustscanl)复杂化。如果乘积也为ST变量,则代码将变得更简单(未经测试):
还可以将>>=foldr替换为>=>(未经测试): foldM。)

一些问题:


是否有必要重播extend中的所有flip?由于它反复执行,因此有必要分别或一次计算ts的组合排列,然后直接应用即可。
实际使用哪种算法?使用两个向量似乎与链接的Wikipedia文章中的任何内容都不匹配。虽然该算法的基本概念很明确,但对于不熟悉该算法的人来说,获得更精确的准则会更容易。使用extendts。在此没有可见的顺序。一个不错的选择是,函数总是在使用前定义的(相互递归函数明显除外)。或反之亦然-主要/导出功能是第一位,而辅助功能是第二位。或者,将功能分成(可能是嵌套的)部分,那么功能的顺序并不重要,各部分的顺序变得很重要。