3 people like it.
Like the snippet!

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

Next Version Raw view Test code New version

More information

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