java - 列出每次占用9个单元格的9x9框的所有可能组合

这是最初的二维阵列9x9网格

如果一个单元格被占用，它将使用1来表示…
每一次必须有9个细胞被使用…

如何编写一些代码来生成9x9图中9个“1”的所有不同组合？

最佳答案

对于n选择k问题，嵌套循环不是一个好主意：
如果只需要占用2个单元格，可以这样做（伪代码）：

for(int i= 0; i < grid.length*grid[0]*length; i++){
    for(int j = i + 1; j < grid.length*grid[0]*length; j++){
        // Build grid with cells i and j occupied
    }
}

有了3，你必须这样做：

for(int i= 0; i < grid.length*grid[0]*length; i++){
    for(int j = i + 1; j < grid.length*grid[0]*length; j++){
        for(int j = k + 1; k < grid.length*grid[0]*length; k++){
            // Build grid with cells i, j and k occupied
        }
    }
}

…我想你现在看到了问题，如果有9个单元格被占用，你将有9个嵌套循环（讨厌的），更重要的是，你的代码对占用单元格的任何其他值都无效。
使用递归，我不是为你做的，但这里有一个线索：
递归的目的是将问题减少很多次，使其变得微不足道。这里有什么小案子？
n-choose-1很简单，它是n。

// This function calculates n-choose-k
public static int nchoosek(int n, int k){
    if(k == 1){
        return n;
    }else{
            // To come up with this, you need to write down your equation and try
            // to express n-choose-k as a function of n-1-choose-k-1
        return nchoosek(n - 1, k - 1) * n / k;
    }
}