筆記與流年

這兩天忙中偷閑做了《計算機程序設計藝術》的第4卷第2分冊的最初的幾個習題，都是關于算法M的，結在一起做一筆記。

算法M其實就是按照字典順序生成出所有的元組。一般的理解，都是生成一個集合的n元組，或者(0,…,m-1)這m個取值的n元組。算法M對我們一般的理解做了擴展，它限定了元組每一位上的最大值，也即給出限制列表bnds:(m_1,m_2,…,m_n)，在第k位上取值可以從0到m_k-1這樣m_k種可能。用Haskell算法M實現如下：

genTuplesM :: [Int] -> [[Int]]
genTuplesM [] = [[]]
genTuplesM (b:bnds) = concat [ map (i:) (genTuplesM bnds) | i <- [0..b-1] ]

-- main = genTuplesM [3,3,3]

這最初的幾個習題除了給出算法M的變形之外，主要討論兩個問題：

• 求字典序中第pos個元組
• 給定一個元組，求它在字典序中的位置

第一個問題—求字典序中第pos個元組，我們可以如下實現：

base [] = 1
base bnds = head (scanr1 (*) bnds)

findTupleM :: [Int] -> Int -> [Int]
findTupleM bnds pos = last (take pos (genTuplesM bnds))

-- main = findTupleM [1,2,3,4,5,6,7,8,9,10] 1000000

findTupleMByPos :: [Int] -> Int -> [Int]
findTupleMByPos [] _ = []
findTupleMByPos (b:bnds) pos = q:(findTupleMByPos bnds r)
                                where qr = quotRem (pos-1) (base bnds)
                                      q = fst qr
                                      r = snd qr + 1

-- main = findTupleMByPos [1,2,3,4,5,6,7,8,9,10] 1000000

第二個問題—給定一個元組，求它在字典序中的位置，我們可以如下實現：

findPosMByTuple :: [Int] -> [Int] -> Int
findPosMByTuple [] [] = 1
findPosMByTuple (b:bnds) (t:tuple) = t * (base bnds) + findPosMByTuple bnds tuple

-- main = findPosMByTuple [1,2,3,4,5,6,7,8,9,10] [0,0,1,2,3,0,2,7,0,9]

還有一個進展，我理解了冪集的生成其實僅僅是元組生成的特例。集合A的冪集其實就是2^A或者{0,1}^A。

另外推薦大家到LiteratePrograms貢獻自己對算法或者程序設計的知識。Literate Programs也是高德納教授所提倡的。