5

私は、再帰的に1,2,3,4と言うことができるすべての可能な組み合わせで満たされた2次元配列リストを作成しようとしています. ダブルアップなし。

例えば。
1,0,0
2,0,0
3,0,0
4,0,0
1,2,0
1,3,0
1,4,0
​​ 1,2,3
など...

これまでのところ私は持っています

//this gives me all my numbers
for(int i =0;i<arraySize;i++)
index[i] = i;

// and is the part that make the combinations
for(int i = 0;i<arraySize;i++){
   for(int x = 0;x<k;x++)
      combinations.get(i).set(x, index[i]);

編集:また、結果を印刷しようとはしていません。結果を2次元配列に保存したい

4

3 に答える 3

2

別の非再帰的なオプション。（部分的な）順列には「単語」を使用し、数値には「記号」を使用します。

/**
 * Expands the set of existing words by adding non-repeated symbols to their right
 * @param symbols to choose from
 * @param existing words (may include the empty word)
 * @param expanded result 
 */
public static void expand(ArrayList<Integer> symbols, 
        ArrayList<ArrayList<Integer>> existing, 
        ArrayList<ArrayList<Integer>> expanded) {
    for (ArrayList<Integer> prev : existing) {
        Integer last = prev.isEmpty() ? null : prev.get(prev.size()-1);
        for (Integer s : symbols) {
            if (last == null || s > last) {
                ArrayList<Integer> toAdd = new ArrayList<>(prev);
                toAdd.add(s);
                expanded.add(toAdd);
            }
        }
    }
}

public static void main(String[] args) {

    ArrayList<Integer> symbols = new ArrayList<>(
            Arrays.asList(new Integer[]{1, 2, 3, 4}));

    ArrayList<ArrayList<Integer>> prev = new ArrayList<>();
    ArrayList<ArrayList<Integer>> next = new ArrayList<>();
    ArrayList<ArrayList<Integer>> aux;
    ArrayList<ArrayList<Integer>> output = new ArrayList<>();
    // add empty
    prev.add(new ArrayList<Integer>());
    // expand empty, then expand that expansion, and so on and so forth
    for (int i=0; i<symbols.size(); i++) {
        expand(symbols, prev, next);
        output.addAll(next);
        aux = prev; prev = next; next = aux;
        next.clear();
    }
    // print result (note: only for debugging purposes)
    for (ArrayList<Integer> o : output) {
        for (int i : o) System.out.print(i);  System.out.println();
    }
}

そして、出力は元の質問と一致します（少なくとも提供された例によれば、実際の順列を求めているようには見えません）：

1
2
3
4
12
13
14
23
24
34
123
124
134
234
1234
于 2013-10-29T11:30:32.710 に答える
0

Java でのコレクションの操作に関する一般的なヒントとして、Google Guavaのユーティリティ クラスを調べて、理解できないパフォーマンスの問題が発生していないことを確認することをお勧めします。

次に、次のステップは、ニーズに合った方法を見つけることです。たとえば、Collections2.permutationsが探しているものかもしれません。

最後に、アルゴリズムの演習としてこれを自分で実装したい場合は、guava または Groove Collection API のソースを参照してアイデアを得ることができます。

于 2013-10-29T08:54:45.700 に答える