CODEWITHSUNDEEP
dynamic-programming
user3717271
user3717271

Reputation: 57

Grouping numbers into the fewest fix-sized groups based on a range

Suppose I have a group that can hold numbers with these two criteria:

  1. It has a range of 5 i.e. the difference between the lowest and highest number can be up to 5.
  2. Each group can hold a maximum of 4 numbers.

e.g. if I have numbers 1,2,3,4,6,8,10,11,13,16,17,18. How do I go about grouping these numbers in the fewest number of windows possible? two possible answers:

  1. [1,2,3,4],[6,8,10,11],[13,16,17,18]
  2. [1,2,3],[4,6,8],[10,11,13],[16,17,18]

Maybe this is not the best example, but is there a programming problem that is similar to this?

Upvotes: 1

Views: 95

Answers (1)

Andrey Tyukin
Andrey Tyukin

Reputation: 44908

That's not a good problem for dynamic programming. A greedy algorithm is enough.

Here is a very rough sketch of a proof that greedy is enough.

(remark-1) Suppose that [x1, x2, ..., xN] is your input sequence of numbers and [(1 = l1, r1), (l2, r2), ..., (lM, rM = N)] are pairs of indices between 1 and N which describe the (start, end) of a window, such that all those windows together satisfy your constraints and cover all numbers in the sequence. Now remove xN. Obviously, the old cover of [x1, ..., xN] can be transformed into a new cover [(1 = l1, r1), ..., (lM, N - 1)] of [x1, ..., x{N-1}], and it has at most as many (or one fewer) windows as the old cover.

(induction) Now make an induction over N to show that the greedy "cut-as-much-as-you-can-from-the-end-of-the-list"-algorithm is optimal.

  • For [x1] the greedy algorithm finds the cover [(1, 1)], which is obviously optimal.

  • Assume that the greedy algorithm finds the optimal covering for [x1, ..., xK] for all K < N. Let M be the smallest index such that xN - xM <= maxWindowWidth and N - M <= maxElemsPerWindow. Let Z be the optimal number of windows that is required to cover [x1, ..., x{M - 1}]. If we choose (M', N) as the last window for any M' > M, then by (remark-1) the solution Z' for [x1, ..., x{M'}] will be equal or worse than Z, that is, Z' >= Z, and we will need (Z' + 1) >= (Z + 1) windows in total. Since the greedy algorithm always cuts away as many elements as possible, it will choose (M, N) as the last window, and end up with (Q + 1) windows in total, where Q is the number of windows the greedy algorithm will use to cover [x1, ..., x{M-1}]. But by induction assumption Q = Z, and thus the greedy algorithm will need Z + 1 windows, which is equal or better than any other solution Z' + 1.

Hence, the greedy algorithm is optimal.

Here is a sketch in Scala:

def greedyCoverByWindows(
  numbers: List[Int], 
  maxWindowWidth: Int,
  maxElemsPerWindow: Int
): List[List[Int]] = numbers match {
  case Nil => Nil
  case h :: t => {
    val window = h :: t.take(maxElemsPerWindow - 1).filter(_ - h <= maxWindowWidth)
    val rest = t.drop(window.size - 1)
    window :: greedyCoverByWindows(rest, maxWindowWidth, maxElemsPerWindow)
  }
}

val example = List(1,2,3,4,6,8,10,11,13,16,17,18)
val maxWindowWidth = 5
val maxElemsPerWindow = 4

val cover = greedyCoverByWindows(example, maxWindowWidth, maxElemsPerWindow)

println(example)
println(cover)

// Output:
// List(1, 2, 3, 4, 6, 8, 10, 11, 13, 16, 17, 18)
// List(List(1, 2, 3, 4), List(6, 8, 10, 11), List(13, 16, 17, 18))

Upvotes: 1

Related Questions