math - 计算给定长度的网格中可能的排列？

Question

我有一个充满字母的 4x4 网格。如何计算从任意点到任意点的所有可能路线，由 2 到 10 个点组成？

route 的所有点必须垂直、水平或对角连接到同一 route 的​​另一个点。例如，您可以从 A 到 B、A 到 E 和 A 到 F，但不能从 A 到 C。

每个点在一条 route 只能使用一次。

这是 25 种可能排列的示例:

+---+---+---+---+
| A | B | C | D |
+---+---+---+---+
| E | F | G | H |
+---+---+---+---+
| I | J | K | L |
+---+---+---+---+
| M | N | O | P |
+---+---+---+---+

- AB
- ABC
- ABCD
- ABCDH
- ABCDHG
- ABCDHGF
- ABCDHGFE
- ABCDHGFEI
- ABCDHGFEIJ
- AE
- AEI
- AEIM
- AEIMN
- AEIMNJ
- AEIMNJF
- AIEMNJFB
- AIEMNJFBC
- AIEMNJFBCG
- AFKP
- PONM
- FGKL
- NJFB
- MNJGD

现在我应该澄清问题了。我不是在问如何获得所有排列。我想问的是可能的排列总数(即整数)是多少以及如何计算它。

Answer 1

正如评论中提到的，这个问题可以用 java 中的基本 DFS 从左上角 (0,0) 开始回答

编辑:我为约束添加了 if(count(visited)>10) return;

static int count=0;

static int count(boolean[][] b){
    int r = 0;
    for(int i=0;i<b.length;i++){
        for(int j=0;j<b[0].length;j++){
            if(b[i][j]) r++;
        }
    }
    return r;
}

static boolean[][] copy(boolean[][] arr){
    boolean [][] r = new boolean[arr.length][];
    for(int i = 0; i < arr.length; i++)
        r[i] = arr[i].clone();
    return r;
}

static void dfs(int i, int j,boolean[][] visited) {
    visited[i][j] = true;
    if(count(visited)>10) return;
    count++;
    for (int k=-1;k<2;k++) {
        for (int l=-1;l<2;l++) {
            int r = i+k;
            int c = j+l;
            if (r>-1 && r<visited.length && c>-1 && c<visited.length && !visited[r][c]){
                dfs(r,c,copy(visited));
            }
        }
    }
}

public static void main(String args[]) {

    boolean[][] visited = {
            {false, false, false, false},
            {false, false, false, false},
            {false, false, false, false},
            {false, false, false, false}
    };
    // dfs(row,column,initialize all to false)
    dfs(0,0,visited);
    System.out.println(count-1);

}

上面的脚本只是遍历每个排列并每次递增 count 因为这包括起点(例如 (0,0))我在底部count-1

输出:105837(根据我不正确的原始 1012519 编辑)

对于从同一个地方开始的 2x2，我得到 15。你可以从运行中看到

static int count=0;

static int count(boolean[][] b){
    int r = 0;
    for(int i=0;i<b.length;i++){
        for(int j=0;j<b[0].length;j++){
            if(b[i][j]) r++;
        }
    }
    return r;
}

static boolean[][] copy(boolean[][] arr){
    boolean [][] r = new boolean[arr.length][];
    for(int i = 0; i < arr.length; i++)
        r[i] = arr[i].clone();
    return r;
}

static void dfs(int i, int j,boolean[][] visited,String str) {
    visited[i][j] = true;
    if (count(visited)>10) return;
    count++;

    str+="("+i+","+j+")";
    System.out.println(str+": "+count);

    for (int k=-1;k<2;k++) {
        for (int l=-1;l<2;l++) {
            int r = i+k;
            int c = j+l;
            if (r>-1 && r<visited.length && c>-1 && c<visited.length && !visited[r][c]){
                dfs(r,c,copy(visited),str);
            }
        }
    }
}

public static void main(String args[]) {

    boolean[][] visited = {
            {false, false},
            {false, false}
    };

    dfs(0,0,visited,"");
    // "count-1" to account for the starting position
    System.out.println(count-1);

}

输出:

(0,0): 1
(0,0)(0,1): 2
(0,0)(0,1)(1,0): 3
(0,0)(0,1)(1,0)(1,1): 4
(0,0)(0,1)(1,1): 5
(0,0)(0,1)(1,1)(1,0): 6
(0,0)(1,0): 7
(0,0)(1,0)(0,1): 8
(0,0)(1,0)(0,1)(1,1): 9
(0,0)(1,0)(1,1): 10
(0,0)(1,0)(1,1)(0,1): 11
(0,0)(1,1): 12
(0,0)(1,1)(0,1): 13
(0,0)(1,1)(0,1)(1,0): 14
(0,0)(1,1)(1,0): 15
(0,0)(1,1)(1,0)(0,1): 16
15

具有 4x4 而不是最后 6 行输出的相同脚本是:

(0,0)(1,1)(2,2)(3,3)(3,2)(3,1)(3,0)(2,1)(1,2)(0,3): 105834
(0,0)(1,1)(2,2)(3,3)(3,2)(3,1)(3,0)(2,1)(1,2)(1,3): 105835
(0,0)(1,1)(2,2)(3,3)(3,2)(3,1)(3,0)(2,1)(1,2)(2,3): 105836
(0,0)(1,1)(2,2)(3,3)(3,2)(3,1)(3,0)(2,1)(2,0): 105837
(0,0)(1,1)(2,2)(3,3)(3,2)(3,1)(3,0)(2,1)(2,0)(1,0): 105838
105837