我遇到的问题是试图找到一种有效的方法来查找矩阵中的可交换元素，以便为创建空模型实现交换算法。
该矩阵由 0 和 1 组成，其想法是元素可以在列之间切换，以便矩阵的行和列总数保持不变。
例如，给定以下矩阵：
c1 c2 c3 c4
r1 0 1 0 0 = 1
r2 1 0 0 1 = 2
r3 0 0 0 0 = 0
r4 1 1 1 1 = 4
------------
2 2 1 2
r1 和 r2 中的 c2 和 c4 列都可以以不改变总数的方式交换，即：
c1 c2 c3 c4
r1 0 0 0 1 = 1
r2 1 1 0 0 = 2
r3 0 0 0 0 = 0
r4 1 1 1 1 = 4
------------
2 2 1 2
这一切都需要随机进行，以免引入任何偏见。
我有一个可行的解决方案。我随机选择一行和两列。如果它们产生 10 或 01 模式，那么我随机选择另一行并检查相同的列以查看它们是否产生相反的模式。如果其中任何一个失败，我会重新开始并选择一个新元素。
这种方法有效，但我只有大约 10% 的时间“命中”了正确的模式。在一个大矩阵或行中只有几个 1 的矩阵中，我浪费了很多时间“失踪”。我认为必须有一种更智能的方式来选择矩阵中的元素，但仍然随机进行。
工作方法的代码是：
def isSwappable(matrix: Matrix): Tuple2[Tuple2[Int, Int], Tuple2[Int, Int]] = {
val indices = getRowAndColIndices(matrix)
(matrix(indices._1._1)(indices._2._1), matrix(indices._1._1)(indices._2._2)) match {
case (1, 0) => {
if (matrix(indices._1._2)(indices._2._1) == 0 & matrix(indices._1._2)(indices._2._2) == 1) {
indices
}
else {
isSwappable(matrix)
}
}
case (0, 1) => {
if (matrix(indices._1._2)(indices._2._1) == 1 & matrix(indices._1._2)(indices._2._2) == 0) {
indices
}
else {
isSwappable(matrix)
}
}
case _ => {
isSwappable(matrix)
}
}
}
def getRowAndColIndices(matrix: Matrix): Tuple2[Tuple2[Int, Int], Tuple2[Int, Int]] = {
(getNextIndex(rnd.nextInt(matrix.size), matrix.size), getNextIndex(rnd.nextInt(matrix(0).size), matrix(0).size))
}
def getNextIndex(i: Int, constraint: Int): Tuple2[Int, Int] = {
val newIndex = rnd.nextInt(constraint)
newIndex match {
case `i` => getNextIndex(i, constraint)
case _ => (i, newIndex)
}
}
我想一种更有效的处理方法是删除任何无法使用的行（全 1 或 0），然后随机选择一个元素。从那里我可以过滤掉行中具有相同值的任何列，并从剩余的列中进行选择。
一旦选择了第一行和第一列，我就会过滤掉不能提供所需模式的行，然后从剩余的行中进行选择。
这在大多数情况下都有效，但我不知道如何处理的问题是当没有列或行可供选择时会发生什么？我不想无限循环试图找到我需要的模式，如果我确实得到一个空的行或列列表可供选择，我需要一种重新开始的方法。
到目前为止，我拥有的那种工作的代码（直到我得到一个空列表）是：
def getInformativeRowIndices(matrix: Matrix) = (
matrix
.zipWithIndex
.filter(_._1.distinct.size > 1)
.map(_._2)
.toList
)
def getRowsWithOppositeValueInColumn(col: Int, value: Int, matrix: Matrix) = (
matrix
.zipWithIndex
.filter(_._1(col) != value)
.map(_._2)
.toList
)
def getColsWithOppositeValueInSameRow(row: Int, value: Int, matrix: Matrix) = (
matrix(row)
.zipWithIndex
.filter(_._1 != value)
.map(_._2)
.toList
)
def process(matrix: Matrix): Tuple2[Tuple2[Int, Int], Tuple2[Int, Int]] = {
val row1Indices = getInformativeRowIndices(matrix)
if (row1Indices.isEmpty) sys.error("No informative rows")
val row1 = row1Indices(rnd.nextInt(row1Indices.size))
val col1 = rnd.nextInt(matrix(0).size)
val colIndices = getColsWithOppositeValueInSameRow(row1, matrix(row1)(col1), matrix)
if (colIndices.isEmpty) process(matrix)
val col2 = colIndices(rnd.nextInt(colIndices.size))
val row2Indices = getRowsWithOppositeValueInColumn(col1, matrix(row1)(col1), matrix)
.intersect(getRowsWithOppositeValueInColumn(col2, matrix(row1)(col2), matrix))
println(row2Indices)
if (row2Indices.isEmpty) process(matrix)
val row2 = row2Indices(rnd.nextInt(row2Indices.size))
((row1, row2), (col1, col2))
}
我认为递归方法是错误的，在这里并没有真正起作用。另外，我真的只是想提高细胞选择的速度，所以任何想法或建议都将不胜感激。
编辑：
我有机会多玩一点，并提出了另一种解决方案，但它似乎并没有比随机选择矩阵中的单元快得多。另外，我应该补充一点，矩阵需要连续交换大约 30000 次才能被认为是随机的，并且我需要为每个测试生成 5000 个随机矩阵，我至少还有另外 5000 个可以这样做，所以性能很好的重要。
当前的解决方案（除了随机单元格选择之外是：
- 从矩阵中随机选择 2 行
- 从另一行中减去一行并将其放入数组中
- 如果新数组同时包含 1 和 -1 那么我们可以交换
减法的逻辑如下所示：
0 1 0 0
- 1 0 0 1
---------------
-1 1 0 -1
执行此操作的方法如下所示：
def findSwaps(matrix: Matrix, iterations: Int): Boolean = {
var result = false
val mtxLength = matrix.length
val row1 = rnd.nextInt(mtxLength)
val row2 = getNextIndex(row1, mtxLength)
val difference = subRows(matrix(row1), matrix(row2))
if (difference.min == -1 & difference.max == 1) {
val zeroOne = difference.zipWithIndex.filter(_._1 == -1).map(_._2)
val oneZero = difference.zipWithIndex.filter(_._1 == 1).map(_._2)
val col1 = zeroOne(rnd.nextInt(zeroOne.length))
val col2 = oneZero(rnd.nextInt(oneZero.length))
swap(matrix, row1, row2, col1, col2)
result = true
}
result
}
矩阵行减法如下所示：
def subRows(a: Array[Int], b: Array[Int]): Array[Int] = (a, b).zipped.map(_ - _)
实际的交换看起来像这样：
def swap(matrix: Matrix, row1: Int, row2: Int, col1: Int, col2: Int) = {
val temp = (matrix(row1)(col1), matrix(row1)(col2))
matrix(row1)(col1) = matrix(row2)(col1)
matrix(row1)(col2) = matrix(row2)(col2)
matrix(row2)(col1) = temp._1
matrix(row2)(col2) = temp._2
matrix
}
这比以前好得多，因为我尝试交换的成功率在 80% 到 90% 之间（随机单元选择只有大约 10%）但是......它仍然需要大约 2.5 分钟才能生成 1000 个随机矩阵。
关于如何提高速度的任何想法？