查找矩阵中所有可能的唯一数组
当给定一个方阵时,在不使用每个数组中任何行/列中的多个元素的情况下找到其中所有可能数组的最佳方法是什么?
例如,在这样的矩阵中:
0 2 3
1 2 3
1 2 0
然后它将像这样遍历它:
然后它将输出以下数组列表:
123
123
023
123
120
020
When given a square matrix, what would be the best way to find all of the possible arrays within it without using more than one element from any row/column in each array?
For example, in a matrix like so:
0 2 3
1 2 3
1 2 0
It would then go through it like this:
And then it would output the following list of arrays:
123
123
023
123
120
020
您可以直接将每个此类数组映射到数字排列 (0 .. size-1)。为了向您展示其工作原理,排列
(2,1,0)
映射到 3 个坐标(2,0), (1,1), (0,2).您给出的 6 个示例是
为了解释映射,让我们采用第一个排列
(2,1,0) --> (2,0)、(1,1)、(0,2)
。那么,你想要使用的值是 array[2][0], array[1][1], array[0][2]所以现在的问题是如何生成每个排列。有几种算法,其中一种是用 java 实现的: http://www.merriampark.com/烫发.htm
You can directly map each such array to a permutation of the digits (0 .. size-1). To show you how this works, the permutation
(2,1,0)
maps to the 3 coordinates(2,0), (1,1), (0,2)
. The 6 examples you gave areTo explain the mapping, lets take the first permutation
(2,1,0) --> (2,0), (1,1), (0,2)
. Then, the values you want to use arearray[2][0], array[1][1], array[0][2]
So now the question is how to generate each permutation. There are a few algorithms, one of which is implemented in java here: http://www.merriampark.com/perm.htm