Java中N×N矩阵的所有可能排列 [英] All possible permutations of a NxN matrix in Java

问题描述

我希望使用递归生成矩阵的所有可能排列。 例如，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);
}
}

推荐答案

我的伪方法是：

1. 将矩阵转换为列表
2. 置换列表
3. 对于列表的每个排列，将列表转换回矩阵。

您没有提到矩阵中的所有元素是否都是唯一的。如果不是，则还需要从排列中删除重复列表(需要在2之后、3之前进行筛选。

置换列表：

1. 理解这一点的最简单方法是通过递归。

基本步骤是当您有两个数字时，排列很容易。它是(a，b)和(b，a)

要添加第三个元素，您需要将该元素添加到所有位置 例如置换(c，{(a，b)，(b，a)})={(c，a，b)，(a，c，b)，(a，b，c)， (C，b，a)，(b，c，a)，(b，a，c)}

因此，您的递归将是置换的(a，permutedlist)

对于permutedlist中的每个b，将a添加到列表中的所有可能位置。

这篇关于Java中N×N矩阵的所有可能排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！