0

我需要通过所涉及的元素数 (M) 找到数字 (N) 的可能分区之一，如下所示：

Number 4
Partitions
4
3 1
2 2
2 1 1
1 3
1 1 1 1

我需要创建一个函数 P(N, M)，它将为调用 P(4, 2) 返回以下结果：

3 1
2 2
1 3

我创建了以下方法，但我找不到打破每个分区之间界限的方法：

List<String> partitions;

public String[] partitionWithNElements(int n, int numberOfElements) {
    partitions = new ArrayList<String>();
    partition(n, n, "");

    String[] arrayPartition = null;

    for (int i = 0; i < partitions.size(); i++) {
        arrayPartition = partitions.get(i).split("#");
        if (arrayPartition.length == numberOfElements)
            break;
    }

    return arrayPartition;
}

private void partition(int n, int max, String prefix) {
    if (n == 0) {
        if (prefix.startsWith("#"))
            prefix = prefix.substring(1);

        partitions.add(prefix);
        return;
    }

    for (int i = Math.min(max, n); i >= 1; i--) {
        partition(n - i, i, prefix + "#" + i);
    }
}

代码再次更新。现在我使用字符串来返回元素并且我已经能够达到预期的结果，但是我试图找到一个不使用字符串来返回分区的解决方案，所以我不需要使用字符串拆分功能。

4

2 回答 2

0

只需将所需大小的分区复制到另一个列表，然后返回。

public List<List<Integer>> partitionWithNElements(int n, int numberOfElements) {
    List<List<Integer>> elements = new ArrayList<List<Integer>>();
    List<List<Integer>> result = new ArrayList<List<Integer>>();

    partition(n, n, elements, null);

    List<List<Integer>> result = new ArrayList<List<Integer>>();

    for (int i = 0; i < elements.size(); i++) {
        if (elements.get(i).size() == numberOfElements) {
            result.add(elements.get(i));
        }
    }

    return result;
}
于 2014-04-14T19:45:24.970 回答
0

可以在函数 partitionWithNElements 中再多一个参数吗？此参数的类型可以是 LIST >。因此，您可以通过使用的变量直接获取它，而不是返回列表。

函数可以是： public void partitionWithNElements(int n, int numberOfElements, List > result) { //和你做的一样，但是把你找到的值推到结果列表中。}

于 2014-04-14T19:49:12.250 回答