0

次のように、関係する要素の数 (M) によって数 (N) の可能なパーティションの 1 つを見つける必要があります。

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

呼び出し P(4, 2) に対して次の結果を返す関数 P(N, M) を作成する必要があります。

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

関数 partitionWithNElements にもう 1 つのパラメーターを指定しても問題ありませんか? このパラメータは LIST > 型を持つことができます。したがって、リストを返す代わりに、使用する変数を介して直接取得できます。

関数は次のようになります: public void partitionWithNElements(int n, int numberOfElements, List > result) { //同じことですが、見つかった値を結果リストにプッシュします。}

于 2014-04-14T19:49:12.250 に答える
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 に答える