brute force with backtracking
hi guys. this is my first post here and i really need help.
i have a vector of vectors with variable length in the 2 dimensions and i wanna get all possible combinations. let me explain with an example:
0123 (columns count)
1524
3152
2 61
47
so if i have a vector of 4 columns(elements) and each column have a variable number of integers.(1st column =4, 2nd=2, 3rd=3, 4th=4)
so i should have all combinations ex:
1,5,2,4
1,5,2,2
1,5,2,1
1,5,2,7
1,5,5,4
1,5,5,2
and so on
until i get all possible combinations. is there an algorithm in java that does that ?
[660 byte] By [
thetrutha] at [2007-10-2 16:12:22]
Interesting problem.. ....
Here's my attempt.. I didnt use backtracking tree algorithm,
rather, just an array to keep track of current row.
Here's the output of the program and the code below it.
Cheers,
Ajay
Input Array --
1 3 2 4
5 1 6 7
2 5 1
4 2
Combinations--
1 3 2 4
1 3 2 7
1 3 6 4
1 3 6 7
1 3 1 4
1 3 1 7
1 1 2 4
1 1 2 7
1 1 6 4
1 1 6 7
1 1 1 4
1 1 1 7
1 5 2 4
1 5 2 7
1 5 6 4
1 5 6 7
1 5 1 4
1 5 1 7
1 2 2 4
1 2 2 7
1 2 6 4
1 2 6 7
1 2 1 4
1 2 1 7
5 3 2 4
5 3 2 7
5 3 6 4
5 3 6 7
5 3 1 4
5 3 1 7
5 1 2 4
5 1 2 7
5 1 6 4
5 1 6 7
5 1 1 4
5 1 1 7
5 5 2 4
5 5 2 7
5 5 6 4
5 5 6 7
5 5 1 4
5 5 1 7
5 2 2 4
5 2 2 7
5 2 6 4
5 2 6 7
5 2 1 4
5 2 1 7
2 3 2 4
2 3 2 7
2 3 6 4
2 3 6 7
2 3 1 4
2 3 1 7
2 1 2 4
2 1 2 7
2 1 6 4
2 1 6 7
2 1 1 4
2 1 1 7
2 5 2 4
2 5 2 7
2 5 6 4
2 5 6 7
2 5 1 4
2 5 1 7
2 2 2 4
2 2 2 7
2 2 6 4
2 2 6 7
2 2 1 4
2 2 1 7
4 3 2 4
4 3 2 7
4 3 6 4
4 3 6 7
4 3 1 4
4 3 1 7
4 1 2 4
4 1 2 7
4 1 6 4
4 1 6 7
4 1 1 4
4 1 1 7
4 5 2 4
4 5 2 7
4 5 6 4
4 5 6 7
4 5 1 4
4 5 1 7
4 2 2 4
4 2 2 7
4 2 6 4
4 2 6 7
4 2 1 4
4 2 1 7
public class Combinations {
public static void main(String [] args) {
int[][] inputArray = { {1, 3, 2, 4}, {5, 1, 6, 7}, {2, 5, 1}, {4, 2}};
System.out.println("Input Array -- ");
for (int i=0; i<inputArray.length; i++) {
for (int j=0; j><inputArray[i].length; j++) {
System.out.print(inputArray[i][j] + " ");
}
System.out.println();
}
int[][] combinations = getCombinations(inputArray);
System.out.println("Combinations-- ");
for (int i=0; i><combinations.length; i++) {
for (int j=0; j><combinations[i].length; j++) {
System.out.print(combinations[i][j] + " ");
}
System.out.println();
}
}
public static int[][] getCombinations(int[][] inputArray) {
int max_outCols= inputArray.length;
int max_outRows= 1;
for (int i=0; i><inputArray.length; i++) {
max_outRows= max_outRows * inputArray[i].length;
}
int [][] combinations = new int[max_outRows][max_outCols];
// The rowIndices array stores the current row for each column.
int [] rowIndices = new int[max_outCols];
for (int i=0; i><rowIndices.length; i++) {
rowIndices[i] = 0; // initialize
}
int output_row = 0;
while (output_row >< max_outRows) {
for (int j=0; j<max_outCols; j++) {
combinations[output_row][j] = inputArray[rowIndices[j]][j];
}
output_row++;
incrementRowIndices(inputArray, rowIndices);
}
return combinations;
}
private static void incrementRowIndices(int[][] inputArray, int [] rowIndices) {
for (int i=rowIndices.length-1; i>=0; i--) {
rowIndices[i]++;
if (rowIndices[i] == inputArray[i].length) {
rowIndices[i] = 0;
} else {
break;
}
}
}
}
