如何定义旋转功能

Question

如何定义生成给定列表的所有旋转的旋转函数？

例如:旋转 [1,2,3,4] =[[1,2,3,4],[2,3,4,1],[3,4,1,2],[4,1,2,3]]

我写了一个可以重新排列顺序的shift函数

 shift ::[Int]->[Int]

 shift x=tail ++ take 1 x

但我不知道如何生成这些新数组并将它们附加在一起.

Answer 1

计算列表的所有旋转的另一种方法是使用预定义的函数tails和inits.该函数tails生成列表中所有最终段的列表,同时inits生成所有初始段的列表.例如,

tails [1,2,3] = [[1,2,3], [2,3], [3],   []]

inits [1,2,3] = [[],      [1],   [1,2], [1,2,3]]

也就是说,如果我们按照缩进的指示逐点连接这些列表,我们就会得到所有的旋转.我们只得到原始列表两次,即一次通过在原始列表的末尾附加空的初始段,并且通过将空的最终段附加到原始列表的前面一次.因此,我们使用该函数init来删除应用于zipWith列表的尾部和内部的结果的最后一个元素.该函数zipWith将其第一个参数逐点应用于提供的列表.

allRotations :: [a] -> [[a]]
allRotations l = init (zipWith (++) (tails l) (inits l))

该解决方案优于其他解决方案,因为它不使用length.该函数length非常严格,因为它在完全评估其参数的列表结构之前不会产生结果.例如,如果我们评估应用程序

allRotations [1..]

也就是说,我们计算无限自然数列表的所有旋转,ghci愉快地开始打印无限列表作为第一个结果.相反,基于length此处建议的类似的实现不会终止,因为它计算无限列表的长度.

Answer 2

shift (x:xs)  =  xs ++ [x]
rotates xs    =  take (length xs) $ iterate shift xs

iterate f x返回流("无限列表")[x, f x, f (f x), ...].有元素列表的n轮换n,所以我们take是第一个n.

Answer 3

下列

shift :: [a] -> Int -> [a]
shift l n = drop n l  ++ take n l

allRotations :: [a] -> [[a]]
allRotations l = [ shift l i | i <- [0 .. (length l) -1]]

产量

> ghci
Prelude> :l test.hs
[1 of 1] Compiling Main             ( test.hs, interpreted )
Ok, modules loaded: Main.
*Main> allRotations [1,2,3,4]
[[1,2,3,4],[2,3,4,1],[3,4,1,2],[4,1,2,3]]

正如您所期望的那样。

我认为这是相当可读的，尽管不是特别有效（没有记忆以前的班次）。

如果你关心效率，那么

> ghci
Prelude> :l test.hs
[1 of 1] Compiling Main             ( test.hs, interpreted )
Ok, modules loaded: Main.
*Main> allRotations [1,2,3,4]
[[1,2,3,4],[2,3,4,1],[3,4,1,2],[4,1,2,3]]

将允许您重用之前班次的结果，并避免重新计算它们。

请注意，iterate返回一个无限列表，并且由于惰性求值，我们只将其求值length l到列表中。

请注意，在第一部分中，我扩展了您的移位函数来询问移位多少，然后我对 进行了列表理解allRotations。