Consider a set of $m$ column vectors each of length $n$. The elements within each position can either be blank or any combination $k$ different items. The columns and elements within the entries are given. The elements within each column can be permuted independently from other columns. We have to satisfy the constraints in the form of
- $n_i$ rows have least one column containing item $i$
Is there an efficient algorithm to determine a particular solution? For small cases, such as illustrative example below, a quick permutation can be done.
Note: In our application we have around 1,000 rows, 10 columns and 100 different items so complete enumeration is not feasible.
Illustrative example:
3 columns, 5 rows, items are $\{*, \square\}$. The elements can be any combination of those items, in any number; even blank. (small scale for illustration of problem, see note above for sizes in our application)
The following is given
$$ \left[ \begin{array}{c|c|c} & & \\ & & \square\\ & \{\square, \square\} & \square\\ \{*,\square\} & \square & \{\square, \square, \square\}\\ * & * & \square\\ \end{array} \right] $$
We wish to have a solution that
- 3 rows have at least one $\{*\}$
- 5 rows have at least one $\{\square\}$
One such solution would be:
$$ \left[ \begin{array}{c|c|c} & & \square \\ \{*,\square\} & \square & \\ & * & \square\\ & \{\square, \square\} & \{\square, \square, \square\}\\ * & & \square\\ \end{array} \right] $$