Все возможные перестановки матрицы NxN в Java

Question

Я хочу сгенерировать все возможные перестановки матрицы с помощью рекурсии. Например, матрица 2x2 будет иметь 24 возможности.

1 2 1 2 1 3 1 4 
3 4, 4 3, 2 4, 2 3....24 possibilities. 

Вот мой код. Логика выглядит прекрасно, но я могу получить только четыре разные возможности. Надеюсь, кто-то может помочь мне в этом.

public class NewClass 
{ 
public static int LENGTH=2,count=0; 

public static int check_if_array_is_fully_filled(int[][] a) 
{ 
    for(int i=0;i<a.length;i++) 
    { 
     for(int j=0;j<a.length;j++) 
     { 
      if(a[i][j]==0) 
      { 
       return 0; 
      } 
     } 
    } 
    return 1; 
} 

public static int[][] initialize_all_zeros(int[][] a) 
{ 
    for(int i=0;i<a.length;i++) 
    { 
     for(int j=0;j<a.length;j++) 
     { 
      a[i][j]=0; 
     } 
    } 
    return a; 
} 
public static void display(int[][] a) 
{ 
    for(int i=0;i<a.length;i++) 
    { 
     for(int j=0;j<a.length;j++) 
     { 
      System.out.print(a[i][j] + " "); 
     } 
     System.out.println(); 
    } 
    System.out.println("********"); 
    count++; 
} 

public static void generate(int[][] a, int value_to_enter, int done) 
{   
    if(done == 0) 
    { 
     for(int i=0;i<a.length;i++) 
     { 
      for(int j=0;j<a.length;j++) 
      { 
       if(a[i][j] == 0) 
       { 
        a[i][j]=value_to_enter; 
        value_to_enter++; 
        int v = check_if_array_is_fully_filled(a); 
        if(v == 1) 
        { 
         done = 1; 
        } 
        else 
        { 
         generate(a,value_to_enter,0); 
        }       
       } 
      } 
     }       
    } 
    if(done == 1) 
    { 
     display(a); 
    } 
} 
public static void main(String[] agrs) 
{ 
    int[][] a; 
    for(int i=0;i<LENGTH;i++) 
    { 
     for(int j=0;j<LENGTH;j++) 
     { 
      a = new int[LENGTH][LENGTH]; 
      a = initialize_all_zeros(a); 
      a[i][j]=1; 
      generate(a,2,0); 
     } 
    } 
    System.out.println(count); 
} 
} 

Answer 1

Вот рекурсивная функция для 1d массива, использующая ту же логику, что и вы. 2d более или менее одно и то же.

private static void generate(int[] values, int currentValue) { 
    if (currentValue == values.length + 1) { 
     System.out.println(Arrays.toString(values)); 
     return; 
    } 
    for (int i = 0; i < values.length; i++) { 
     if (values[i] == 0) { 
      values[i] = currentValue; 
      generate(values, currentValue + 1); 
      values[i] = 0; 
     } 
    } 
} 

вызовов следующим образом:

generate(new int[3], 1); 

Выходы

[1, 2, 3] 
[1, 3, 2] 
[2, 1, 3] 
[3, 1, 2] 
[2, 3, 1] 
[3, 2, 1] 

Какой должна быть заключена в

public static void generate(int size) { 
    generate(new int[size], 1); 
} 

Answer 2

Мой псевдо подход будет:

1. преобразования матрицы в список
2. список переставлять
3. для каждой перестановки списка, преобразовать список обратно в матрицу.

Вы не указали, что все элементы в вашей матрице уникальны. Если их нет, то вам нужно удалить дубликаты списки из вашей перестановки а (нужно фильтровать через 2 до 3.

список переставлять:

1. Самый простой способ понять это рекурсией.

базовый шаг, когда у вас есть два числа, перестановки легко. это (а, Ь) и (Ь, а)

чтобы добавить третий элемент, будет добавлен элемент все позиции eg permute (c, {(a, b), (b, a)}) = {(c, a, b), (a, c, b), (a, b, c), (c, b, a), (b, с, а), (Ь, а, с)}

так, то рекурсия будет переставлять (а, permutedlist)

для каждого б в permutedlist, добавить на все возможные позиции в списке.