从矩阵中找出长度为 N 的组合，每个元素需要来自不同的 row/column

Question

在一个n*n的矩阵中，找出所有长度为n的组合，使得组合中的每个元素都来自不同的列和不同的行。

For 2*2 Matrix
00 01
10 10
The possible combinations are (00,10) and (10,01)

For 3*3 Matrix
00 01 02
10 11 12
20 21 22
The possible combinations are (00,11,22) (00,12,21) (10,01,22) (10,02,21) (20,01,12) (20,02,11)

我在java中写了下面的代码。该程序创建所有长度为 n 的组合。

对于2*2矩阵的程序returns所有长度为2的组合。即4*4=16种组合
[[0, 0], [0, 1], [0, 10], [0, 11], [1, 0], [1, 1], [1, 10], [1, 11], [ 10, 0], [10, 1], [10, 10], [10, 11], [11, 0], [11, 1], [11, 10], [11, 11]]

我想修改这个程序，只返回满足上述属性的组合。

我已经尝试对 for 循环进行多种修改（如下所示）。但其中 none 有效。

for (int j = 0; j < lengOfComb; j++)

注意：传递给函数 findCombinations 的参数 i,j 是多余的。
我将此 article 引用到代码中。

import java.util.ArrayList;

public class MatrixCombinations {

    public static void main(String args[]) {
        int n = 4;
        int[][] multi = new int[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                multi[i][j] = i * 10 + j;
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(multi[i][j] + " ");
            }
            System.out.println();
        }

        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> current = new ArrayList<Integer>();
        findCombinations(multi, result, current, 0, 0, 0);
        System.out.println(result);
        System.out.println("The lenght of the result array is " + result.size());

    }

    public static void findCombinations(int[][] input, ArrayList<ArrayList<Integer>> result, ArrayList<Integer> current,
            int lengOfComb, int m, int n) {
        int size = input.length;

        if (lengOfComb == size) {
            ArrayList<Integer> temp = new ArrayList<Integer>(current);
            result.add(temp);
            return;
        }

        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                current.add(input[i][j]);
                findCombinations(input, result, current, lengOfComb + 1, i, j);
                current.remove(current.size() - 1);
            }
        }
    }

}

Answer 1

你的方法太复杂了。
这个问题基本上也可以这样表述：
找出 [0 , n) 范围内所有长度为 n 的数字排列。然后可以通过将范围为 [0 , n) 的排列组合成一组对，将这些排列转换为搜索到的组合，这些排列可以用作矩阵中的索引：

int[] permutation = generatePermutation(int n);
int[] combination = new int[n];

for(int i = 0 ; i < n ; i++)
    combination[i] = matrix[i][permutation[i]];

基本上您需要做的就是生成 [0 , n) 中数字的所有排列并应用上述算法来查找排列：

编辑：对于不正确的 permutation-generator，我感到抱歉，当我发布这篇文章时，我有点心不在焉而且很匆忙。这是使用 Steinhaus-Johnson-Trotter-Algorithm:

的正确生成器

void generatePermutations(List<Integer> permutation , int n){
    if(n == -1){
        for(int i = 0 ; i < permutation.size() ; i++)
            System.out.print(matrix[i][permutation.get(i)]);
        System.out.println();
    }else{
        for(int i = 0 ; i <= permutation.size() ; i++){
            permutation.add(i , n);
            generatePermutations(permutation , n - 1);
            permutation.remove(i);
        }
    }
}

A test-run 这个矩阵：

matrix = new String[][]{
    {"a1" , "b1" , "c1"} ,
    {"a2" , "b2" , "c2"} ,
    {"a3" , "b3" , "c3"}
};

产生这个输出：

a1b2c3
b1a2c3
b1c2a3
a1c2b3
c1a2b3
c1b2a3

从矩阵中找出长度为 N 的组合，每个元素需要来自不同的 row/column

Find the combinations of length N from a matrix, each element need to be from different row/column

java

algorithm

backtracking