Find all Combinations of a Matrix

I have a $$16\times11$$ matrix and want to find all eligible* combinations of this matrix including always entities from all 11 columns.

A simple example from a $$2\times3$$ matrix would be the following:

$$\begin{bmatrix} 1 & 2 \\ 3 & 0 \\ 5 & 6 \end{bmatrix}$$

1,2; 1,0; 1,6;

3,2; 3,0; 3,6;

5,2; 5,0; 5,6

1,3,5 (is for my case, not an option)

*Combinations with 0 entries should get neglected

I have already found a direct algorithm that provides all such combinations Return all combinations from the matrix in Java provided from the user @Niklas Rosencrantz. I have edited the code to fit my case. The problem with this case is it takes too long since I have to use for-loop $$16^{11} = 17,592,186,044,416$$ times. For an iteration of $$10,000,000$$ the code needs 25s including reading the data from an Excel file. This means that I need roughly 21 days for the calculation of all data.

I can model the same problem using linear programming. Is there a way to find only the feasible solutions of the problem without searching for the optimal one? I have found documentation in the gurobi site PoolSolutions although I am not sure if this is the best way to search them.

Does it make any sense to use linear programming for this case?

public class main {
private static String excelFileName = "Mappe1 v2.xlsx";
private static int startExcelColumnIndex = 1;
private static int endExcelColumnIndex = 11;
private static int startExcelRowIndex = 1;
private static int endExcelRowIndex = 16;
private static ArrayList<String> stringArrayList = new ArrayList<String>();
private static int maxNumberProviders = 2;
private static List<int[]> combine(int[][] matrix) {
int sizeArray[] = new int[matrix.length];
int counterArray[] = new int[matrix.length];
long total = 1;
for (int i = 0; i < matrix.length; ++i) {
sizeArray[i] = matrix.length; //todo: check this if the following two lines are correct!
total *= matrix.length; // rows^columns
}
//        total = 100000000; //fixme: remove this line after checking the
//        combinations barier
//        List<int[]> list = new ArrayList<>(total);
List<int[]> list = new ArrayList<>();
StringBuilder sb;
String s;
for (long count = total; count > 0; --count) {
// check the number of different providers, using the counterArray
boolean combinationAcceptable = combinationAllowedForMaxNumberOfProviders(counterArray);
boolean combinationPossible;
sb = new StringBuilder();
s = "";
if (combinationAcceptable) {
combinationPossible = true;
for (int i = 0; i < matrix.length; ++i) {
if (matrix[counterArray[i]][i]>0) {
sb.append(matrix[counterArray[i]][i]);
s = s + "; " + counterArray[i] +  "," + i + "; ";
} else {
combinationPossible = false;
break;
}
}
} else {
combinationPossible = false;
}
if (combinationPossible) {
int tmpi[] = new int[sb.toString().length()];
for (int tmp = 0; tmp < sb.toString().length(); tmp++) {
tmpi[tmp] = Integer.parseInt("" + sb.toString().toCharArray()[tmp]);
}
} else {
combinationPossible = true;
}
for (int incIndex = matrix.length - 1; incIndex >= 0; --incIndex) {
if (counterArray[incIndex] + 1 < sizeArray[incIndex]) {
++counterArray[incIndex];
break;
}
counterArray[incIndex] = 0;
}
}
return list;
}
public static boolean combinationAllowedForMaxNumberOfProviders(int[] counterArray) {
HashSet<Integer> integerHashSet = new HashSet<>();
for (int i = 0; i < counterArray.length; i++) {
int rowIndex = counterArray[i];
}
if (integerHashSet.size() <= maxNumberProviders) {
return true;
} else {
return false;
}
}
public static void main(String[] args) {
/*int[][] matrix = {{1, 2, 3},
{4, 5, 6},
{7, 8, 9}};*/
int[][] matrix = new int[endExcelRowIndex][endExcelColumnIndex];
int i = 0;
combine(matrix);
writeToTXT();
}
public static void writeToTXT() {
PrintWriter writer = null;
try {
writer = new PrintWriter("MatrixCombinations.txt", "UTF-8");
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (UnsupportedEncodingException e) {
e.printStackTrace();
}
for (String s: stringArrayList
) {
writer.println(s);
}
writer.close();
}
public static void readXlsx(int[][] matrix) {
File myFile = new File(excelFileName);
FileInputStream fis = null;
try {
fis = new FileInputStream(myFile);
} catch (FileNotFoundException e) {
e.printStackTrace();
System.exit(0);
}

// Finds the workbook instance for XLSX file
XSSFWorkbook myWorkBook = null;
try {
myWorkBook = new XSSFWorkbook(fis);
} catch (IOException e) {
e.printStackTrace();
System.exit(0);
}
XSSFSheet mySheet = myWorkBook.getSheet("Kombinationen");
// Get iterator to all the rows in current sheet
Iterator<Row> rowIterator = mySheet.iterator();
while (rowIterator.hasNext()) {
Row row = rowIterator.next();
if (row.getRowNum() >= startExcelRowIndex && row.getRowNum() <= endExcelRowIndex) {
Iterator<Cell> cellIterator = row.cellIterator();
while (cellIterator.hasNext()) {
Cell cell = cellIterator.next();
if (cell.getColumnIndex() >= startExcelColumnIndex && cell.getColumnIndex() <= endExcelColumnIndex) {
matrix[row.getRowNum()-startExcelRowIndex][cell.getColumnIndex()-startExcelColumnIndex] = (int) cell.getNumericCellValue();

}
}
}
}
}
}
• how can you expect to produce an output of cardinality $16^{11}$ without at least touching each item at least once? when the output is that large, this is a lower bound on the running time of the algorithm... Nov 26 '19 at 17:31
• I would rethink about why do you need all the $16^{11}$ combinations at once. Do you need to do something on each individual pair? Then, rather than generating all those $16^{11}$ combinations at once, pass each one to what you want to do one by one. You can do something like that by creating generators (this is Python. I think the idea should be similar in Java)
– EhsanK
Nov 26 '19 at 18:08
• I would solve this problem using backtracking. From what I can see, you want a maximum amount of unique values per combination. Say MAX=2 and your first 3 values are different, then there is no need to check all possible combinations afterwards. This eliminates a lot. Smart sorting of the matrix might speed up the process. Check out the N Queens Problem and try to understand recursion and backtracking that way, then this problem might make more sense. PS: I did not really catch what 'optimal' means in this context and I am not even sure about 'feasible', I tried to derive it from your code. Nov 26 '19 at 20:38
• @EhsanK No, I do not need each pair. I have a matrix with elements of 0,1,2. All combinations with a zero entity should get discarded/ignored. Still, I have to somehow search for these entities to find out they are equal to 0. I will try to optimize the matrix/data. Nov 27 '19 at 13:24
• @Maarten This is a great tip. Optimizing my matrix will save computing time since I do not need all entities. With feasible and optimal I meant in the case I would use linear programming to find such combinations, a feasible solution would be $(1,2)$ according to my example shown above. Nov 27 '19 at 13:28

It sounds like what you want is to reduce each vector in your matrix to the relevant entries, and take the Cartesian Product of the column vectors. That is definitely not a problem where linear programming can help, but where you should resort either to traditional combinatorial algorithms, or use a database system that typically has support for generating all kinds of combinations of (sets of) columns in tables.

Writing code that generates a Cartesian product is doable, but also a hassle. I would advice to use a Java library that supports combinatorics; one that I could find with a simple search is combinatoricslib3. This library has the advantage that it does not generate all combinations in memory, but rather generates them one-by-one when they are requested (in a lazy fashion). That is probably a lot more efficient when you just want to write all combinations to a file, and the amount of RAM in your computer is not a bottleneck any more on which sizes of files you can generate.

I noted that your Java code suffers from resource leaks, which is wise (and easy) to avoid by using the try-with-resources construct that was introduced in Java 7 and which is very similar to Python's with keyword.

Finally, it is not clear to me how you want to deal with duplicate values in columns. Maybe your data is sanitized and such values do not occur, or maybe you want duplicate values to result in certain combinations being duplicated in your output as well. That is something to think about.

Writing neater Java code than in your example, you would end up with something like the following. Note that I did not test this code in much detail, and that I use some Java 8 features to make life easier or more flexible.

import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.PrintWriter;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.function.IntPredicate;
import java.util.stream.Collectors;

import org.apache.poi.ss.usermodel.Cell;
import org.apache.poi.ss.usermodel.Row;
import org.apache.poi.ss.usermodel.Sheet;
import org.apache.poi.xssf.usermodel.XSSFWorkbook;
import org.paukov.combinatorics3.Generator;
import org.paukov.combinatorics3.IGenerator;

public class Main {

public static void main(String [] args) throws IOException {
// Define input/output files
File input = new File("Mappe1 v2.xlsx");
File output = new File("MatrixCombinations.txt");

// Define cell range
// Alternatively, you can do:

// Read the data from the input file (this is the non-unique version due to the use of false)
List<List<Integer>> data = readDataNonZero(input, "Kombinationen", range, true);

// Generate a lazy/iterable version of cartesian product based combinations
IGenerator<List<Integer>> combinations = combinations(data);
// Write everything to the output file delimited by ; symbols
writeToFile(output, ";", combinations);
}

public static void writeToFile(File output, String delim, Iterable<List<Integer>> combinations) throws IOException {
try (PrintWriter pw = new PrintWriter(output, "UTF-8")) {
for (List<Integer> combination : combinations) {
// Convert the integers to a delimited String
String row = combination.stream()
.map(Object::toString)
.collect(Collectors.joining(delim));
// Write the row to the output
pw.println(row);
}
}
}

public static IGenerator<List<Integer>> combinations(List<List<Integer>> matrix) {
// Some casting required due to generics/arrays behavior in Java
@SuppressWarnings("unchecked")
List<Integer> [] array = (List<Integer>[]) Array.newInstance(List.class, matrix.size());
array = matrix.toArray(array);
return Generator.cartesianProduct(array);
}

// Reads the data from a particular spreadsheet file and provides a default predicate which only removes zero values
public static List<List<Integer>> readDataNonZero(File file, String sheetName, CellRangeAddress range, boolean unique) throws IOException {
return readData(file, sheetName, range, i -> i != 0, unique);
}

public static List<List<Integer>> readData(File file, String sheetName, CellRangeAddress range, IntPredicate accept, boolean unique) throws IOException {
// This try-with-resources avoids a resource leak
try (XSSFWorkbook wb = new XSSFWorkbook(new FileInputStream(file))) {
}
}

/**
* Reads data from a spreadsheet in the given cell range and constructs a sparsified data set as a list of lists
* @param sheet the sheet to read
* @param accept a predicate which we use to check which numbers should be included
* @param unique whether each column in our data set should hold unique values or whether duplicates are allowed
* @return a list of column-lists that contain possibly unique occurrences of values that are valid according to the predicate
*/
public static List<List<Integer>> readData(Sheet sheet, CellRangeAddress range, IntPredicate accept, boolean unique) {
int firstCol = range.getFirstColumn();
// Initialize the output data structure
int cols = 1 + range.getLastColumn() - firstCol;
List<List<Integer>> result = new ArrayList<>(cols);
List<Set<Integer>> uniqueCheck = new ArrayList<>(cols);
for (int t=0; t < cols; t++) {
if (unique) {
}
}
Set<Integer> checkSet = Collections.emptySet();
for (Row row : sheet) {
for (Cell c : row) {
if (range.isInRange(c)) {
int col = c.getColumnIndex() - firstCol;
int val = (int) c.getNumericCellValue();
if (unique) {
checkSet = uniqueCheck.get(col);
}
if (accept.test(val) && !checkSet.contains(val)) {
// If we are checking for unique, add this value to the set
if (unique) {
}
}
}
}
}
return result;
}
}

which assumes you have added the following external dependencies to your project:

<dependency>
<groupId>org.apache.poi</groupId>
<artifactId>poi-ooxml</artifactId>
<version>4.1.0</version>
</dependency>
<dependency>
<groupId>com.github.dpaukov</groupId>
<artifactId>combinatoricslib3</artifactId>
<version>3.3.0</version>
</dependency>
• With duplicate values in columns, I suppose you are talking about the elements found within the columns,e.g., this combination $(1,2,3)$ produced from columns such as $(0,0);(0,1);(0,2)$ or $(0,0);(1,1);(0,2)$. In this case, this is not a concern, since I can save the respective indices which I need in the end. As for the "try-with" I was not aware of it :) Dec 4 '19 at 15:06
• I was referring to the case where you have for example vectors $(1,1,2)$ and $(3,4)$. If you want only unique outputs, you get 4 output rows $(1,3)$, $(1,4)$, $(2,3)$ and $(2,4)$. If you want duplicates you get 6 output rows, because $(1,3)$ and $(1,4)$ are occuring twice. That is what the unique parameter in my answer is used for. Dec 5 '19 at 7:58
• I got it. As mentioned above, at this point the matrix (vector) entities are not that important as long they are $>0$ as the indices of these combinations. Nevertheless, thank you for the note. Dec 5 '19 at 17:22

In the end, I reduced the matrix by using HashMaps and ignoring the 0 entities.

The code needs around 60' to run for a maximum of 2 different row combinations.

I am sure that I can still optimize it, by reducing the iterations when I need at maximum X different row combinations.

The following code, is what I have at this moment.

import org.apache.poi.ss.usermodel.Cell;
import org.apache.poi.ss.usermodel.Row;
import org.apache.poi.xssf.usermodel.XSSFSheet;
import org.apache.poi.xssf.usermodel.XSSFWorkbook;

import java.io.*;
import java.util.*;

public class main {
private static String excelFileName = "Mappe1 v2.xlsx";
private static int startExcelColumnIndex = 1;
private static int endExcelColumnIndex = 11;
private static int startExcelRowIndex = 1;
private static int endExcelRowIndex = 16;
private static ArrayList<String> stringArrayList = new ArrayList<String>();
private static int maxNumberProviders = 2;

private static void combine(HashMap<Integer,HashMap<Integer,Integer>> rowsColumnsMatrixEntitiesHashMapHashMap,
HashMap<Integer,HashMap<Integer,Integer>> columnsRowsMatrixEntitiesHashMapHashMap,
HashMap<Integer,ArrayList<Integer>> columnsRowsIndicesArrayListHashMap) {
/*matrix.length = 16 anzahl der zeilen
* matrix.length = 11 anzahl der spalten*/
int columnsNumber = columnsRowsMatrixEntitiesHashMapHashMap.size();
int sizeArray[] = new int[columnsNumber];
int counterArray[] = new int[columnsNumber];
long total = 1;
total = initializeSizeArraysAndFindIterationsCount(columnsRowsMatrixEntitiesHashMapHashMap,sizeArray,total);
//        total = 1000000;
StringBuilder sb;
String s;
for (long count = total; count > 0; --count) {
/*check the number of different providers, using the counterArray
* this check is not anymore sufficient since not all indices start from the same number*/
boolean combinationAcceptable = combinationAllowedForMaxNumberOfProviders(counterArray);
sb = new StringBuilder();
s = "";
HashSet<Integer> rowIndexInAColumn = new HashSet<Integer>();
if (combinationAcceptable) {
for (Map.Entry<Integer,ArrayList<Integer>> integerArrayListEntry: columnsRowsIndicesArrayListHashMap.entrySet()
) {
int columnI = integerArrayListEntry.getKey();
ArrayList<Integer> columnIndices = integerArrayListEntry.getValue();
int rowIndex = columnIndices.get(counterArray[columnI]);
s = s + "; " + rowIndex +  "," + columnI + "; ";
}
if (rowIndexInAColumn.size() <= maxNumberProviders) {
combinationAcceptable = true;
} else {
combinationAcceptable = false;
}
}
if (combinationAcceptable) {
int tmpi[] = new int[sb.toString().length()];
for (int tmp = 0; tmp < sb.toString().length(); tmp++) {
tmpi[tmp] = Integer.parseInt("" + sb.toString().toCharArray()[tmp]);
}
}
for (int incIndex = columnsNumber - 1; incIndex >= 0; --incIndex) {
if (counterArray[incIndex] + 1 < sizeArray[incIndex]) {
++counterArray[incIndex];
break;
}
counterArray[incIndex] = 0;
}
}
}
public static long initializeSizeArraysAndFindIterationsCount(HashMap<Integer,HashMap<Integer,Integer>> columnsRowsMatrixEntitiesHashMapHashMap,
int sizeArray[], long total) {
for (Map.Entry<Integer,HashMap<Integer,Integer>> integerHashMapEntry: columnsRowsMatrixEntitiesHashMapHashMap.entrySet()
) {
Integer providerColumn = integerHashMapEntry.getKey(); // provider index
HashMap<Integer,Integer> rowMatrixEntityHashMap = integerHashMapEntry.getValue(); // eligibility for attribute of a provider
int numberOfRowsInColumn = rowMatrixEntityHashMap.size();
sizeArray[providerColumn] = numberOfRowsInColumn;
total *= numberOfRowsInColumn; // multiply rows per column -> rows(columns[i])
}
}
public static boolean combinationAllowedForMaxNumberOfProviders(int[] counterArray) {
HashSet<Integer> integerHashSet = new HashSet<>();
for (int i = 0; i < counterArray.length; i++) {
int rowIndex = counterArray[i];
}
if (integerHashSet.size() <= maxNumberProviders) {
return true;
} else {
return false;
}
}
public static void main(String[] args) {
/*int[][] matrix = {{1, 2, 3},
{4, 5, 6},
{7, 8, 9}};*/
int[][] matrix = new int[endExcelRowIndex][endExcelColumnIndex];
HashMap<Integer,HashMap<Integer,Integer>> rowsColumnsMatrixEntitiesHashMapHashMap = new HashMap<Integer, HashMap<Integer, Integer>>();
HashMap<Integer,HashMap<Integer,Integer>> columnsRowsMatrixEntitiesHashMapHashMap = new HashMap<Integer, HashMap<Integer, Integer>>();
HashMap<Integer,ArrayList<Integer>> columnsRowsIndicesArrayListHashMap = new HashMap<Integer,ArrayList<Integer>>();
writeToDataStructures(matrix,rowsColumnsMatrixEntitiesHashMapHashMap,columnsRowsMatrixEntitiesHashMapHashMap,columnsRowsIndicesArrayListHashMap);
System.out.println("matrix.length: " + matrix.length);
System.out.println("matrix.length: " + matrix.length);
constraintProgramming(matrix,rowsColumnsMatrixEntitiesHashMapHashMap,columnsRowsMatrixEntitiesHashMapHashMap,columnsRowsIndicesArrayListHashMap);
//        combine(rowsColumnsMatrixEntitiesHashMapHashMap,columnsRowsMatrixEntitiesHashMapHashMap,columnsRowsIndicesArrayListHashMap);
writeToTXT();
}
public static void constraintProgramming(int[][] matrix, HashMap<Integer,HashMap<Integer,Integer>> rowsColumnsMatrixEntitiesHashMapHashMap,
HashMap<Integer,HashMap<Integer,Integer>> columnsRowsMatrixEntitiesHashMapHashMap,
HashMap<Integer,ArrayList<Integer>> columnsRowsIndicesArrayListHashMap) {

}
public static void writeToDataStructures(int[][] matrix, HashMap<Integer,HashMap<Integer,Integer>> rowsColumnsMatrixEntitiesHashMapHashMap,
HashMap<Integer,HashMap<Integer,Integer>> columnsRowsMatrixEntitiesHashMapHashMap,
HashMap<Integer,ArrayList<Integer>> columnsRowsIndicesArrayListHashMap ) {
// column-wise
for (int i = 0; i < matrix.length; i++) {
HashMap<Integer,Integer> columnsMatrixEntitiesHashMap = new HashMap<Integer, Integer>();
for (int j = 0; j < matrix.length; j++) {
int matrixEntity = matrix[i][j];
if (matrixEntity >0) {
columnsMatrixEntitiesHashMap.put(j,matrixEntity);
}
}
rowsColumnsMatrixEntitiesHashMapHashMap.put(i,columnsMatrixEntitiesHashMap);
}
for (int j = 0; j < matrix.length; j++) {
HashMap<Integer,Integer> rowsMatrixEntitiesHashMap = new HashMap<Integer, Integer>();
ArrayList<Integer> rowIndicesList = new ArrayList<Integer>();
for (int i = 0; i < matrix.length; i++) {
int matrixEntity = matrix[i][j];
if (matrixEntity >0) {
rowsMatrixEntitiesHashMap.put(i,matrixEntity);
}
}
columnsRowsIndicesArrayListHashMap.put(j,rowIndicesList);
columnsRowsMatrixEntitiesHashMapHashMap.put(j,rowsMatrixEntitiesHashMap);
}
}
public static void writeToTXT() {
PrintWriter writer = null;
try {
writer = new PrintWriter("MatrixCombinations.txt", "UTF-8");
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (UnsupportedEncodingException e) {
e.printStackTrace();
}
for (String s: stringArrayList
) {
writer.println(s);
}
writer.close();
}
public static void readXlsx(int[][] matrix) {
File myFile = new File(excelFileName);
FileInputStream fis = null;
try {
fis = new FileInputStream(myFile);
} catch (FileNotFoundException e) {
e.printStackTrace();
System.exit(0);
}
// Finds the workbook instance for XLSX file
XSSFWorkbook myWorkBook = null;
try {
myWorkBook = new XSSFWorkbook(fis);
} catch (IOException e) {
e.printStackTrace();
System.exit(0);
}
XSSFSheet mySheet = myWorkBook.getSheet("Kombinationen");
// Get iterator to all the rows in current sheet
Iterator<Row> rowIterator = mySheet.iterator();
while (rowIterator.hasNext()) {
Row row = rowIterator.next();
if (row.getRowNum() >= startExcelRowIndex && row.getRowNum() <= endExcelRowIndex) {
Iterator<Cell> cellIterator = row.cellIterator();
while (cellIterator.hasNext()) {
Cell cell = cellIterator.next();
if (cell.getColumnIndex() >= startExcelColumnIndex && cell.getColumnIndex() <= endExcelColumnIndex) {
matrix[row.getRowNum()-startExcelRowIndex][cell.getColumnIndex()-startExcelColumnIndex] = (int) cell.getNumericCellValue();
}
}
}
}
}
}