title: "Finding the Permutations and Combinations of a Two-Dimensional Array, and the Self-Product of the Array"
date: "2012-06-14"
categories:
- "algorithms"
tags: - "ccplusplus"
- "java"
CG has been training at the ETP base for some time now, and during this period there have been several exams. The following is the recent written exam question that will be shared. This question is considered an additional question for the JAVA exam, and the requirements are quite simple. The original question is as follows:
The length and initial values of a two-dimensional array are determined by the input. How to find all the permutations and combinations of this array,
i.e.: int a[X][X] = {{X,X,X},...} as follows
int a[3][3] = {{1,2,3},{4,5,6},{7,8,9}}
or int a[4][4] = {{1,2,3,4},{4,5,6,7},{7,8,9,10}}
Calculate the result of a[3][3] as follows:
147,148,149
157,158,159
167,168,169
247,248,249
............
Solution approach:
Based on the algorithm complexity of this question, we know that a 3*3 two-dimensional array can have 3^3 = 27 different output results. By using these results with different % and / operations, we can obtain the following cyclic patterns:
//Total number of output results
int it = (int) Math.pow((a[0].length),(a.length)) -1;
//Generate a cyclic pattern with a period of 0-a[0].length
//Using 3 as an example: 210210210210.....
it % a[0].length;
//Generate a cyclic pattern with a period of 0-a[0].length * a[0].length
//Using 3 as an example: 222111000222111000
(it / a[0].length) % a[0].length;
//Generate a cyclic pattern with a period of 0-a[0].length * a[0].length * a[0].length
//Using 3 as an example: 2222222221111111110000...
(it / a[0].length) / a[0].length % a[0].length;
These patterns satisfy the array index representation that we need.
The JAVA code is as follows:
/*
*Finding the permutations and combinations of a two-dimensional array
*by CG
*/
public static void main(String[] args) {
//Test array
int a[][] = {{1 , 2 , 3 },{4 , 5 , 6 },{7 , 8 , 9}};
String s;
//Total number of iterations, controls the loop
int it = (int) Math.pow((a[0].length),(a.length)) -1;
while(it >= 0){
s = "";
//it % a[0].length;
//(it / a[0].length) % a[0].length;
//(it / a[0].length) / a[0].length % a[0].length;
//Temporary variable to store the iterator
int temp = it;
for(int m = 0 ; m < a.length ; m++){
if(temp / a[0].length >= 0) {
s += a[m][temp % a[0].length];
temp /= a[0].length;
}
}
System.out.println(s);
it--;
}//while
}//main