我有三个2 * 2矩阵。我需要找到所有可能的序列
从他们。但条件是我不能从一个以上的价值
每个矩阵。假设：matrix1 [] [] = {1,2,3,4} matrix2 [] [] =
{5,6,7,8} matrxi3 [] [] = {9,10,11,12}子集可以是（1,5,9），
（4,5,11），（3,7,12）...等等。但不是（1,2,7）或（4,10,12）。的
条件是，值不能来自同一矩阵。我尝试过了
将2 * 2矩阵的值排列在一维数组中，然后尝试
应用递归解决方案，但找不到合适的条件。这里
是从给定数组中查找常用子集的代码：
class Combination {
static void combinationUtil(int arr[], int data[], int start,
int end, int index, int r)
{
// Current combination is ready to be printed, print it
if (index == r)
{
for (int j=0; j<r; j++)
System.out.print(data[j]+" ");
System.out.println("");
return;
}
for (int i=start; i<=end && end-i+1 >= r-index; i++)
{
data[index] = arr[i];
combinationUtil(arr, data, i+1, end, index+1, r);
}
}
static void printCombination(int arr[], int n, int r)
{
int data[]=new int[r];
combinationUtil(arr, data, 0, n-1, 0, r);
}
/*Driver function to check for above function*/
public static void main (String[] args) {
int arr[] = {1,2,3,4,5,6,7,8,9,10,11,12};
int r = 3;
int n = arr.length;
printCombination(arr, n, r);
}
}
最佳答案
从您的问题来看，找到任何长度的子序列的要求并不十分明确。试试看：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Difficult {
public static void main(String[] argg) {
// inputs: define your matrixes as arrays here
int[][] m1 = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}};
// print input data
System.out.print("input: [");
for (int length = 0; length < m1.length; length++) {
System.out.print(Arrays.toString(m1[length]));
if (length < m1.length - 1) {
System.out.print(",");
}
}
System.out.println("]");
for (int i = 2; i <= m1.length; i++) {
// find and print subsets starts from 2
print(i, findSubsets(i, m1.length), m1);
}
}
static List<List<Integer>> findSubsets(int grade, int base) {
List<List<Integer>> result = new ArrayList<>();
if (grade > base) return result;
int max = base - 1;
int[] counters = new int[grade];
// init counters
for (int i = 0; i < grade; i++) {
counters[i] = i;
}
do {
addSubset(counters, result);
} while (increment(counters, max));
return result;
}
static void addSubset(int[] counters, List<List<Integer>> result) {
List<Integer> subset = new ArrayList<>();
for (int i : counters) {
subset.add(i);
}
result.add(subset);
}
// increment to next combination and check for stop
static boolean increment(int[] counters, int max) {
boolean result = false;
for (int i = counters.length - 1; i >= 0; i--) {
// last counter can be incremented until max
// before last counter until max-1 and so on
int counterMax = max - (counters.length - 1 - i);
if (counters[i] < counterMax) {
counters[i]++;
int counterValue = counters[i];
// reset all following counter after the current, if there are any
for (int j = i + 1; j < counters.length - 1; j++) {
counters[j] = (++counterValue);
}
result = true;
break;
}
}
return result;
}
static void print(int i, List<List<Integer>> sets, int[][] input) {
//print index combinations
System.out.println("index combinations, size " + i + " : " + sets);
//print element combinations
System.out.print("combinations, size " + i + ": [");
for (List<Integer> set : sets) {
int[][] subset = new int[set.size()][];
int count = 0;
for (int index : set) {
subset[count] = input[index];
count++;
}
print(subset);
}
System.out.println("]");
}
static void print(int[][] matrix) {
// initialize position
int[] positions = new int[matrix.length];
for (int i = 0; i < positions.length; i++) {
positions[i] = 0;
}
boolean end;
do {
//print out current matrix position
String combination = "";
for (int i = 0; i < positions.length; i++) {
if (combination.length() != 0) {
combination += ", ";
}
combination += matrix[i][positions[i]];
}
System.out.print("[" + combination + "]");
end = true;
// increment and set end
for (int i = positions.length - 1; i >= 0; i--) {
int value = positions[i];
if (value < matrix[i].length - 1) {
positions[i]++;
// reset position in every following row (if there is any) to zero
for (int j = i + 1; j < positions.length; j++) {
positions[j] = 0;
}
end = false;
break;
}
}
if (!end) {
System.out.print(",");
}
} while (!end);
}
}
该代码能够从给定的输入中找到每种可能长度的组合。它产生以下输出：
input: [[1, 2, 3, 4],[5, 6, 7, 8],[9, 10, 11, 12]]
index combinations, size 2 : [[0, 1], [0, 2], [1, 2]]
combinations, size 2: [[1, 5],[1, 6],[1, 7],[1, 8],[2, 5],[2, 6],[2, 7],[2, 8],[3, 5],[3, 6],[3, 7],[3, 8],[4, 5],[4, 6],[4, 7],[4, 8][1, 9],[1, 10],[1, 11],[1, 12],[2, 9],[2, 10],[2, 11],[2, 12],[3, 9],[3, 10],[3, 11],[3, 12],[4, 9],[4, 10],[4, 11],[4, 12][5, 9],[5, 10],[5, 11],[5, 12],[6, 9],[6, 10],[6, 11],[6, 12],[7, 9],[7, 10],[7, 11],[7, 12],[8, 9],[8, 10],[8, 11],[8, 12]]
index combinations, size 3 : [[0, 1, 2]]
combinations, size 3: [[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]]
关于java - 如何使用来自多个不同矩阵的值查找子序列？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/60420303/