java - 如何计算数字的无序分区数

Question

我真的被这个问题困住了。

在这个问题中，给你一 block 2xN 的板。您需要以这种方式在此板上填写非负数，即:

1. 所有填入的数字之和=N
2. 2 行中的每一行由非递增顺序的数字组成
3. N 个中的每一个列由非递增顺序的数字组成。

给定数字 N，有多少种方法可以做到这一点？如果板上有一个单元格具有不同的编号，则两种方式被认为是不同的。

输出应该是可以形成矩阵的方式的数量。矩阵可以有重复的数字，可以使用零。矩阵不应该有递增的数字，但相等的数字可以并排填充。

例子:

输入->5

输出->16

Answer 1

根据您的示例(输入=5，输出=16)，我想只允许使用整数。

一种天真的(蛮力)解决方案是使用回溯算法:

http://en.wikipedia.org/wiki/Backtracking

在此站点上，您可以看到在找到解决方案之前填充数独板的示例。

==

例如:

您有大小为 2N 的整数数组。

For position 0 you take first free number. 
If solution is not broken yet you go to position 1 of array.
If solution is broken - stop as cannot back anymore

  For position 1 you take next free number.
  If solution is not broken you you go to position 2 of array.
  If solution is broken you back to previous sten and take next free number.

    For position 2...

这通常是通过递归完成的。我认为，在每个位置(递归级别)上，数字都可以从池 0..N 中获取。

尝试 - 祝你好运。

编辑:

这是有效的解决方案(使用回溯算法):

private final int N = 5;

// 2 rows in one array [0..N-1, N..2N-1]
private int[] board = new int[2 * N];

// found solution counter
int found = 0;

/*
 * this method set next number to current position
 * and recursively go to next position.
 */
public void check(int position) {

    // if board is complete - check if valid
    if (position == 2 * N) {
        if (isValid()) {
            System.out.println("foun : " + Arrays.toString(board));
            found++;
        }
        return;
    }


    // if board is not complete - put all numbers (0..N) into current position
    // and recursively go to next position
    for (int v = 0; v <= N; v++) {
        board[position] = v;

        // if solution is already broken - step backwards
        // see: backtracking algorithms
        if (isBroken(position)) {
            return;
        }

        check(position + 1);
    }
}

public boolean isValid() {

    // condition 1
    int sum = 0;
    for (int i = 0; i < board.length; i++) {
        sum += board[i];
    }
    if (sum != N) {
        return false;
    }

    // conditin 2
    int prev = board[0];
    for (int i = 1; i < N; i++) {
        if (board[i] > prev) {
            return false;
        }
        prev = board[i];
    }
    prev = board[N];
    for (int i = N + 1; i < 2 * N; i++) {
        if (board[i] > prev) {
            return false;
        }
        prev = board[i];
    }

    // condition 3
    for (int i = 0; i < N; i++) {
        int top = board[i];
        int bottom = board[i + N];
        if (top < bottom) {
            return false;
        }
    }

    // valid
    return true;
}

// simplified version of this method - but correct
public boolean isBroken(int current) {
    int sum = 0;
    for (int i = 0; i <= current; i++) {
        sum += board[i];
    }
    return sum > N;
}

public void start() {
    check(0);
    System.out.println("found: " + found);
}

N = 5 的程序输出:

found : [1, 1, 1, 0, 0, 1, 1, 0, 0, 0]
found : [1, 1, 1, 1, 0, 1, 0, 0, 0, 0]
found : [1, 1, 1, 1, 1, 0, 0, 0, 0, 0]
found : [2, 1, 0, 0, 0, 1, 1, 0, 0, 0]
found : [2, 1, 0, 0, 0, 2, 0, 0, 0, 0]
found : [2, 1, 1, 0, 0, 1, 0, 0, 0, 0]
found : [2, 1, 1, 1, 0, 0, 0, 0, 0, 0]
found : [2, 2, 0, 0, 0, 1, 0, 0, 0, 0]
found : [2, 2, 1, 0, 0, 0, 0, 0, 0, 0]
found : [3, 0, 0, 0, 0, 2, 0, 0, 0, 0]
found : [3, 1, 0, 0, 0, 1, 0, 0, 0, 0]
found : [3, 1, 1, 0, 0, 0, 0, 0, 0, 0]
found : [3, 2, 0, 0, 0, 0, 0, 0, 0, 0]
found : [4, 0, 0, 0, 0, 1, 0, 0, 0, 0]
found : [4, 1, 0, 0, 0, 0, 0, 0, 0, 0]
found : [5, 0, 0, 0, 0, 0, 0, 0, 0, 0]
found: 16