是否可以在保留行和列频率的同时对二维矩阵进行混洗？

Question

假设我有一个如下所示的2D数组:

GACTG
AGATA
TCCGA

每个数组元素取自一个小的有限集(在我的例子中,DNA核苷酸 - {A, C, G, T}).我想以某种方式随机洗牌这个数组,同时保留行和列核苷酸频率.这可能吗？可以有效地完成吗？

[编辑]:我的意思是我想要生成一个新的矩阵,其中每一行的As,Cs,Gs和Ts的数量与原始矩阵的相应行数相同,并且每列具有相同数量的As,Cs,Gs和Ts作为原始矩阵的对应列. 置换原始矩阵的行或列通常不会实现此目的. (例如,对于上面的例子中,顶行有2 G秒,1的每一个A,C并且T,如果该行与第2行交换,在所得到的矩阵的最上一行将具有3个AS,1 G和1 T).

通过一次改变列来保​​持列频率,同样适用于行,这很简单.但这样做通常会改变另一种频率.

到目前为止我的想法: 如果可以选择2行和2列,以便这个矩形角落的4个元素具有模式

XY
YX

对于一些对不同元件的X和Y,然后更换这些4个元素与

YX
XY

将保持行频和列频.在顶部的示例中,这可以针对(至少)第1行和第2行以及第2列和第5列(其角部给出2x2矩阵AG;GA)以及第1行和第3行以及第1列和第4列(其角落给出GT;TG)进行.显然,这可以重复多次以产生一定程度的随机化.

推广一点,由行的子集和列的子集引起的任何"子矩形",其中所有行的频率相同并且所有列的频率相同,可以使其行和列置换以产生一个有效的完整矩形.(其中,只有那些至少改变了1个元素的子矩形实际上很有趣.)大问题:

1. 是否所有有效的完整矩阵都可通过一系列此类"子矩阵重排"到达？ 我怀疑答案是肯定的.
2. 是否所有有效的子矩阵重排都可以分解为一系列2x2交换？ [编辑]:mhum的反例表明答案是否定的.不幸的是,因为这似乎使得提出一种有效的算法变得更加困难,但重要的是要知道.
3. 是否可以有效地计算部分或全部有效重排？

这个问题涉及一组特殊情况,其中包含可能的元素集{0, 1}.人们提出的解决方案与我自己提出的解决方案类似,可能是可用的,但并不理想,因为它们需要任意数量的回溯才能正常工作.另外我担心只考虑2x2掉期.

最后,我理想地想要一种解决方案,可以证明从具有与原始行相同的行频率和列频率的所有矩阵的集合中随机均匀地选择矩阵.我知道,我要求很多:)

Answer 1

没有线索，但你所说的基本上是一个广义的数独求解器。尝试http://scholar.google.com/scholar?q=sudoku