3 people like it.

Maximum Sublist Problem

According to Wikipedia, the maximum sub-array problem is a programming task of finding the contiguous sub-array within a one-dimensional array of numbers (containing at least one positive number) which has the largest sum. The following is an attempt to solve this problem by using F# list rather than array.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
31: 
32: 
33: 
34: 
35: 
36: 
37: 
38: 
39: 
40: 
41: 
42: 
43: 
44: 
45: 
46: 
47: 
48: 
49: 
50: 
51: 
52: 
53: 
54: 
55: 
56: 
57: 
module MaxSubList = 
  
  /// Divide the input list into halves
  let split lst =
    let mid = (lst |> List.length)/2
    let left  = lst |> Seq.take mid |> Seq.toList
    let right = lst |> Seq.skip mid |> Seq.toList
    left, right
  
  /// Collect states from mid towards the left end
  let collectState lst =
    List.scanBack(fun x s ->
      let l = s|> fst 
      x::l, (x::l |> List.sum)) lst ([],0)
  
  /// Get the max state from the left list
  let maxList lst = 
    lst |> collectState |> List.maxBy snd |> fst

  /// Collect states from mid towards the right end
  let collectState' lst =
    List.scan(fun s t -> 
      let l = s |> fst
      t::l, (t::l |> List.sum)) ([],0) lst

  /// Get the max state from the right list
  let maxList' lst = 
    lst |> collectState' |> List.maxBy snd |> fst |> List.rev

  /// Crossing maximum subList
  let crossMax left right =
    let maxLeft = maxList left
    let maxRight = maxList' right
    maxLeft@maxRight

  /// Recursive maxSubList
  let rec maxSubList = function
    | [] -> []
    | [x] -> [x]
    | lst -> 
      let left, right = split lst
      let leftMax  = maxSubList left
      let rightMax = maxSubList right
      let crossingMax = crossMax left right
      let sum = List.sum
      if sum leftMax >= sum rightMax && sum leftMax >= sum crossingMax then leftMax
      elif sum leftMax <= sum rightMax && sum crossingMax <= sum rightMax then rightMax
      else crossingMax 

  // Testing cases
  let testList1 = [13;-3;-25;20;-3;-16;-23;18;20;-7;12;-5;-22;15;-4;7]
  let testList2 = [-2; 1; -3; 4; -1; 2; 1; -5; 4]

  // [18; 20; -7; 12]
  maxSubList testList1
  // [4; -1; 2; 1]
  maxSubList testList2
val split : lst:'a list -> 'a list * 'a list

Full name: Script.MaxSubList.split


 Divide the input list into halves
val lst : 'a list
val mid : int
Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
  | ( [] )
  | ( :: ) of Head: 'T * Tail: 'T list
  interface IEnumerable
  interface IEnumerable<'T>
  member Head : 'T
  member IsEmpty : bool
  member Item : index:int -> 'T with get
  member Length : int
  member Tail : 'T list
  static member Cons : head:'T * tail:'T list -> 'T list
  static member Empty : 'T list

Full name: Microsoft.FSharp.Collections.List<_>
val length : list:'T list -> int

Full name: Microsoft.FSharp.Collections.List.length
val left : 'a list
module Seq

from Microsoft.FSharp.Collections
val take : count:int -> source:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.take
val toList : source:seq<'T> -> 'T list

Full name: Microsoft.FSharp.Collections.Seq.toList
val right : 'a list
val skip : count:int -> source:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.skip
val collectState : lst:int list -> (int list * int) list

Full name: Script.MaxSubList.collectState


 Collect states from mid towards the left end
val lst : int list
val scanBack : folder:('T -> 'State -> 'State) -> list:'T list -> state:'State -> 'State list

Full name: Microsoft.FSharp.Collections.List.scanBack
val x : int
val s : int list * int
val l : int list
val fst : tuple:('T1 * 'T2) -> 'T1

Full name: Microsoft.FSharp.Core.Operators.fst
val sum : list:'T list -> 'T (requires member ( + ) and member get_Zero)

Full name: Microsoft.FSharp.Collections.List.sum
val maxList : lst:int list -> int list

Full name: Script.MaxSubList.maxList


 Get the max state from the left list
val maxBy : projection:('T -> 'U) -> list:'T list -> 'T (requires comparison)

Full name: Microsoft.FSharp.Collections.List.maxBy
val snd : tuple:('T1 * 'T2) -> 'T2

Full name: Microsoft.FSharp.Core.Operators.snd
val collectState' : lst:int list -> (int list * int) list

Full name: Script.MaxSubList.collectState'


 Collect states from mid towards the right end
val scan : folder:('State -> 'T -> 'State) -> state:'State -> list:'T list -> 'State list

Full name: Microsoft.FSharp.Collections.List.scan
val t : int
val maxList' : lst:int list -> int list

Full name: Script.MaxSubList.maxList'


 Get the max state from the right list
val rev : list:'T list -> 'T list

Full name: Microsoft.FSharp.Collections.List.rev
val crossMax : left:int list -> right:int list -> int list

Full name: Script.MaxSubList.crossMax


 Crossing maximum subList
val left : int list
val right : int list
val maxLeft : int list
val maxRight : int list
val maxSubList : _arg1:int list -> int list

Full name: Script.MaxSubList.maxSubList


 Recursive maxSubList
val leftMax : int list
val rightMax : int list
val crossingMax : int list
val sum : (int list -> int)
val testList1 : int list

Full name: Script.MaxSubList.testList1
val testList2 : int list

Full name: Script.MaxSubList.testList2

More information

Link:http://fssnip.net/fh
Posted:11 years ago
Author:Joel Huang
Tags: subarray , sublist , list