java - 如何使用多个不同矩阵中的值查找子序列？

Question

I have three 2*2 matrices. I need to find all the possible sequences from them. But the condition is I cannot take more than one value from each of the matrices. Suppose: matrix1[][]= {1,2,3,4} matrix2[][]= {5,6,7,8} matrxi3[][]= {9,10,11,12} the subsets can be (1,5,9), (4,5,11), (3,7,12)...and so on. But not (1,2,7) or (4,10,12). The condition is, value cannot come from the same matrix. I tried to arrange the values of the 2*2 matrices in a 1-D array and then tried to apply recursive solution but cannot find the proper condition. Here is the code to find usual subsets from a given array:

   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); 
        } 
    } 

Answer 1

您的问题并不清楚查找任意长度的子序列的要求。试试这个:

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]]