5

我最近正在尝试一个问题。在这种情况下，我几乎没有问题。

Input: generatingListforRightShifting 2 [1,2,3,4,5,6,7,8]
Output: [[1,2,3,4,5,6,7,8],[8,1,2,3,4,5,6,7],[7,8,1,2,3,4,5,6]]

正如您所了解的，该程序会将元素朝正确的方向移动。第一个参数表示它将执行多少次移位。作为一个新手，我正在尝试解决一些众所周知的列表函数。并使用递归。但对我来说，递归的想法并不清楚。我的代码是：

generatingListforRightShifting' _ []=[]
generatingListforRightShifting' 0 x=x
generatingListforRightShifting' n xs=   newList where
                        newList=takeWhile(\i->[1..n] 
                                            <=n)(reverse(take 
                                           i(reverse xs))++reverse(drop i(reverse xs)))

我知道我正在做的主要错误是在 takeWhile 部分。但是我怎样才能迭代n次。我已经制作了一个程序，可以直接显示移位结果，例如 Input:generatingListforRightShifting 2 [1,2,3,4,5,6,7,8] Output: [7,8,1,2,3,4, 5,6] 但是当我尝试进行所有先前的转换时，我做不到。

有谁可以帮我离开这里吗。如果你给我解决的想法，我也欢迎你。

4

6 回答 6

3

这通常称为旋转而不是移位。将列表向右旋转一次很简单，因为有一些方法可以获取最后一个元素和除最后一个之外的所有元素的子列表。

rotateOnce lst = (last lst):(init lst)

另请注意，旋转两次相当于调用 rotateOnce 两次。因此，该方法可以简单地实现为先前结果的递归：

rotateN 0 lst = [lst]
rotateN n lst = lst : rotateN (n-1) ((last lst):(init lst))

（注意：这可能不是最佳解决方案。）

于 2012-10-24T11:57:19.767 回答
2

您似乎更喜欢我们修复您的代码而不是重新开始，所以让我们看看您的代码。首先，主列表砍：

reverse (take i (reverse xs)) ++ reverse (drop i (reverse xs))

现在从列表末尾reverse (take i (reverse xs))获取i元素，但是您将列表反转两次以实现此目的，这样做会更好 drop (length xs - i) xs。同样，您可以实现reverse (drop i (reverse xs))) 为take (length xs - i) xs. 这给了我们

drop (length xs - i) xs ++ take (length xs - i) xs

现在您的代码\i->[1..n]<=n没有意义，因为它将列表[1..n] 与进行比较n，这是行不通的。我认为您正在尝试创建一个i从 1to运行的循环n，这是一个不错的计划。让我们使用列表推导来获得我们想要的：

[drop (length xs - i) xs ++ take (length xs - i) xs | i <- [1 .. length xs], i <= n]

但是现在我们从 1 运行到列表的长度，但丢弃了上面的数字n，这样写会更好

[drop (length xs - i) xs ++ take (length xs - i) xs | i <- [1..n]]

这确实允许n超过length xs，但我看不出有什么大问题，我们可以先检查一下。

现在请注意，我们只i在 form(length xs - i)中使用，实际上我们重新计算 length xs的次数比我们应该的要多得多，所以不要让run ifrom 1ton和 using length xs - i，我们为什么不直接运行 from to ：j=length xs -ijlength xslength xs - n

[drop j xs ++ take j xs | j <- [length xs,length xs - 1 .. length xs - n]]

这有效，因为例如[6,5..1] == [6,5,4,3,2,1]

这样做会更整洁

let l = length xs in
  [drop j xs ++ take j xs | j <- [l,l - 1 .. l - n]]

或者你可能take比你更喜欢做算术，所以我们可以使用：

let l = length xs in
  take n [drop j xs ++ take j xs | j <- [l,l - 1 .. 0]]

这还有一个额外的好处，就是阻止你做太多事情，当你回到起点时阻止你。

我会将您的功能从generatingListforRightShiftingto重命名rotationsR为

rotationsR n xs = let l = length xs in
  take n [drop j xs ++ take j xs | j <- [l,l - 1 ..]]

这给了rotationsR 6 [1..4] == [[1,2,3,4],[4,1,2,3],[3,4,1,2],[2,3,4,1],[1,2,3,4]].

左旋转看起来更简单：

rotationsL n xs = take n [drop j xs ++ take j xs | j <- [0..length xs]]

题外话：我忍不住，对不起，我又开始了。

我仍然不喜欢每次都丢掉和拿走所有的东西，我宁愿弹出无限多的副本xs（第一个：cycle xstails

rotationsL' n xs = let l = length xs in take n 。地图（取 l）。尾巴。周期 $xs

由于惰性评估，只有有限的cycle xsever 被计算，但是这个可以运行和运行：rotationsL' 10 [1..4]给你：

 [[1,2,3,4],[2,3,4,1],[3,4,1,2],[4,1,2,3],[1,2,3,4],[2,3,4,1],[3,4,1,2],[4,1,2,3],[1,2,3,4],[2,3,4,1]]

以这种方式进行正确的循环也很好，但它不起作用，因为我需要从无限列表的末尾开始并返回。让我们重用你的反向，采取你需要的，再次反向技巧，虽然：

rotationsR' n xs = let l = length xs in
  take n . map (reverse.take l) . tails . cycle . reverse $ xs

题外话：如果您宁愿更贴近原始代码，您可以这样做

generatingListforRightShifting n xs = 
    [reverse (take i (reverse xs)) ++ reverse (drop i (reverse xs)) | i <- [1..n]]
于 2012-10-24T16:44:08.927 回答
2

您可以递归地定义“移位”：shift 0是无操作，shift 1+n (x:xs)是shift n xs。

就像是：

shift 0 = \x -> x
shift n = \lst@(x:xs) -> (shift (n-1) xs)

-- example:
sh3 = shift 3

然后“旋转”问题变得更容易：

rotate n = \lst -> (shift lst) ++ (take n lst)
于 2012-10-24T11:53:45.260 回答
1

我会放弃目前非常复杂的方法。相反，专注于抽象操作的不同组件。如果将操作分成几部分，您会注意到有两个对称组件：向左旋转列表，向右旋转列表。您希望定义的操作在某个列表上以指定的次数迭代右旋转。这表明可以通过对左或右旋转进行指定次数的迭代来定义所需的操作。例如，

left :: [a] -> [a]
left [] = []
left xs = tail xs ++ [head xs]

right :: [a] -> [a]
right [] = []
right xs = last xs : init xs

shiftL :: Int -> [a] -> [[a]]
shiftL n = take n . iterate left

shiftR :: Int -> [a] -> [[a]]
shiftR n = take n . iterate right
于 2012-10-24T12:29:20.560 回答
1

在这里使用cycle看起来不错：

shifts n xs = take (n+1) $ shifts' (cycle xs)
  where
    len = length xs
    shifts' ys = take len ys:shifts' (drop (len-1) ys)
于 2012-10-24T13:15:12.110 回答
1

我发现左旋转非常简单，使用splitAt：

import Data.Tuple (swap)
rotateLeft n = uncurry (++) . swap . splitAt n

> rotateLeft 2 "Hello World!"
>>> "llo World!He"
于 2012-10-24T18:05:10.303 回答