Home > 算法研究 > 求二维数组的全排列组合,二位数组的自乘积问题

求二维数组的全排列组合,二位数组的自乘积问题

CG在ETP基地的培训也有一段时间了,这期间也有几次考试,下面将要分享的是最近一次笔试的考试题目,该题算是JAVA考试的附加题,要求也很简单,下面是原题

二维数组的长度和初始值均由输入确定,如何求出此数组的全排列组合,
即:int a[X][X] = {{X,X,X},…}如下
int a[3][3] = {{1,2,3},{4,5,6},{7,8,9}}
或者是 int a[4][4] = {{1,2,3,4},{4,5,6,7},{7,8,9,10}}
计算a[3][3]的结果如下:
147,148,149
157,158,159
167,168,169
247,248,249
…………


解决思路:
根据本题的算法复杂度可知3*3的二维数组可以有 3^3 = 27中输出结果,而利用这个结果进行不同的%和/运算,可以得到以下的周期变化的规律
//总输出结果数
int it = (int) Math.pow((a[0].length),(a.length)) -1;
//产生0-a[0].length周期为1变化规律
//以3为例:210210210210…..
it % a[0].length;
//产生0-a[0].length周期为a[0].length变化规律
//以3为例:222111000222111000
(it / a[0].length) % a[0].length;
//产生0-a[0].length周期为a[0].length * a[0].length变化规律
//以3为例:2222222221111111110000…
(it / a[0].length) / a[0].length % a[0].length;
以上规律则满足我们所需要的数组下标表示

JAVA代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/*
*求二维数组的全排列组合
*by CG
*/
public static void main(String[] args) {
 //测试数组
 int a[][] = {{1 , 2 , 3 },{4 , 5 , 6 },{7 , 8 , 9}};
 String s;
 //总循环次数,控制循环量
 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;
  //临时变量,保存迭代器
  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
Categories: 算法研究 Tags: ,
  1. iris
    May 18th, 2013 at 21:35 | #1

    楼主,你这段代码有局限性啊。如果数字是10以上就不行了。如果数字是10以下,我们可以同过s[i]-‘0’得到相应的数字,如果是10以上就不行了啊,能改进吗?还有,你得到的全排列是无序的,很多时候我们想要的是有序的全排列,如果数字小于10,可以同过快排,数字大于10了就不行啊。

  2. CG
    May 18th, 2013 at 22:06 | #2

    本题的算法利用的是数组下标的运算规律来计算的,因此与数组本身的存储内容无关,字符,数字,甚至汉字都是可以的,但是两位以上数字计算时建议楼上使用char型转换,转换后即可计算和排序了。

  3. iris
    June 1st, 2013 at 10:52 | #3

    我懂了,开始没转过弯来~

  1. No trackbacks yet.