# Optimal partitioning of n-arrays

You're given N integer arrays. Each array can have different size and contains unique values. However same integers can be found in different arrays.

The goal is to partition those arrays into K groups such that:

1. Arrays grouped together don't share any integer
2. I want to minimize the number of groups

Example:

Input: [[1, 2, 3], [2, 4, 5], [6, 7, 8], [4, 6, 10]]

Suboptimal Solution using 3 groups:

• group 1: [[1, 2, 3], [6, 7, 8]]
• group 2: [[2, 4, 5]]
• group 3: [[4, 6, 10]]

Optimal Solution using 2 groups:

• group 1: [[1, 2, 3], [4, 6, 10]]
• group 2: [[2, 4, 5], [6, 7, 8]]

Any idea on how to solve this effectively?

• There's no polynomial time algorithm, you can quite easily reduce this to the minimum clique cover problem.
– orlp
Commented Oct 6, 2020 at 2:50
• Welcome to COMPUTER SCIENCE @SE. There is a difference between effectively (having the effect under consideration) and efficiently (low effort in relation to effect and problem size). Commented Oct 7, 2020 at 7:42