Maximum uniqueness in pairs of numbers with a slight constraint

Question

Here's an algorithmic challenge for you,

I have a list of [0..100] pairs of numbers and I need to find the maximum number of unique "left number" while making sure there is no more than 3 of the "right number".

Here's an example

• (1, 1)
• (2, 1)
• (3, 1)
• (4, 1)
• (5, 1)
• (6, 1)
• (7, 1)
• (1, 2)
• (4, 2)
• (1, 3)
• (2, 3)
• (5, 4)

And the result would be: 7. We would take: (3, 1), (6, 1), (7, 1), (1, 2), (4, 2), (2, 3) and (5, 4).

For whatever reason I can't seem to find any other way than brute forcing it...

Any help is greatly appreciated :)

Answer 1

You can express this problem as a maximum flow problem:

Make edges of capacity 1 from a source node to each of your left numbers.

Make edges of capacity 3 from each of your right numbers to a sink node.

Make edges of capacity 1 from left number a to right number b for each pair of the form (a, b).

Compute the maximum flow in this network from source to sink.

Answer 2

If anyone is interested in the implementation, here's a ruby version of the push–relabel maximum flow algorithm with relabel-to-front selection rule.

def relabel_to_front(capacities, source, sink)
  n      = capacities.length
  flow   = Array.new(n) { Array.new(n, 0) }
  height = Array.new(n, 0)
  excess = Array.new(n, 0)
  seen   = Array.new(n, 0)
  queue  = (0...n).select { |i| i != source && i != sink }.to_a

  height[source] = n - 1
  excess[source] = Float::INFINITY
  (0...n).each { |v| push(source, v, capacities, flow, excess) }

  p = 0
  while p < queue.length
    u = queue[p]
    h = height[u]
    discharge(u, capacities, flow, excess, seen, height, n)
    if height[u] > h
      queue.unshift(queue.delete_at(p))
      p = 0
    else
      p += 1
    end
  end

  flow[source].reduce(:+)
end

def push(u, v, capacities, flow, excess)
  residual_capacity = capacities[u][v] - flow[u][v]
  send = [excess[u], residual_capacity].min
  flow[u][v] += send
  flow[v][u] -= send
  excess[u] -= send
  excess[v] += send
end

def discharge(u, capacities, flow, excess, seen, height, n)
  while excess[u] > 0
    if seen[u] < n
      v = seen[u]
      if capacities[u][v] - flow[u][v] > 0 && height[u] > height[v]
        push(u, v, capacities, flow, excess)
      else
        seen[u] += 1
      end
    else
      relabel(u, capacities, flow, height, n)
      seen[u] = 0
    end
  end
end

def relabel(u, capacities, flow, height, n)
  min_height = Float::INFINITY
  (0...n).each do |v|
    if capacities[u][v] - flow[u][v] > 0
      min_height = [min_height, height[v]].min
      height[u] = min_height + 1
    end
  end
end

And here's the code to transform the pairs of numbers into the capacities array of array

user_ids = Set.new
post_ids = Set.new

pairs.each do |p|
  user_ids << p[:user_id]
  post_ids << p[:post_id]
end

index_of_user_id = {}
index_of_post_id = {}

user_ids.each_with_index { |user_id, index| index_of_user_id[user_id] = 1 + index }
post_ids.each_with_index { |post_id, index| index_of_post_id[post_id] = 1 + index + user_ids.count }

source = 0
sink = user_ids.count + post_ids.count + 1
n = sink + 1

capacities = Array.new(n) { Array.new(n, 0) }
# source -> user_ids = 1
index_of_user_id.values.each { |i| capacities[source][i] = 1 }
# user_ids -> post_ids = 1
pairs.each { |p| capacities[index_of_user_id[p[:user_id]]][index_of_post_id[p[:post_id]]] = 1 }
# post_ids -> sink = 3
index_of_post_id.values.each { |i| capacities[i][sink] = 3 }