矩阵组合排列，算法问题

Question

public static void main(String[] args) {
// TODO Auto-generated method stub
int[][] arr = { { 1, 3, 5, 7, 9, 10 },
{ 1, 4, 8, 10 },
{ 1, 5, 10 }};
for(int i = 0; i < arr[0].length; i++){
for(int j = 0; j < arr[1].length; j++){
for(int k = 0; k < arr[2].length; k++){
System.out.print("["+arr[0][i]+","+arr[1][j]+","+arr[2][k]+"]");
}
System.out.println();
}
System.out.println();
}
}
结果：[1,1,1][1,1,5][1,1,10]
[1,4,1][1,4,5][1,4,10]
[1,8,1][1,8,5][1,8,10]
[1,10,1][1,10,5][1,10,10][3,1,1][3,1,5][3,1,10]
[3,4,1][3,4,5][3,4,10]
[3,8,1][3,8,5][3,8,10]
[3,10,1][3,10,5][3,10,10][5,1,1][5,1,5][5,1,10]
[5,4,1][5,4,5][5,4,10]
[5,8,1][5,8,5][5,8,10]
[5,10,1][5,10,5][5,10,10][7,1,1][7,1,5][7,1,10]
[7,4,1][7,4,5][7,4,10]
[7,8,1][7,8,5][7,8,10]
[7,10,1][7,10,5][7,10,10][9,1,1][9,1,5][9,1,10]
[9,4,1][9,4,5][9,4,10]
[9,8,1][9,8,5][9,8,10]
[9,10,1][9,10,5][9,10,10][10,1,1][10,1,5][10,1,10]
[10,4,1][10,4,5][10,4,10]
[10,8,1][10,8,5][10,8,10]
[10,10,1][10,10,5][10,10,10]

Answer 1

public static void main(String[] args) {
int[] arr1 = { 1, 3, 5, 7, 8, 9 };
int[] arr2 = { 1, 2, 3, 4, 5 };
int[] arr3 = { 1, 3, 5, 6 };
int[] arr4 = { 1, 5, 7 };
List<int[]> list = new ArrayList<int[]>();
list.add(arr1);
list.add(arr2);
list.add(arr3);
list.add(arr4);
System.out.println("begin");
test(list, 0, "");
System.out.println("end");
} public static void test(List<int[]> list, int index, String str) {
// 迭代list
for (int i = 0; i < list.size(); i++) {
// 取得当前的数组
if (i == index) {
// 迭代数组
for (int st : list.get(i)) {
String temp = "";
temp = str + "," + st;
if (i < list.size() - 1) {
test(list, i + 1, temp);
} else /*if (i == list.size() - 1)*/ {
System.out.println(temp.substring(1));
}
}
}
}
}

Answer 2

简化了下5楼的代码，并提供另一种递归方式：
import java.util.Arrays;public class RecursivePermutation {    public static void main(String[] args) {
        int[][] arr = { { 1, 3, 5, 7, 9 }, { 2, 4, 6 }, { 8, 0 } };
        permutation(arr, 0, ""); // 第一次执行时需要额外指定两个固化参数
        permutation(arr); // 第一次执行时比较简单
    }    /**
     * 递归，以字符串来传递递归前缀
     * @param arr 原始数组
     * @param pos 当前递归位置
     * @param prefix 已递归前缀
     */
    public static void permutation(int[][] arr, int pos, String prefix) {
        if (pos < arr.length) {
            for (int i = 0; i < arr[pos].length; i++) {
                permutation(arr, pos + 1, prefix + arr[pos][i] + ",");
            }
        } else {
            System.out.println(prefix.substring(0, prefix.length() - 1));
        }
    }    /**
     * 递归，以数组来传递完整递归信息
     * @param arr 原始数组
     * @param pos 递归信息
     */
    public static void permutation(int[][] arr, int... pos) {
        if (pos.length < arr.length) {
            int[] newPos = Arrays.copyOf(pos, pos.length + 1);
            for (int i = 0; i < arr[pos.length].length; i++) {
                newPos[pos.length] = i;
                permutation(arr, newPos);
            }
        } else {
            for (int i = 0; i < pos.length; i++) {
                System.out.print(arr[i][pos[i]] + " ");
            }
            System.out.println();
        }
    }
}

Answer 3

排列顺序有要求吗？比如 int[][] arr={{1,2,3},{4,5},{6,7}};
拿出来的1,4,6 需要再重新排列组合出4,1,6、4,6,1这样的吗？

Answer 4

其实大家想复杂了void permutation(int **a, int x, int y)
{
    int total;
    int *info = (int *)malloc(sizeof(int) * x);
    int i, j;    total = y;
    for (i = 1; i < x; i++)
    {
        total *= y;
    }
    i = 0;
    
    for (i = 0; i < total; i++)
    {
        int val = i;
        for (j = x - 1; j >= 0; j--)
        {
            info[j] = val % y;
            val = val / y;
        }        for (j = 0; j < x; j++)
        {
            printf("%d, ", a[j * y + info[j]]);
        }
        printf("\n");
    }
    
    free(info);
}int main()
{
    int A[3][4] = { {1, 2, 3, 4},
                {5, 6, 7, 8},
                {9, 10, 11, 12} };    permutation((int **)A, 3, 4);    return 0;
}输出
1, 5, 9,
1, 5, 10,
1, 5, 11,
1, 5, 12,
1, 6, 9,
1, 6, 10,
1, 6, 11,
1, 6, 12,
1, 7, 9,
1, 7, 10,
1, 7, 11,
1, 7, 12,
1, 8, 9,
1, 8, 10,
1, 8, 11,
1, 8, 12,
2, 5, 9,
2, 5, 10,
2, 5, 11,
2, 5, 12,
2, 6, 9,
2, 6, 10,
2, 6, 11,
2, 6, 12,
2, 7, 9,
2, 7, 10,
2, 7, 11,
2, 7, 12,
2, 8, 9,
2, 8, 10,
2, 8, 11,
2, 8, 12,
3, 5, 9,
3, 5, 10,
3, 5, 11,
3, 5, 12,
3, 6, 9,
3, 6, 10,
3, 6, 11,
3, 6, 12,
3, 7, 9,
3, 7, 10,
3, 7, 11,
3, 7, 12,
3, 8, 9,
3, 8, 10,
3, 8, 11,
3, 8, 12,
4, 5, 9,
4, 5, 10,
4, 5, 11,
4, 5, 12,
4, 6, 9,
4, 6, 10,
4, 6, 11,
4, 6, 12,
4, 7, 9,
4, 7, 10,
4, 7, 11,
4, 7, 12,
4, 8, 9,
4, 8, 10,
4, 8, 11,
4, 8, 12,

Answer 5

应该没那么复杂吧
var  z=1;
var a = [[1, 2, 3], [4, 5], [6, 7]];
var total = 1;
//总数:公倍数
for (var i = 0; i < a.length; i++) {
    total *= a[i].length;
}var info = [];
//初始化
for (var i = 0; i < total; i++) {
    info.push('');
}
//生成
for (var j = a.length - 1; j >= 0; j--) {
    var v = a[j].length;
    
    for (var i = 0; i < total; i++) {
        var y =Math.floor(i/z) % v;
        info[i] =a[j][y] + "|" + info[i];
    }
    z *= v;
}
console.log(info);[code=javascript][/code]