найти минимальный номер столбца

Question

Вот пример: Предположим, у меня есть 2D-массив, который только включают в себя 0 и 1:

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

Мне нужно найти минимальное число столбца, который может быть добавить до тех вектор. Например, column0 + column1 + колонка3 = 0,0,1 + 1,0,0 + 0,1,0 = 1,1,1 Таким образом, минимальное количество столбца 3.

Answer 1

Это в основном Set cover problem, которая является NP-трудной. Он может быть сформулирован и решен (оптимально) как задача целочисленного линейного программирования.

Вы также можете перевести проблему на другую проблему того же класса, которая имеет очень хорошие решатели, например. к логическому SAT.

Последнее, но не менее важное: вы можете решить его субоптимально с использованием жадных алгоритмов и/или локальных алгоритмов поиска, например. Симулированный отжиг.

Answer 2

Бесстыдно скопирована комбинацию кода из: 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; 
    } 
} 

Выход:

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