从矩阵中找出长度为 N 的组合,每个元素需要来自不同的 row/column
Find the combinations of length N from a matrix, each element need to be from different row/column
在一个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);
}
}
}
}
你的方法太复杂了。
这个问题基本上也可以这样表述:
找出 [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*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);
}
}
}
}
你的方法太复杂了。
这个问题基本上也可以这样表述:
找出 [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