33,008
社区成员
发帖
与我相关
我的任务
分享思考一下，谢谢
有一个3*3的矩阵，里面分别填着数字0~8，填入的时候是随机的，要求每次只能用0和和边上的一个数字交换，最终实现所要求的数字排列。
如：
随机真数字矩阵为：
1 3 5
0 2 6
4 7 8 0，可以与1，2，4交换
最终变成目标矩阵
1 2 3
8 0 4
7 6 5
中间可进行无限次0与其他数字的交换。
问：
任意给一个数字矩阵，能否证明：经过无限次的交换，一定能到达目标矩阵或者经过无限的交换也不能实现目标矩阵？
如果没说清楚，请跟贴
解决问题，再追加300分
如：
随机真数字矩阵为：
1 3 5
0 2 6
4 7 8 0，可以与1，2，4交换
最终变成目标矩阵
1 2 3
8 0 4
7 6 5
中间可进行无限次0与其他数字的交换。
问：
任意给一个数字矩阵，能否证明：经过无限次的交换，一定能到达目标矩阵或者经过无限的交换也不能实现目标矩阵？
如果没说清楚，请跟贴
解决问题，再追加300分
...全文
请发表友善的回复…
发表回复
loginnum 2010-08-17
- 打赏
- 举报
[Quote=引用 8 楼 medie2005 的回复:]
呵呵，没说清楚。
矩阵
1 3 5
0 2 6
4 7 8
按行展开就得到了：
1 3 5 0 2 6 4 7 8
我们定义其逆序数为：从中去掉0之后，剩下排列的逆序数。
于是，
对于2,0,1， => 2,1 => r(p)=1
对于0,2,1， => 2,1 => r(p)=1
[/Quote] 但是
对于 1，2，3 => r(p)=0
对于 2，1，3 => r(p)=1
应该说，只有两个数字位置不同的排列，其奇偶性不同，这个和0没关系。
呵呵，没说清楚。
矩阵
1 3 5
0 2 6
4 7 8
按行展开就得到了：
1 3 5 0 2 6 4 7 8
我们定义其逆序数为：从中去掉0之后，剩下排列的逆序数。
于是，
对于2,0,1， => 2,1 => r(p)=1
对于0,2,1， => 2,1 => r(p)=1
[/Quote] 但是
对于 1，2，3 => r(p)=0
对于 2，1，3 => r(p)=1
应该说，只有两个数字位置不同的排列，其奇偶性不同，这个和0没关系。
foolishai 2009-11-24
- 打赏
- 举报
123 ？ 123
456 → 456
870 780？
456 → 456
870 780？
ian123 2009-08-04
- 打赏
- 举报
你们真无聊；
游戏开发用的着套用公式吗，
让程序随机走几步不就行了。
游戏开发用的着套用公式吗，
让程序随机走几步不就行了。
光义 2009-03-03
- 打赏
- 举报
学习一下，呵呵！
锋妍踏雪 2009-01-06
- 打赏
- 举报
新手，mark一下，一会回来学习一下，呵呵！
zjk2752 2008-10-06
- 打赏
- 举报
[size=18px]实在不实在不好意思，本来说给三百分的，可是系统只让给三百分，下次我再补上了，再次谢谢各位[/size]
zjk2752 2008-10-06
- 打赏
- 举报
唉，我现在都大二了，怎么对这样研究性的问题还是无从下手呀，根本就不知道从哪里下手呀？你们都是什么学历呀？各位大哥
zjk2752 2008-10-06
- 打赏
- 举报
这么多的高手呀！我这次真是学到了不少，先谢谢各位！分数以后补上
绿色夹克衫 2008-10-04
- 打赏
- 举报
最后还有一个推论忘了说了，就是如果整个矩阵中存在两个相同的元素，则这个矩阵内的元素不论怎么打乱，均可以同原矩阵相互转换。
绿色夹克衫 2008-10-04
- 打赏
- 举报
原来也想过走逆序数这条路，但由于偶数列时，每次上下移动，逆序数都会变化，就没有继续深入，
另外逆序数的方法存在一个选择方向的问题，比如：
0 1 2
3 4 5
6 7 8
构造逆序数列的时候即可以看成 0 1 2 3 4 5 6 7 8，也可以看成0 3 6 1 4 7 2 5 8
当时觉得恐怕走这条路比较难。
关于偶数次交换的方法，我原来的证明只提供了充分性（且很不完整，还有漏洞），即偶数次交换可以到达，但未能证明必要性，即奇数次交换则永远不能到达。
我现在也完整的写一下：
首先利用2*2的矩阵证明n = 2的情况下成立
0 1
2 3
矩阵中除0以外的元素进行偶数次交换后形成的新矩阵，都可以由现在的矩阵变形后得到
交换后形成的矩阵共有2种情况：
0 2
3 1
0 3
1 2
假设n * 2的矩阵中，所有的非0元素进行偶数次交换后形成的新矩阵，都可以由现在的矩阵变形后得到
证明(n + 1) * 2的矩阵中，所有的非0元素进行偶数次交换后形成的新矩阵，都可以由现在的矩阵变形后得到
对于(n + 1) * 2的矩阵
0 v(12) v(13) ...... v(1 n + 1)
v(21) v(22) v(23) ...... v(2 n + 1)
其中新加入的两个元素为
v(1 n + 1)
v(2 n + 1)
因为在n * 2的矩阵中成立，所以仅需证明包含
v(1 n + 1)
v(2 n + 1)
这两个新元素在内的偶数次交换也成立即可
0 v(12) v(13) ...... v(1n) v(1 n + 1)
v(21) v(22) v(23) ...... v(2n) v(2 n + 1)
将0移至v(12)位置
v(12) 0 v(13) ...... v(1 n + 1)
v(21) v(22) v(23) ...... v(2 n + 1)
因为在n * 2的矩阵中成立，所以去掉第一列后形成的n * 2矩阵中，任何两个非0元素进行偶数次交换后形成的新矩阵，都可以由现在的矩阵变形后得到
而所有包含
v(1 n + 1)
v(2 n + 1)
的交换，也都可以利用这两个矩阵，进行元素间的交换来等价实现。当且仅当v(12)或v(21) 与v(1 n + 1)或v(2 n + 1)进行交换时，需要同时在两个矩阵中进行交换操作，其他交换都是在一个矩阵内进行操作，
因此，如果不涉及v(12)或v(21) 与v(1 n + 1)或v(2 n + 1)的交换，交换次数等于n * 2的矩阵，即仍为偶数次交换。
如果涉及到v(12)或v(21) 与v(1 n + 1)或v(2 n + 1)的交换，则需要在中间随便找一个v(i j)作为过渡元素，再随便找该矩阵中的两个元素v(mn) v(op)作为临时交换变量，交换过程为：
v(12)或v(21)交换到v(i j)，再将v(1 n + 1)或v(2 n + 1)与v(12)或v(21)交换，再将v(i j)与v(1 n + 1)或v(2 n + 1)交换
交换次数由1次变为了3次，但总的交换次数仍为偶数次，因此可以证明
(n + 1) * 2的矩阵中，所有的非0元素进行偶数次交换后形成的新矩阵，都可以由现在的矩阵变形后得到。
我们把这个结论叫做推论1
这个证明仅在n=3时，选择过渡元素时存在一些问题，但n=3时，该命题同样成立。（在真正交换过程中，可能还需要借助另外两个交换变量，以达到变化的完全等价，在这里写起来比较麻烦，省略了）
同理，在证明了n * 2型的矩阵后，假设n * m矩阵也成立，证明n * (m+1)也成立，证明方法同n * 2型一样，所有涉及2个矩阵的交换，交换次数之和仍为偶数。因此可以证明矩阵中的任何非0元素进行偶数次交换后所得到的新矩阵，可以由原始矩阵变形后得到。推论2
上面证明了充分性的问题。
因为推论2，所有n * m阶矩阵，均可利用这个交换的特性将问题变为2 * 2的矩阵问题。且在2 * 2的矩阵中，存在2种永远无法相互转换的矩阵
0 1
2 3
0 1
3 2
且这两个矩阵可通过奇数次交换（交换一次2 3）互相转换，因此当两个矩阵互相转化的过程当中，需要进行奇数次交换，这两个矩阵将永远无法相互转换，反之偶数次交换，则两个矩阵可以互相转换
证明完毕(希望没有什么逻辑漏洞)
另外逆序数的方法存在一个选择方向的问题，比如：
0 1 2
3 4 5
6 7 8
构造逆序数列的时候即可以看成 0 1 2 3 4 5 6 7 8，也可以看成0 3 6 1 4 7 2 5 8
当时觉得恐怕走这条路比较难。
关于偶数次交换的方法，我原来的证明只提供了充分性（且很不完整，还有漏洞），即偶数次交换可以到达，但未能证明必要性，即奇数次交换则永远不能到达。
我现在也完整的写一下：
首先利用2*2的矩阵证明n = 2的情况下成立
0 1
2 3
矩阵中除0以外的元素进行偶数次交换后形成的新矩阵，都可以由现在的矩阵变形后得到
交换后形成的矩阵共有2种情况：
0 2
3 1
0 3
1 2
假设n * 2的矩阵中，所有的非0元素进行偶数次交换后形成的新矩阵，都可以由现在的矩阵变形后得到
证明(n + 1) * 2的矩阵中，所有的非0元素进行偶数次交换后形成的新矩阵，都可以由现在的矩阵变形后得到
对于(n + 1) * 2的矩阵
0 v(12) v(13) ...... v(1 n + 1)
v(21) v(22) v(23) ...... v(2 n + 1)
其中新加入的两个元素为
v(1 n + 1)
v(2 n + 1)
因为在n * 2的矩阵中成立，所以仅需证明包含
v(1 n + 1)
v(2 n + 1)
这两个新元素在内的偶数次交换也成立即可
0 v(12) v(13) ...... v(1n) v(1 n + 1)
v(21) v(22) v(23) ...... v(2n) v(2 n + 1)
将0移至v(12)位置
v(12) 0 v(13) ...... v(1 n + 1)
v(21) v(22) v(23) ...... v(2 n + 1)
因为在n * 2的矩阵中成立，所以去掉第一列后形成的n * 2矩阵中，任何两个非0元素进行偶数次交换后形成的新矩阵，都可以由现在的矩阵变形后得到
而所有包含
v(1 n + 1)
v(2 n + 1)
的交换，也都可以利用这两个矩阵，进行元素间的交换来等价实现。当且仅当v(12)或v(21) 与v(1 n + 1)或v(2 n + 1)进行交换时，需要同时在两个矩阵中进行交换操作，其他交换都是在一个矩阵内进行操作，
因此，如果不涉及v(12)或v(21) 与v(1 n + 1)或v(2 n + 1)的交换，交换次数等于n * 2的矩阵，即仍为偶数次交换。
如果涉及到v(12)或v(21) 与v(1 n + 1)或v(2 n + 1)的交换，则需要在中间随便找一个v(i j)作为过渡元素，再随便找该矩阵中的两个元素v(mn) v(op)作为临时交换变量，交换过程为：
v(12)或v(21)交换到v(i j)，再将v(1 n + 1)或v(2 n + 1)与v(12)或v(21)交换，再将v(i j)与v(1 n + 1)或v(2 n + 1)交换
交换次数由1次变为了3次，但总的交换次数仍为偶数次，因此可以证明
(n + 1) * 2的矩阵中，所有的非0元素进行偶数次交换后形成的新矩阵，都可以由现在的矩阵变形后得到。
我们把这个结论叫做推论1
这个证明仅在n=3时，选择过渡元素时存在一些问题，但n=3时，该命题同样成立。（在真正交换过程中，可能还需要借助另外两个交换变量，以达到变化的完全等价，在这里写起来比较麻烦，省略了）
同理，在证明了n * 2型的矩阵后，假设n * m矩阵也成立，证明n * (m+1)也成立，证明方法同n * 2型一样，所有涉及2个矩阵的交换，交换次数之和仍为偶数。因此可以证明矩阵中的任何非0元素进行偶数次交换后所得到的新矩阵，可以由原始矩阵变形后得到。推论2
上面证明了充分性的问题。
因为推论2，所有n * m阶矩阵，均可利用这个交换的特性将问题变为2 * 2的矩阵问题。且在2 * 2的矩阵中，存在2种永远无法相互转换的矩阵
0 1
2 3
0 1
3 2
且这两个矩阵可通过奇数次交换（交换一次2 3）互相转换，因此当两个矩阵互相转化的过程当中，需要进行奇数次交换，这两个矩阵将永远无法相互转换，反之偶数次交换，则两个矩阵可以互相转换
证明完毕(希望没有什么逻辑漏洞)
tailzhou 2008-09-30
- 打赏
- 举报
你有仔细看我的结论1没？？
结论1： "对于任意的m*n的矩阵，若经过偶数次的左右移动，以及偶数次的上下移动，那么序列的逆序对的奇偶性保持不变"
偶数次的左右移动，以及偶数次的上下交换；
结论1： "对于任意的m*n的矩阵，若经过偶数次的左右移动，以及偶数次的上下移动，那么序列的逆序对的奇偶性保持不变"
偶数次的左右移动，以及偶数次的上下交换；
jiangbin00cn 2008-09-30
- 打赏
- 举报
矩阵
1 3 5
0 2 6
4 7 8
按0可能的移动方位展开就得到了：
1 3 5 6 2 4 7 8 －－－－修改读取的方向
即：3×3的矩阵展开为：
a00 a01 a02 a12 a11 a10 a20 a21 a22
－－－>
<----
----->
你的结论1不用4种方法证明
假设0在a[i][j]位
1. 0左右移不改变奇偶性
2. 0上移或下移，改变的逆序数为：2×j;或2*(n-j)
因此逆序数的改变为偶数
1 3 5
0 2 6
4 7 8
按0可能的移动方位展开就得到了：
1 3 5 6 2 4 7 8 －－－－修改读取的方向
即：3×3的矩阵展开为：
a00 a01 a02 a12 a11 a10 a20 a21 a22
－－－>
<----
----->
你的结论1不用4种方法证明
假设0在a[i][j]位
1. 0左右移不改变奇偶性
2. 0上移或下移，改变的逆序数为：2×j;或2*(n-j)
因此逆序数的改变为偶数
tailzhou 2008-09-30
- 打赏
- 举报
to:楼上
为什么不可以先行后列的顺序排列？
对于任意的m*n的矩阵，旋转成n*m,不就是另一排列方式了么？
不管是哪种方式排列，都是一样的；只要源与目的状态里的0的位置相同（这点是必须的，必须先对源与目的状态进行规范化处理，才能应用逆序数的奇偶性），且两矩阵的排列顺序一致就可以；因此(n*m)!种排列方式中的任意一种都是可以的；
另外我的结论1跟排列方式没任何关系；
不管上下交换还是左右交换改不改变逆序数的奇偶性，只要次数是偶数，最终都不改变逆序数的奇偶性；
为什么不可以先行后列的顺序排列？
对于任意的m*n的矩阵，旋转成n*m,不就是另一排列方式了么？
不管是哪种方式排列，都是一样的；只要源与目的状态里的0的位置相同（这点是必须的，必须先对源与目的状态进行规范化处理，才能应用逆序数的奇偶性），且两矩阵的排列顺序一致就可以；因此(n*m)!种排列方式中的任意一种都是可以的；
另外我的结论1跟排列方式没任何关系；
不管上下交换还是左右交换改不改变逆序数的奇偶性，只要次数是偶数，最终都不改变逆序数的奇偶性；
tailzhou 2008-09-30
- 打赏
- 举报
to: jiangbin00cn
实际上，我的序列是包含0在里面的，不管是上下还是左右,所以每次移动都会改变奇偶性；
"偶数次的左右移动，以及偶数次的上下移动" 这个条件可以更宽松，只需要总的移动是偶数就行；
我重新整理了一下，若有兴趣可以去看看这个链接:
http://blog.csdn.net/tailzhou/archive/2008/09/30/3002442.aspx
实际上，我的序列是包含0在里面的，不管是上下还是左右,所以每次移动都会改变奇偶性；
"偶数次的左右移动，以及偶数次的上下移动" 这个条件可以更宽松，只需要总的移动是偶数就行；
我重新整理了一下，若有兴趣可以去看看这个链接:
http://blog.csdn.net/tailzhou/archive/2008/09/30/3002442.aspx
jiangbin00cn 2008-09-30
- 打赏
- 举报
结论1： "对于任意的m*n的矩阵，若经过偶数次的左右移动，以及偶数次的上下交换，那么序列的逆序对的奇偶性保持不变"
1）假设序列按照先行后列的顺序排列，那么每次左右交换，都不改变序列的逆序对的奇偶性；
a) 当列为奇数的时候，每次上下交换，也不改变序列的逆序对的奇偶性；
b) 当列为偶数的时候，每次上下交换，都会改变序列的逆序对的奇偶性；
2）假设序列按照先列后行的顺序排列，那么每次上下交换，都不改变序列的逆序对的奇偶性；
a) 当行为奇数的时候，每次左右交换，也不改变序列的逆序对的奇偶性；
b) 当行为偶数的时候，每次左右交换，都会改变序列的逆序对的奇偶性；
由于左右交换，以及上下交换的总次数都是偶数，所以 结论1得证；
////////////////////////////////////////////////////////////////////
这个完全不应该用先行后列的顺序排列
排列方法见24楼
这样能够保证无论上下交换还是左右交换都不改变逆序数
1）假设序列按照先行后列的顺序排列，那么每次左右交换，都不改变序列的逆序对的奇偶性；
a) 当列为奇数的时候，每次上下交换，也不改变序列的逆序对的奇偶性；
b) 当列为偶数的时候，每次上下交换，都会改变序列的逆序对的奇偶性；
2）假设序列按照先列后行的顺序排列，那么每次上下交换，都不改变序列的逆序对的奇偶性；
a) 当行为奇数的时候，每次左右交换，也不改变序列的逆序对的奇偶性；
b) 当行为偶数的时候，每次左右交换，都会改变序列的逆序对的奇偶性；
由于左右交换，以及上下交换的总次数都是偶数，所以 结论1得证；
////////////////////////////////////////////////////////////////////
这个完全不应该用先行后列的顺序排列
排列方法见24楼
这样能够保证无论上下交换还是左右交换都不改变逆序数
tailzhou 2008-09-30
- 打赏
- 举报
什么科学不科学;
只要没错误,就是正确的;
哪怕我是按照a11,a13,a15,....a12,a14...来排列都行
只要没错误,就是正确的;
哪怕我是按照a11,a13,a15,....a12,a14...来排列都行
jiangbin00cn 2008-09-30
- 打赏
- 举报
你有仔细看我的结论1没？？
结论1： "对于任意的m*n的矩阵，若经过偶数次的左右移动，以及偶数次的上下移动，那么序列的逆序对的奇偶性保持不变"
偶数次的左右移动，以及偶数次的上下交换；
//////////////////////////////////////////////////////////////
换一种展开方式，任意次左右移动，上下移动，逆序对的奇偶性都保持不变。
你的结论没有问题，但是按需先行后列（或先列后行）的展开方式不科学
结论1： "对于任意的m*n的矩阵，若经过偶数次的左右移动，以及偶数次的上下移动，那么序列的逆序对的奇偶性保持不变"
偶数次的左右移动，以及偶数次的上下交换；
//////////////////////////////////////////////////////////////
换一种展开方式，任意次左右移动，上下移动，逆序对的奇偶性都保持不变。
你的结论没有问题，但是按需先行后列（或先列后行）的展开方式不科学
tailzhou 2008-09-29
- 打赏
- 举报
还没解决呢；
还不能完全证明；
我贴的也有问题；
实际上，交换两元素的位置，必定导致逆序对的奇偶性的改变；
从结论2又可以得到“交换两非0元素的位置，其他元素的位置保持不变”时，逆序对的奇偶性的不变，得到了矛盾；
因此 "交换两非0元素的位置，其他元素的位置保持不变" 是不可能做到的;
所以 结论3的证明是完全错误的；
还不能完全证明；
我贴的也有问题；
实际上，交换两元素的位置，必定导致逆序对的奇偶性的改变；
从结论2又可以得到“交换两非0元素的位置，其他元素的位置保持不变”时，逆序对的奇偶性的不变，得到了矛盾；
因此 "交换两非0元素的位置，其他元素的位置保持不变" 是不可能做到的;
所以 结论3的证明是完全错误的；
zzwu 2008-09-29
- 打赏
- 举报
我以前为这类问题编过一个游戏，
可以用2*2，3*3，4*4，5*5，6*6的不同方阵。
程序要解决的问题就是如何给出随机的初始矩阵，但要保证有解，
为此就要考虑对换的奇偶性。
可以用2*2，3*3，4*4，5*5，6*6的不同方阵。
程序要解决的问题就是如何给出随机的初始矩阵，但要保证有解，
为此就要考虑对换的奇偶性。
C1053710211 2008-09-29
- 打赏
- 举报
哇，4颗星星
加载更多回复（34）
