二维数组排序问题之一

最近做项目，遇到一个需求，需要用到下列排列组合方法，于是记下来，将来再遇到此类方法时，直接拿来用。
先设置几个数组
a1,a2,a3,a4    list[0]        长度4
b1,b2,b3        list[1]        长度3
c1,c2             list[2]        长度2
d1,d2,d3         list[3]        长度3
一共有4*3*2*3 = 72种组合（a1b1c1d1算是一种，但是b1a1c1d1等等内容相同，位置不同的不算）
是一个array[72]的数组
array[0] = list[0][0]list[1][0]list[2][0]list[3][0] = a1b1c1d1        1/72
array[1] = list[0][0]list[1][0]list[2][0]list[3][1] = a1b1c1d2        2/72
array[2] = list[0][0]list[1][0]list[2][0]list[3][2] = a1b1c1d3        3/72
array[3] = list[0][0]list[1][0]list[2][1]list[3][0] = a1b1c2d1        4/72
array[4] = list[0][0]list[1][0]list[2][1]list[3][1] = a1b1c2d2        5/72
array[5] = list[0][0]list[1][0]list[2][1]list[3][2] = a1b1c2d3        6/72
......
array[65] = list[0][3]list[1][1]list[2][1]list[3][2] = a4b2c2d3        66/72
array[66] = list[0][3]list[1][2]list[2][0]list[3][0] = a4b3c1d1        67/72
array[67] = list[0][3]list[1][2]list[2][0]list[3][1] = a4b3c1d2        68/72
array[68] = list[0][3]list[1][2]list[2][0]list[3][2] = a4b3c1d3        69/72
array[69] = list[0][3]list[1][2]list[2][1]list[3][0] = a4b3c2d1        70/72
array[70] = list[0][3]list[1][2]list[2][1]list[3][1] = a4b3c2d2        71/72
array[71] = list[0][3]list[1][2]list[2][1]list[3][2] = a4b3c2d3        72/72

找到规律：
array[i] = list[0][i / (3 * 2 * 3) % 4]list[1][i / (2 * 3) % 3]list[2][i / 3 % 2]list[3][i % 3]
或：
array[i] = list[0][i / (72 / 4) % 4]list[1][i / (72 / (4 * 3)) % 3]list[2][i / (72 / (4 * 3 * 2)) % 2]list[3][i /(72 / (4 * 3 * 2 * 3)) % 3]
==========================================================================
下列是一个比较死板的代码（因为数组是预先定义好的）：
       

        String a[] = {"a1", "a2", "a3", "a4"};
        String b[] = {"b1", "b2", "b3"};
        String c[] = {"c1", "c2"};
        String d[] = {"d1", "d2", "d3"};
        int max = a.length * b.length * c.length * d.length;
        for (int i = 0; i < max; i++) {
            String str1 = a[i / (b.length * c.length * d.length) % a.length] + b[i / (c.length * d.length) % b.length] + c[i / (d.length) % c.length] + d[i % d.length];
            System.out.println("第 " + (i + 1) + " 个： " + str1);
        }

 
==========================================================================
再下列是比较灵活的代码，动态的：

        String[][] str = {{"a1", "a2", "a3", "a4"},
                                  {"b1", "b2", "b3"},
                                  {"c1", "c2"},
                                  {"d1", "d2", "d3"}};    //这个str可以换成动态的二维数组，或者list[]
        int max = 1;
        for(int i = 0; i < str.length; i++){
            max *= str[i].length;
        }
        
        for(int i = 0; i < max; i++){
            String s = "";
            int temp = 1;      //注意这个temp的用法。
            for(int j = 0; j < str.length; j++){
                temp *= str[j].length;
                s += str[j][i / (max / temp) % str[j].length];
            }
            System.out.println("第 " + (i + 1) + " 个： " + s);
        }

        System.out.println(max);

 
以上就是二维数组的排列组合方法。我不是数学天才，所以方法是按照正常的逻辑思维推导出来写的，估计肯定有效率极高、超级漂亮的算法，如果哪位仁兄看到我这篇文章，又恰巧知道更为漂亮的算法，希望不吝赐教。大家进步社会才会进步么。呵呵，说多了。

评论

1 楼 ipandao 2010-01-27  

另注：我在你的网易博客有评论上面的代码

我把上面的代码改成PHP的了，不过还是有点不明白，想问你一下，规律是怎么算出来的，

i / (max / temp) % str[j].length <----这段代码是怎么想出来的？

能加你的QQ吗？

我的QQ是：272383090

贴一下PHP版的代码

//二维数组的排列组合方法
$array = array(
        "0" => array("绿色","白色", "黑色"),
        "1" => array("X", "XL"),
        "2" => array("围巾"," PHP")
);

$max = 1;
foreach($array as $val){
    $max *= count($val);
}

$result=array();
for($i = 0; $i < $max; $i++)
{
    $temp = 1; //注意这个temp的用法。
    for($j = 0; $j < count( $array ); $j++)
    {
        $count = count( $array[$j] );
        $temp *= $count;
        $result[$i] .= $array[$j][ $i / ( $max / $temp ) % $count ];
    }
}

print_r($result);