Javaの行列からすべての組み合わせを返します

Question

私はこの質問のさまざまなバージョンを見てきましたが、決して良い答えはありません。私はMXN配列を持ち、Mサイズのすべての可能な組み合わせを返したいと思います。例をあげましょう.3X3の配列があります。結果は27通りあります。私はここで再帰的な方法を試みていますが、今まで運がありませんでした。

Answer 1

このプログラムでお手伝いしてください。私はこの行列を使用しました

int[][] matrix = {{1, 2, 3}, 
       {4, 5, 6}, 
       {7, 8, 9}}; 

出力は以下のように27通りあります。

import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.List; 

public class Main { 
    private static List<int[]> combine(int[][] matrix) { 
     int sizeArray[] = new int[matrix.length]; 
     int counterArray[] = new int[matrix.length]; 
     int total = 1; 
     for (int i = 0; i < matrix.length; ++i) { 
      sizeArray[i] = matrix[i].length; 
      total *= matrix[i].length; 
     } 
     List<int[]> list = new ArrayList<>(total); 
     StringBuilder sb; 
     for (int count = total; count > 0; --count) { 
      sb = new StringBuilder(); 
      for (int i = 0; i < matrix.length; ++i) { 
       sb.append(matrix[i][counterArray[i]]); 
      } 
      int tmpi[] = new int[sb.toString().length()]; 
      for (int tmp = 0; tmp < sb.toString().length(); tmp++) { 
       tmpi[tmp] = Integer.parseInt("" + sb.toString().toCharArray()[tmp]); 
      } 
      list.add(tmpi); 
      for (int incIndex = matrix.length - 1; incIndex >= 0; --incIndex) { 
       if (counterArray[incIndex] + 1 < sizeArray[incIndex]) { 
        ++counterArray[incIndex]; 
        break; 
       } 
       counterArray[incIndex] = 0; 
      } 
     } 
     return list; 
    } 

    public static void main(String[] args) { 
     int[][] matrix = {{1, 2, 3}, 
       {4, 5, 6}, 
       {7, 8, 9}}; 
     int i = 0; 
     for (int[] c : (combine(matrix))) { 
      System.out.println(Arrays.toString(c)); 
      i++; 
     } 
     System.out.println(i); 
    } 
} 

テスト

[1, 4, 7] 
[1, 4, 8] 
[1, 4, 9] 
[1, 5, 7] 
[1, 5, 8] 
[1, 5, 9] 
[1, 6, 7] 
[1, 6, 8] 
[1, 6, 9] 
[2, 4, 7] 
[2, 4, 8] 
[2, 4, 9] 
[2, 5, 7] 
[2, 5, 8] 
[2, 5, 9] 
[2, 6, 7] 
[2, 6, 8] 
[2, 6, 9] 
[3, 4, 7] 
[3, 4, 8] 
[3, 4, 9] 
[3, 5, 7] 
[3, 5, 8] 
[3, 5, 9] 
[3, 6, 7] 
[3, 6, 8] 
[3, 6, 9] 
27 

Answer 2

再帰バージョン：

import java.util.Arrays; 

public class Matrix { 
    private static int counter = 0; 

    private static void combin2(int depth, int[][]matrix, int[] output) 
    { 
     int[] row = matrix[depth]; 

     if(depth == 0) { 
      counter = 0; 
      output = new int[matrix.length]; 
      System.out.println("matrix length: " + matrix.length); 
     } 

     for(int i=0; i<row.length; i++) { 
      output[depth] = row[i]; 

      if(depth == (matrix.length-1)) { 
       //print the combination 
       System.out.println(Arrays.toString(output)); 
       counter++; 
      } else { 
       //recursively generate the combination 
       combin2(depth+1, matrix, output); 
      } 
     } 
    } 

    public static void main(String[] args) { 
     int[][] matrix = new int[][] {{1, 2, 3, 4}, {5, 6, 7, 8}}; 
     combin2(0, matrix, null); 
     System.out.println("counter = " + counter); 
     System.out.println(""); 

     matrix = new int[][]{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}; 
     combin2(0, matrix, null); 
     System.out.println("counter = " + counter); 
     System.out.println(""); 

     matrix = new int[][]{{1, 2, 3}, {4,5,6}, {7,8,9}, {10,11,12}}; 
     combin2(0, matrix, null); 
     System.out.println("counter = " + counter); 
     System.out.println(""); 
    } 
} 

出力：

matrix length: 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] 
counter = 16 

matrix length: 3 
[1, 4, 7] 
[1, 4, 8] 
[1, 4, 9] 
[1, 5, 7] 
[1, 5, 8] 
[1, 5, 9] 
[1, 6, 7] 
[1, 6, 8] 
[1, 6, 9] 
[2, 4, 7] 
[2, 4, 8] 
[2, 4, 9] 
[2, 5, 7] 
[2, 5, 8] 
[2, 5, 9] 
[2, 6, 7] 
[2, 6, 8] 
[2, 6, 9] 
[3, 4, 7] 
[3, 4, 8] 
[3, 4, 9] 
[3, 5, 7] 
[3, 5, 8] 
[3, 5, 9] 
[3, 6, 7] 
[3, 6, 8] 
[3, 6, 9] 
counter = 27 

matrix length: 4 
[1, 4, 7, 10] 
[1, 4, 7, 11] 
[1, 4, 7, 12] 
[1, 4, 8, 10] 
[1, 4, 8, 11] 
[1, 4, 8, 12] 
[1, 4, 9, 10] 
[1, 4, 9, 11] 
[1, 4, 9, 12] 
[1, 5, 7, 10] 
[1, 5, 7, 11] 
[1, 5, 7, 12] 
[1, 5, 8, 10] 
[1, 5, 8, 11] 
[1, 5, 8, 12] 
[1, 5, 9, 10] 
[1, 5, 9, 11] 
[1, 5, 9, 12] 
[1, 6, 7, 10] 
[1, 6, 7, 11] 
[1, 6, 7, 12] 
[1, 6, 8, 10] 
[1, 6, 8, 11] 
[1, 6, 8, 12] 
[1, 6, 9, 10] 
[1, 6, 9, 11] 
[1, 6, 9, 12] 
[2, 4, 7, 10] 
[2, 4, 7, 11] 
[2, 4, 7, 12] 
[2, 4, 8, 10] 
[2, 4, 8, 11] 
[2, 4, 8, 12] 
[2, 4, 9, 10] 
[2, 4, 9, 11] 
[2, 4, 9, 12] 
[2, 5, 7, 10] 
[2, 5, 7, 11] 
[2, 5, 7, 12] 
[2, 5, 8, 10] 
[2, 5, 8, 11] 
[2, 5, 8, 12] 
[2, 5, 9, 10] 
[2, 5, 9, 11] 
[2, 5, 9, 12] 
[2, 6, 7, 10] 
[2, 6, 7, 11] 
[2, 6, 7, 12] 
[2, 6, 8, 10] 
[2, 6, 8, 11] 
[2, 6, 8, 12] 
[2, 6, 9, 10] 
[2, 6, 9, 11] 
[2, 6, 9, 12] 
[3, 4, 7, 10] 
[3, 4, 7, 11] 
[3, 4, 7, 12] 
[3, 4, 8, 10] 
[3, 4, 8, 11] 
[3, 4, 8, 12] 
[3, 4, 9, 10] 
[3, 4, 9, 11] 
[3, 4, 9, 12] 
[3, 5, 7, 10] 
[3, 5, 7, 11] 
[3, 5, 7, 12] 
[3, 5, 8, 10] 
[3, 5, 8, 11] 
[3, 5, 8, 12] 
[3, 5, 9, 10] 
[3, 5, 9, 11] 
[3, 5, 9, 12] 
[3, 6, 7, 10] 
[3, 6, 7, 11] 
[3, 6, 7, 12] 
[3, 6, 8, 10] 
[3, 6, 8, 11] 
[3, 6, 8, 12] 
[3, 6, 9, 10] 
[3, 6, 9, 11] 
[3, 6, 9, 12] 
counter = 81