find minimal number of column

Question

Here is a example: Suppose I have a 2D-array which only include 0 and 1:

0,1,0,0
0,0,0,1
1,0,1,0

I need to find minimal number of column which can be add up to ones vector. For example, column0 + column1 + column3 =0,0,1 + 1,0,0 + 0,1,0 = 1,1,1 So, the minimal number of column is 3.

score 3 · Accepted Answer · answered May 24 '16 at 12:25

This is basically a Set cover problem, which is NP-hard. It can be formulated and solved (optimally) as Integer Linear Programming problem.

You can also translate the problem to another problem of the same class which have very good solvers, e.g. to boolean SAT.

Last, but not least, you can solve it suboptimally using greedy and/or local search algorithms, e.g. Simmulated Annealing.

score 0 · Answer 2 · edited May 23 '17 at 11:46

Shamelessly copied combination code from: https://stackoverflow.com/a/34588366/1203882

import java.util.ArrayList;
import java.util.List;

public class Combin {

    public static void main(String... banana) {
        int[][] input = new int[][] { { 0, 1, 0, 0 }, { 0, 0, 0, 1 }, { 1, 0, 1, 0 } };
        List<int[]> columns = new ArrayList<int[]>();
        int min = Integer.MAX_VALUE;

        //Set columns list
        for (int column = 0; column < input[0].length; column++) {
            int[] e = new int[input.length];
            int index = 0;
            for (int row = 0; row < input.length; row++) {
                e[index++] = input[row][column];
            }
            columns.add(e);
        }

        //Sizes 0 1 2 3 and 4
        for (int i = 0; i <= columns.size(); i++)
        {
            List<List<int []>> theList = getCombinations(i, columns);
            for (List <int[]> a : theList)
            {
                if (check(a))
                {
                    if (a.size() < min)
                        min = a.size();

                    //For the test returns 3, 3, and 4 as possibilities.
                    System.out.println("Found a possibility: " + a.size());
                }
            }
        }
        System.out.println("Min value: " + min);
    }

    public static <T> List<List<T>> getCombinations(int k, List<T> list) {
        List<List<T>> combinations = new ArrayList<List<T>>();
        if (k == 0) {
            combinations.add(new ArrayList<T>());
            return combinations;
        }
        for (int i = 0; i < list.size(); i++) {
            T element = list.get(i);
            List<T> rest = getSublist(list, i+1);
            for (List<T> previous : getCombinations(k-1, rest)) {
                previous.add(element);
                combinations.add(previous);
            }
        }
        return combinations;
    }

    public static <T> List<T> getSublist(List<T> list, int i) {
        List<T> sublist = new ArrayList<T>();
        for (int j = i; j < list.size(); j++) {
            sublist.add(list.get(j));
        }
        return sublist;
    }  

    //Create a vector by "or"ing every value.
    public static boolean check(List<int []> result)
    {   
        if (result.size() == 0)
            return false;
        int [] a = new int [result.get(0).length];
        for(int [] j : result)
            for (int index = 0; index < a.length; index++)
                a[index] |= j[index];
        return equalsVec(a);
    }

    //If all values aren't 1, return false. (ones vector)
    public static boolean equalsVec(int [] a)
    {
        for (int i = 0; i < a.length; i++)
            if (a[i] != 1)
                return false;
        return true;
    }
}

Output:

Found a possibility: 3
Found a possibility: 3
Found a possibility: 4
Min value: 3

find minimal number of column

2 Answers2