如何定义旋转函数

Question

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

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

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

 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 应用到列表的 tails 和 inits 的结果的最后一个元素。函数 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, fx, f (fx), ...]。 n 元素列表有 n 次旋转，因此我们采用其中的前 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]]

正如您所期望的那样。

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

---

如果您关心效率，那么

shift :: [a] -> [a]
shift [] = []
shift (x:xs) = xs ++ [x]

allRotations :: [a] -> [[a]]
allRotations l = take (length l) (iterate shift l)

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

请注意，迭代返回一个无限列表，并且由于惰性计算，我们只将其计算到列表中的长度为l。

---

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

Answer 4

到目前为止给出的答案对于有限列表来说效果很好，但当给出无限列表时最终会出错。 （它们都在列表中调用length。）

shift :: [a] -> [a]
shift xs = drop 1 xs ++ take 1 xs

rotations :: [a] -> [[a]]
rotations xs = zipWith const (iterate shift xs) xs

我的解决方案使用zipWith const。 zipWith const foos bar 乍一看可能与 foos 相同（回想一下 const xy = x）。但是，当任一输入列表终止时，从 zipWith 返回的列表也会终止。

因此，当 xs 有限时，返回的列表与 xs 的长度相同，正如我们所希望的那样；当 xs 为无限时，返回的列表不会被截断，因此将是无限的，再次如我们所愿。

（在您的特定应用程序中，尝试旋转无限列表可能没有意义。另一方面，它可能没有意义。我提交此答案只是为了完整性。）

Answer 5

我更喜欢以下解决方案，使用内置函数 cycle 和 tails：

rotations xs = take len $ map (take len) $ tails $ cycle xs where
    len = length xs 

对于您的示例 [1,2,3,4]函数cycle生成一个无限列表[1,2,3,4,1,2,3,4,1,2...]。函数 tails 从给定列表生成所有可能的尾部，这里 [[1,2,3,4,1,2...],[2,3,4,1, 2,3...],[3,4,1,2,3,4...],...]。现在我们需要做的就是将“尾部”列表削减到长度 4，并将整个列表削减到长度 4，这是使用 take 完成的。引入别名len是为了避免多次重新计算length xs。

Answer 6

我想它会是这样的（我现在没有ghc，所以我无法尝试）

shift (x:xs) = xs ++ [x]

rotateHelper xs 0 = []
rotateHelper xs n = xs : (rotateHelper (shift xs) (n - 1))

rotate xs = rotateHelper xs  (length xs)

Answer 7

myRotate lst = lst : myRotateiter lst lst
  where myRotateiter (x:xs) orig
          |temp == orig = []
          |otherwise = temp : myRotateiter temp  orig               
          where temp = xs ++ [x]

Answer 8

我建议：

rotate l = l : rotate (drop 1 l ++ take 1 l)

distinctRotations l = take (length l) (rotate l)