Let say i have N sets of same size (max 500) having integers filled with 1 to 9 now I want to find a new set such that when its elements are compared then i should get same element in worst case comparison.
plz see the example 1 2 1 1 3 , 2 2 1 2 1 , 1 2 3 1 1 are 3 sets now display the set -, 2 , - ,- ,- here 2th element is obvious since it is same in all , so what blank space should be filled with??
if i say 1 2 1 1 1 is my answer set then matching elements are 4 , 3 , 4 respectively for 3 given set, so worst is 3 hence 3 element are matched and 1 2 1 1 1 will be optimal choice and my score is 3.
I am looking to create a special set in which for worst case comparison is maximized and hence my score.
any help ! thnx in advance
You can solve the problem via integer linear programming as follows. For clues $c\in\{1,\dots,N\}$ and positions $p\in\{1,\dots,5\}$, let $a_{c,p}$ denote the value that appears in the input. For positions $p\in\{1,\dots,5\}$ and digits $d\in\{1,\dots,9\}$, let binary decision variable $x_{p,d}$ indicate whether position $p$ takes value $d$. The problem is to maximize $z$ subject to: \begin{align} \sum_d x_{p,d} &= 1 &&\text{for all $p$}\\ z &\le \sum_{p, d:\ a_{c,p} = d} x_{p,d} &&\text{for all $c$} \end{align} The first constraint assigns exactly one digit to each position. The second constraint enforces the max-min objective.
For your sample data, an optimal $x$, with a score of $z=3$, is: \begin{matrix} p\backslash d &1 &2 &3 &4 &5 &6 &7 &8 &9 \\ \hline 1 &1 &0 &0 &0 &0 &0 &0 &0 &0 \\ 2 &0 &1 &0 &0 &0 &0 &0 &0 &0 \\ 3 &1 &0 &0 &0 &0 &0 &0 &0 &0 \\ 4 &1 &0 &0 &0 &0 &0 &0 &0 &0 \\ 5 &1 &0 &0 &0 &0 &0 &0 &0 &0 \\ \end{matrix} This corresponds to vector $(1,2,1,1,1)$.