如何定义一个旋转函数 [英] How to define a rotates function

问题描述

例如：旋转 [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 
  

但我不知道如何生成这些新数组并将它们追加在一起。 以下

shift :: [a] - > Int - > [a]
移位l n =下降n l ++取n l

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


yield

 > ghci 
前奏> ：l test.hs 
 [1的1]编译主（test.hs，解释）
好​​了，加载的模块：Main。 
 * Main> allRotations [1,2,3,4] 
 [[1,2,3,4]，[2,3,4,1]，[3,4,1,2]，[4,1， 2,3]] 
  

这是您的预期。

我认为这是相当可读的，尽管不是特别有效（没有记录先前的转变发生）。

---

如果您关心效率，那么 $ b

  shift :: [a]  - > [a] 
 shift [] = [] 
 shift（x：xs）= xs ++ [x] 
 
 allRotations :: [a]  - > [[a]] 
 allRotations l = take（length l）（iterate shift l）
  

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

请注意， iterate 返回无限的列表，并且由于懒惰的评估，我们只评估它高达长度l 到列表中。

---

请注意，在第一部分中，我已经扩展了shift功能以询问需要转移多少，然后我对 allRotations 。

How to define a rotates function that generates all rotations of the given list?

For example: rotates [1,2,3,4] =[[1,2,3,4],[2,3,4,1],[3,4,1,2],[4,1,2,3]]

I wrote a shift function that can rearrange the order

 shift ::[Int]->[Int]

 shift x=tail ++ take 1 x

but I don't how to generate these new arrays and append them together.

解决方案

The following

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]]

yields

> 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]]

which is as you expect.

I think this is fairly readable, although not particularly efficient (no memoisation of previous shifts occurs).

---

If you care about efficiency, then

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

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

will allow you to reuse the results of previous shifts, and avoid recomputing them.

Note that iterate returns an infinite list, and due to lazy evaluation, we only ever evaluate it up to length l into the list.

---

Note that in the first part, I've extended your shift function to ask how much to shift, and I've then a list comprehension for allRotations.

这篇关于如何定义一个旋转函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！