logo标签列表

在F#中将列表分成两个相等的列表

listf#splitequals
7
我非常陌生 F#，需要帮助解决一个 F# 问题。
我需要实现一个 cut 函数，它将列表分成两半，输出应为...
``` cut [1;2;3;4;5;6];; ```
val it : int list * int list = ([1; 2; 3], [4; 5; 6])
我可以假设列表的长度是偶数。
我还需要定义一个辅助函数 gencut(n, xs)，将 xs 切成两段，其中 n 给出第一段的大小:
``` gencut(2, [1;3;4;2;7;0;9]);; ```
val it : int list * int list = ([1; 3], [4; 2; 7; 0; 9])
通常我不会在这里寻求练习帮助，但我真的不知道从哪里开始。任何帮助，即使只是指导方向，都会有所帮助。
谢谢！
7个回答
14

因为你的列表长度是偶数，而且你要将其平均分成两部分，我建议按照以下步骤进行（先提供伪代码）：

  • 首先，使用两个指针：slow 和 fast。
  • slow 每次移动一个元素，fast 每次移动两个元素。
  • 在 slow 遍历列表的过程中，将每个元素加到累加变量中，同时 fast 一直向前移动。
  • 当 fast 指针到达列表末尾时，slow 只移动了一半的元素，所以它现在在列表的中间位置。
  • 返回 slow 经过的元素和剩余的元素。这应该是将列表平均分成两个整齐的列表。

上述过程只需要遍历一次列表，时间复杂度为 O(n)。

由于这是作业问题，我不会给出完整答案，但是我已经帮你开始了。

let cut l =
    let rec cut = function
        | xs, ([] | [_]) -> xs
        | [], _ -> []
        | x::xs, y::y'::ys -> cut (xs, ys)
    cut (l, l)

注意，x::xs 步进 1 个元素，y::y'::ys 步进 2 个元素。

该函数返回列表的后一半。它很容易修改以返回列表的前一半。

4
您正在寻找F#中的列表切片。在这个SO线程中，@Juliet提供了一个很好的答案：Slice like functionality from a List in F# 基本上，这是因为F#列表中没有常数时间索引访问，所以这不是内置的，但您可以按照详细说明解决此问题。她的方法应用于您的问题将产生（效率不高但可行的）解决方案：
let gencut(n, list) = 
    let firstList = list |> Seq.take n |> Seq.toList
    let secondList = list |> Seq.skip n |> Seq.toList
    (firstList, secondList)
2

攻克list问题的第一步是查看List模块，该模块包含了许多通用问题的高阶函数，可以为您提供简洁的解决方案。如果您在那里找不到合适的内容，那么您可以查看Seq模块，像@BrokenGlass演示的那样寻找解决方案（但是您可能会遇到性能问题）。接下来，您需要考虑递归和模式匹配。处理列表时，您必须考虑两种递归类型：尾递归和非尾递归。它们之间存在权衡。尾递归解决方案涉及使用累加器传递状态，使您可以将递归调用放置在尾部位置，并避免使用大型列表导致堆栈溢出。但是，您通常会得到一个反转的列表！例如：

尾递归gencut解决方案：

let gencutTailRecursive n input =
    let rec gencut cur acc = function
        | hd::tl when cur < n ->
            gencut (cur+1) (hd::acc) tl
        | rest -> (List.rev acc), rest //need to reverse accumulator!
    gencut 0 [] input

非尾递归的gencut解决方案：

let gencutNonTailRecursive n input =
    let rec gencut cur = function
        | hd::tl when cur < n ->
            let x, y = gencut (cur+1) tl //stackoverflow with big lists!
            hd::x, y
        | rest -> [], rest
    gencut 0 input

一旦您拥有了gencut解决方案，定义cut就非常容易:

let cut input = gencut ((List.length input)/2) input
+1 很好的解释 - 但你没有指出为什么一开始就应该以尾递归为目标：它们可以被编译器优化，以不使用任何调用栈空间（因为栈上没有状态需要返回），所以它们允许（基本上）无限递归。 - BrokenGlass
@BrokenGlass - 谢谢！你说得对，那是一个重要的观点。考虑如何回答这个问题，并反思自己的学习经验，我意识到向FP初学者解释像递归列表处理这样基本的东西真的很困难，因为你需要先掌握很多基础知识。 - Stephen Swensen
2
这里有另一种使用内置库函数的方法来完成它，这可能比其他答案更易于理解。此解决方案还仅需要对输入进行一次遍历。看完你的问题后，我首先想到的是你想要类似于List.partition的东西，它可以根据给定的谓词将列表分成两个列表。然而，在你的情况下，这个谓词将基于当前元素的索引，而partition无法处理，除非查找每个元素的索引。
我们可以使用fold或foldBack来实现创建我们自己等效于此行为的方式。我将在此处使用foldBack，因为这意味着您无需在之后反转列表（请参见Stephens的优秀答案）。我们要做的是使用fold提供我们自己的索引以及两个输出列表，所有内容都作为累加器。以下是将根据n索引将列表拆分为两个列表的通用函数：
let gencut n input =
    //calculate the length of the list first so we can work out the index
    let inputLength = input |> List.length 
    let results =
        List.foldBack( fun elem acc-> 
                            let a,b,index = acc     //decompose accumulator
                            if (inputLength - index) <= n then (elem::a,b,index+1)
                            else (a,elem::b,index+1)  ) input ([],[],0)
    let a,b,c = results
    (a,b) //dump the index, leaving the two lists as output.

所以在这里，我们使用 ([],[],0) 作为初始累加器值开始 foldBack。然而，因为我们是从列表末尾开始的，所以需要将表示当前索引的 0 减去列表的总长度，以获取当前元素的实际索引。
然后，我们只需检查当前索引是否在 n 的范围内。如果是，我们通过将当前元素添加到列表 a、保持列表 b 不变并将索引增加 1 来更新累加器：(elem::a,b,index+1)。在所有其他情况下，我们做完全相同的事情，但将元素添加到列表 b 中：(a,elem::b,index+1)。
现在，您可以轻松地创建一个函数来通过创建另一个函数来将列表分成两半，如下所示：
let cut input = 
    let half = (input |> List.length) / 2
    input |> gencut half

我希望能在IT技术方面为您提供一些帮助！

> cut data;;
val it : int list * int list = ([1; 2; 3], [4; 5; 6])

> gencut 5 data;;
val it : int list * int list = ([1; 2; 3; 4; 5], [6])

编辑：你可以通过将长度值作为初始累加器值并在每个周期中取反它来避免使用索引的否定 - 可能更简单一些 :)

let gencut n input =
    let results =
        List.foldBack( fun elem acc-> 
                            let a,b,index = acc     //decompose accumulator
                            if index <= n then (elem::a,b,index-1)
                            else (a,elem::b,index-1)  ) input ([],[],List.length input)
    let a,b,c = results
    (a,b) //dump the index, leaving the two lists as output.
2

我有同样的作业，这是我的解决方案。我只是一名学生，对F#还很陌生。

let rec gencut(n, listb) = 
    let rec cut  n (lista : int list)  (listb : int list) =
        match (n , listb ) with
        | 0, _   ->  lista, listb
        | _, []  -> lista, listb
        | _, b :: listb -> cut  (n - 1) (List.rev (b :: lista ))  listb
    cut n [] listb

let cut xs = gencut((List.length xs) / 2, xs)

这可能不是最好的递归解决方案，但它可以工作。我认为

1

check this one out:

let gencut s xs =  
    ([for i in 0 .. s - 1 -> List.nth xs i], [for i in s .. (List.length xs) - 1 -> List.nth xs i])

你刚刚调用了它

let cut xs =                            
    gencut ((List.length xs) / 2) xs

使用n持续时间仅进行一次迭代，分成两部分

1
您可以使用List.nth进行随机访问，使用列表推导式来生成帮助函数：
let Sublist x y data = [ for z in x..(y - 1) -> List.nth data z ]

这将从数据中返回项目[x..y]。使用此功能，您可以轻松生成gencut和cut函数（记得检查x和y的边界）:)

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接