计算二维数组的所有组合

之前有一篇《一道有趣的Java编程题》，后来发现我的解题方式只适合于通过正确答案一定有错误答案的题，如果通过正确答案找不到对应错误答案的话，就解不出来了。通过和同事交流，知道了可以使用暴力破解，这个说起来好像很简单，但是写起来还是挺难的，难点就在于如何把所有的答案组合统计起来，示例如下：

A 1 2

B 3 4

C 5 6

假设有A、B、C三组答案，每一组是两个答案，每组有且仅有一个答案正确，则答案组合的数量有8组（2的3次幂），所有答案组合如下：

1、3、5

1、3、6

1、4、5

1、4、6

2、3、5

2、3、6

2、4、5

2、4、6

这数据还不多，自己口头也能找出来这个所有的组合，但是数据多的话，口头肯定是算不出来的，太累人了，如果通过代码实现呢？这是比较有挑战性的，花了我半天时间才写出来，分析如下：

如上图，这是一个3 x 2的二维数据，这是题目数据，然后我们再看所有答案组合，如下：

这个答案组合也是一个二维数组，我们的难题就是如何把前一个二维数组转换为后一个二维数组，首先要找出规律，如下：

1、题目数组放到结果数组中时，第一行放到第一列，第二行放到第二列，第三行放到第三列，如下：

这里我们发现，左边数组的行索引和右边的列索引一样，即左边数组第一行的数据会放到右边数组的第一列，左边第二行会放到右边第二列，左边第三行会放到右边第三列。

2、每个答案都正好存在4次，如下：

这里可以发现

a、左边第一行放到右边时，每个数字连续放4次，即先放4次1，再放4次2。

b、左边第二行放到右边时，则两个两个交替放，即先往两个3，再放两个4，再放两个3，再放两个4，如果换一种理解可以这样，先放两个3，然后空两个再放两个3，然后往4时也一样，但是放4的起始位置要注意不是从0开始的。

c、左边第三行放到右边时，则是隔一个放一个。

右边数组中，每个数字可以连续放多少次呢？第一、第二、第三列分别为4、2、1，这个数字如何得来？可通过下面的发现规律：

如上图，连续放的次数和行索引组合起来，如下：

0 - 4 2的2次方

1 - 2 2的1次方

2 - 1 2的0次方

这里发现了有0、1、2和2、1、0是反顺序，如何通过0、1、2得到2、1、0呢？因为总共有3行，可以使用变量3来完成，如下：

3 - 1 - 0 = 2

3 - 1 - 1 = 1

3 - 1 - 2 = 0

所以，通过已经行数3和行索引，就能得到2、1、0。

找到了这些规律，我们就可以写代码了，如下：

fun main() {
    val allAnswers = arrayOf(
        arrayOf(1, 2),
        arrayOf(3, 4),
        arrayOf(5, 6),
    )

    val answerSheet = getAnswerSheet(allAnswers)
    answerSheet.forEach { println(it.contentToString()) }
}

private fun getAnswerSheet(allAnswers: Array<Array<Int>>): Array<Array<Int>> {
    // 计算答案表的大小为：2的allAnswers.size次幂
    val sheetSize = 2.0.pow(allAnswers.size).toInt()
    // 创建答案表
    val answerSheet = Array(sheetSize) { Array(allAnswers.size) { 0 } }
    // 遍历所有答案，并填充到答案表中
    allAnswers.forEachIndexed { outIndex, answers ->
        // 计算答案可以连续填充的最大次数
        val maxPutCount = 2.0.pow((allAnswers.size - 1 - outIndex).toDouble()).toInt()
        answers.forEachIndexed { index, answer ->
            var putCount = 0
            for (i in answerSheet.indices) {
                if (++putCount <= maxPutCount) {
                    answerSheet[i + index * maxPutCount][outIndex] = answer
                } else if (putCount % maxPutCount == 0) {
                    putCount = 0
                }
            }
        }
    }
    return answerSheet
}

运行结果如下：

[1, 3, 5]
[1, 3, 6]
[1, 4, 5]
[1, 4, 6]
[2, 3, 5]
[2, 3, 6]
[2, 4, 5]
[2, 4, 6]

Ok，完美的把所有的组合都打印出来了。学会了这个，似乎也可以玩玩密码的暴力破解了，原理就是把所有的密码数字列出来，然后转换成所有的密码组合，然后每个密码组合都试一下是否为正确密码。

续（2021_04_21）：前面说到，每个答案都会填充相同的次数，则循环这个次数即可，之前是循环的次数是比较多的，优化后，如下：

import kotlin.math.pow

fun main() {
    val allAnswers = arrayOf(
        arrayOf(1, 2),
        arrayOf(3, 4),
        arrayOf(5, 6),
    )

    val answerSheet = getAnswerSheet(allAnswers)
    answerSheet.forEach { println(it.contentToString()) }
}

private fun getAnswerSheet(allAnswers: Array<Array<Int>>): Array<Array<Int>> {
    // 计算答案表的大小为：2的allAnswers.size次幂
    val sheetSize = 2.0.pow(allAnswers.size).toInt()
    // 创建答案表
    val answerSheet = Array(sheetSize) { Array(allAnswers.size) { 0 } }
    // 遍历所有答案，并填充到答案表中
    allAnswers.forEachIndexed { outIndex, answers ->
        // 计算答案可以连续填充的最大次数
        val maxPutCount = 2.0.pow((allAnswers.size - 1 - outIndex).toDouble()).toInt()
        answers.forEachIndexed { index, answer ->
            var putCount = 0
            var putIndex = 0
            repeat(answerSheet.size / 2) {
                answerSheet[putIndex++ + index * maxPutCount][outIndex] = answer
                if (++putCount % maxPutCount == 0) {
                    putIndex += maxPutCount
                }
            }
        }
    }
    return answerSheet
}

最后，我们把《一道有趣的Java编程题》中的练习题，使用暴力破解实现一下，如下：

import kotlin.math.pow

// 定义一个Answer类来表示一个答案
data class Answer(val number: Int, val name: String) {
    override fun toString() = "$number$name"
}

fun main() {
    val allAnswers = arrayOf(
        arrayOf(Answer(2, "陕西"), Answer(5, "甘肃")),
        arrayOf(Answer(2, "湖北"), Answer(4, "山东")),
        arrayOf(Answer(1, "山东"), Answer(5, "吉林")),
        arrayOf(Answer(3, "湖北"), Answer(4, "吉林")),
        arrayOf(Answer(2, "甘肃"), Answer(3, "陕西"))
    )

    val answerSheet = getAnswerSheet(allAnswers)
    val rightAnswer = findRightAnswers(answerSheet)
    rightAnswer.forEach { println(it.contentToString()) }
}

private fun getAnswerSheet(allAnswers: Array<Array<Answer>>): Array<Array<Answer>> {
    // 计算答案表的大小为：2的allAnswers.size次幂
    val sheetSize = 2.0.pow(allAnswers.size).toInt()
    // 创建答案表
    val answerSheet = Array(sheetSize) { Array(allAnswers.size) { Answer(0, "") } }
    // 遍历所有答案，并填充到答案表中
    allAnswers.forEachIndexed { outIndex, answers ->
        // 计算答案可以连续填充的最大次数
        val maxPutCount = 2.0.pow((allAnswers.size - 1 - outIndex).toDouble()).toInt()
        answers.forEachIndexed { index, answer ->
            var putCount = 0
            var putIndex = 0
            repeat(answerSheet.size / 2) {
                answerSheet[putIndex++ + index * maxPutCount][outIndex] = answer
                if (++putCount % maxPutCount == 0) {
                    putIndex += maxPutCount
                }
            }
        }
    }
    return answerSheet
}

/** 找到答案表中的所有正确答案 */
fun findRightAnswers(answerSheet: Array<Array<Answer>>): List<Array<Answer>> {
    val rightAnswer = mutableListOf<Array<Answer>>()
    // 遍历每一组答案，并验证是否正确
    answerSheet.forEach { oneGroupAnswer ->
        if (isRightAnswer(oneGroupAnswer)) {
            rightAnswer.add(oneGroupAnswer)
        }
    }
    return rightAnswer
}

/** 判断一组答案是否正确 */
fun isRightAnswer(oneGroupAnswer: Array<Answer>): Boolean {
    val rightAnswers = mutableListOf<Answer>()
    oneGroupAnswer.forEach { answer ->
        if (rightAnswers.any { it.number == answer.number || it.name == answer.name }) {
            return false
        }
        rightAnswers.add(answer)
    }
    return true
}

运行结果如下：

[5甘肃, 2湖北, 1山东, 4吉林, 3陕西]