Haskell - 有没有更好的方法将元素均匀分布在列表上

Question

给定一个这样的矩阵

matrix_table =

[[ 0, 0, 0, 0]
,[ 0, 0, 0, 0]
,[ 0, 0, 0, 0]
,[ 0, 0, 0, 0]
]

和一个列表position_list = [2, 3, 2, 10]

函数的输出

distribute_ones :: [[Int]] -> [Int] -> [[Int]]
distribute_ones matrix_table position_list 

应该是这样的

[[ 0, 1, 0, 1] -- 2 '1's in the list
,[ 0, 1, 1, 1] -- 3 '1's in the list
,[ 0, 1, 0, 1] -- 2 '1's in the list
,[ 1, 1, 1, 1] -- Since 10 > 4, all '1's in the list
]

<小时/>

我尝试过的:

我生成了列表的列表，基本矩阵为

 replicate 4 (replicate 4 0)

然后使用 Data.List.Split 库中的 chunksOf 划分内部列表，以制作 4 - (position_list !! nth).

最后像这样附加并连接 1

take 4 . concat . map (1 :)

尽管我认为这并不是最好的方法。有更好的方法吗？

Answer 1

对于均匀分布的元素，我推荐 Bjorklund 算法。 Bjorklund 的算法需要两个序列进行合并，并重复:

1. 尽可能多地合并两者的前缀，各取一个，然后
2. 递归调用自身，将合并的元素作为一个序列，将较长输入的剩余元素作为另一个序列。

在代码中:

bjorklund :: [[a]] -> [[a]] -> [a]
bjorklund xs ys = case zipMerge xs ys of
    ([], leftovers) -> concat leftovers
    (merged, leftovers) -> bjorklund merged leftovers

zipMerge :: [[a]] -> [[a]] -> ([[a]], [[a]])
zipMerge [] ys = ([], ys)
zipMerge xs [] = ([], xs)
zipMerge (x:xs) (y:ys) = ((x++y):merged, leftovers) where
    ~(merged, leftovers) = zipMerge xs ys

以下是 ghci 中的一些示例:

> bjorklund (replicate 2 [1]) (replicate 2 [0])
[1,0,1,0]
> bjorklund (replicate 5 [1]) (replicate 8 [0])
[1,0,0,1,0,1,0,0,1,0,0,1,0]

如果您愿意，您可以编写一个小包装器，只接受您关心的参数。

ones len numOnes = bjorklund
    (replicate ((-) len numOnes) [0])
    (replicate (min len numOnes) [1])

在 ghci 中:

> map (ones 4) [2,3,2,10]
[[0,1,0,1],[0,1,1,1],[0,1,0,1],[1,1,1,1]]