l*****c
发帖数: 316 | 1 给定一个整数n , 给定整数m
列举所有的矩阵，满足条件：1 元素都是0 或 1
2，矩阵 n * m
3, 每行的和为 m-1，每列不得全为1
例如 n=4, m=3
1 0 1
0 1 1
1 1 0
1 0 1
或
1 1 0
0 1 1
1 1 0
1 0 1
如何找出所有的矩阵，用最少的时间
觉得这题有点bt, 被难住了，求帮助 | m******k
发帖数: 593 | | l*****c
发帖数: 316 | 3 sorry， 改过来了
【在 m******k 的大作中提到】
: the 2nd ex is wrong
| f***g
发帖数: 214 | 4 跟8皇后类似吧，
往全1矩阵里面放0；
条件：
每行有一个0；
每列必须要有0；
递归。
不知道有没有更快的 | l*****c
发帖数: 316 | 5 8皇后？
【在 f***g 的大作中提到】
: 跟8皇后类似吧，
: 往全1矩阵里面放0；
: 条件：
: 每行有一个0；
: 每列必须要有0；
: 递归。
: 不知道有没有更快的
| l*****c
发帖数: 316 | 6 8皇后是8*8的，任意n*m的如何做呢
我这个问题一直比较没搞清楚，请指教
【在 l*****c 的大作中提到】
: 8皇后？
| I*********g
发帖数: 93 | 7 A[n][m] = C(n, 1) * A[n-1][m-1] + ... + C(n,k)*A[n-k][m-1]
n-k >= m-1
A[n][m]是结果。
A[m][m]=m!
首先考虑在第一列中一些行放0,然后递归。 | l*****c
发帖数: 316 | 8 thanks，will try this
【在 I*********g 的大作中提到】
: A[n][m] = C(n, 1) * A[n-1][m-1] + ... + C(n,k)*A[n-k][m-1]
: n-k >= m-1
: A[n][m]是结果。
: A[m][m]=m!
: 首先考虑在第一列中一些行放0,然后递归。
| h**6
发帖数: 4160 | 9 如果只求不同矩阵的个数，还是很好办的。
f(n,1) = 1
f(n,n) = n!
f(n,m) = m[f(n-1,m)+f(n-1,m-1)] | b******e
发帖数: 925 | 10 没看明白，能再说说不。。。
【在 I*********g 的大作中提到】
: A[n][m] = C(n, 1) * A[n-1][m-1] + ... + C(n,k)*A[n-k][m-1]
: n-k >= m-1
: A[n][m]是结果。
: A[m][m]=m!
: 首先考虑在第一列中一些行放0,然后递归。
| | | n******h
发帖数: 50 | 11 嗯。
【在 h**6 的大作中提到】
: 如果只求不同矩阵的个数，还是很好办的。
: f(n,1) = 1
: f(n,n) = n!
: f(n,m) = m[f(n-1,m)+f(n-1,m-1)]
| I*********g
发帖数: 93 | 12 这个会有重复的吧。
在第一行选一个位置(假设是第j列)放一个0
然后根据你的式子有两种选择：
1. 第j列没有0了 => f(n-1, m-1)
2. 第j列还可以存在0 => f(n-1, m)
但是第二种情况可以包括第一种。
【在 h**6 的大作中提到】
: 如果只求不同矩阵的个数，还是很好办的。
: f(n,1) = 1
: f(n,n) = n!
: f(n,m) = m[f(n-1,m)+f(n-1,m-1)]
| I*********g
发帖数: 93 | 13 就是先考虑在第一列上放0啊。
因为一行只有一个，那么放0 的那一行在子问题中就可以消去了。
【在 b******e 的大作中提到】
: 没看明白，能再说说不。。。
| h**6
发帖数: 4160 | 14 f(n, m)的定义是每行恰好有一个0，每列至少有一个0的矩阵数。
那么在第一行第j列放0后，以下n-1行有两种选择：
1. 第j列没有0 => f(n-1, m-1)
2. 第j列有0 => f(n-1, m)
两种选择不会重复或遗漏
【在 I*********g 的大作中提到】
: 这个会有重复的吧。
: 在第一行选一个位置(假设是第j列)放一个0
: 然后根据你的式子有两种选择：
: 1. 第j列没有0了 => f(n-1, m-1)
: 2. 第j列还可以存在0 => f(n-1, m)
: 但是第二种情况可以包括第一种。
| P********l
发帖数: 452 | 15 没搞懂，觉得哪里不对。
先说我的理解。
把每行的0的位置写下来可以得到一个编码.
例如 n=4, m=3
1 0 1
0 1 1
1 1 0
1 0 1
编码是: 1,0,2,1.
0到2肯定在其中，然后再从0－2任选一个。
所以f(4,3)=3! * 3 * 3 = 54种。
han6的迭代公式是36种。哪里不对。 | r******d
发帖数: 308 | 16 为什么是f(4,3)=3! * 3 * 3？
如果不考虑行的顺序， 按照你编码，可能的矩阵是 0120，0121，0122三种
如果考虑行的顺序， 每种上面的矩阵又有p(4,2)=4*3 种排列法。所以一起有36种
p(4,2)是要把两个不同的数放在四个位置上， 例如0120, 只要考虑把1, 2 放在四个位
置的可能性就好了
如果n-m相差比较大的话, 从概率的角度越想越复杂.....
【在 P********l 的大作中提到】
: 没搞懂，觉得哪里不对。
: 先说我的理解。
: 把每行的0的位置写下来可以得到一个编码.
: 例如 n=4, m=3
: 1 0 1
: 0 1 1
: 1 1 0
: 1 0 1
: 编码是: 1,0,2,1.
: 0到2肯定在其中，然后再从0－2任选一个。
| r******d
发帖数: 308 | 17 想到一个办法， 先按照PuTTYshell同学的编码方式对矩阵的行进行编码
例如 n=4, m=3
1 0 1
0 1 1
1 1 0
1 0 1
编码是: 1,0,2,1
因为每行的和为 m-1，就是说每行必须有一个0, 所以矩阵有m种行， 每种行可以用它
的二进制值来表示。
题目要求每列不得全为1， 所以矩阵里面m种行每种必须要有
所以我的思路是先找到所有的矩阵编码， 然后对每种编码排列组合输出数组来。
1 先建立一个一维大小为n的数组， 用来放所有的编码组合。
2 问题简化为要从m个数中选n 个出来， 而且所有的m要在里面。
如果先选m个不重复的出来， 然后再选(n-m)个，那样就需要排序才能够保证结果不重
复。 假定这个一维数组已经是排序的， 把问题转化为把 m个排序的数字放在n个空位
置里面就没有这个问题了。中间的空位就按照相邻的左边的数字来补上。
例如， 如果是n=4, m=3, 那么先把排序的3个数字放在4个空上，例如其中一个可能是0
*12, 或者01*2。 那这两种对应的编码分别是0012, 0112
最后就是输出矩阵了。 | h**6
发帖数: 4160 | 18 本题可分三步走：
1.把长度为 n 的数组分为 m 段，每段不为空。对应每一种分段法，把第一段全部赋值
为0， 第二段全部赋值为1，……，最后一段全部赋值为 m-1。
2.此时得到升序排列的有重复元素的数组，且 0~m-1 每个元素至少出现一次，使用
next_permutation 函数得到其全排列。
3.根据数组中每一个元素值，把矩阵对应位置元素设置为0，其余为1。
明显，第二、三步都很容易，现在我们看看如何进行第一步，数组分段。
众所周知，把长度为 n 的数组分为 m 段，一共有 C(n-1,m-1) 种方法，其中 C(,) 是
组合数。
1)以数组形式列出所有 n-1 中选 m-1 的组合数，此时得到一个长度为 n-1 的数组，
下标范围为 0~n-2 ，其中有 m-1 个1，其余为0。
2)在数组首尾两端各缩进一格，即位置 -1 和 n-1 处，设置起点和终点。
3)对应每一个组合数，一定能找出一个分段方法与之对应，具体如下：
第一个1与起点的距离为第一段长度，
第二个1与第一个1的距离为第二段长度，
……
第 m-1 个1与第 m-2 个1的距离为第 m-1 段长度，
终点与第 m-1 个1的距离为第 m 段长度。
以上分段方法满足 1)共m段；2)每段不为空；3)所有段长总和为起终点距离，即n
分段后，按升序填充数字，并遵照第二、三步即可列出所有矩阵。 | P********l
发帖数: 452 | 19 受益匪浅。
非常佩服han6,redcloud的数学推导。
这是按照han6的思路写的代码。
http://code.google.com/p/sureinterview/source/browse/test/test1/Matrix1.java#22
======
void generate(int n, int m) {
Integer[] segEnd = new Integer[n - 1];
for (int i = 0; i < n - 1; i++) {
segEnd[i] = i;
}
CombinationImpl combn = new CombinationImpl(Lists
.newArrayList(segEnd), m - 1);
for (List lastPos : combn) {
Integer[] codeSeed = new Integer[n];
lastPos.add(0, -1);
lastPos.add(n - 1);
// lastPos : ascending position number. In the case of f(4,3),
the
// first lastPos is {-1,0,1,3}
for (int i = 0; i < m; i++) {
// current segment is in range ( loasPos[i]+1, lastPos[i+1] )
for (int j = lastPos.get(i) + 1; j <= lastPos.get(i + 1); j+
+) {
codeSeed[j] = i;
}
}
// codeSeed : the ascending coding. In the case of f(4,3), the
first
// codeSeed is {0,1,2,2}
PermutationImpl perm = new PermutationImpl(
codeSeed);
// get all matrixes based on the seed code.
for (Integer[] code : perm) {
System.out.println(StringUtils.join(code, ","));
}
}
} | P********l
发帖数: 452 | 20 Result:
-1,0,1,3 <- lastPos
> 0,1,2,2 <- codeSeed
> 0,2,1,2
> 0,2,2,1
> 1,0,2,2
> 1,2,0,2
> 1,2,2,0
> 2,0,1,2
> 2,0,2,1
> 2,1,0,2
> 2,1,2,0
> 2,2,0,1
> 2,2,1,0
-1,0,2,3
> 0,1,1,2
> 0,1,2,1
> 0,2,1,1
> 1,0,1,2
> 1,0,2,1
> 1,1,0,2
> 1,1,2,0
> 1,2,0,1
> 1,2,1,0
> 2,0,1,1
> 2,1,0,1
> 2,1,1,0
-1,1,2,3
> 0,0,1,2
> 0,0,2,1
> 0,1,0,2
> 0,1,2,0
> 0,2,0,1
> 0,2,1,0
> 1,0,0,2
> 1,0,2,0
> 1,2,0,0
> 2,0,0,1
> 2,0,1,0
> 2,1,0,0 |
|
