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)

然后分成内列出与chunksOf从Data.List.Split库做出的切口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]]