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