現在、私は配列と整数nを取り、各サイズnの組み合わせのリスト（つまり、int配列のリスト）を提供する関数を記述しようとしています。n個のネストされたループを使用してそれを書くことができますが、これはサブセットの特定のサイズでのみ機能します。どのようなサイズの組み合わせでも機能するように一般化する方法がわかりません。再帰を使用する必要があると思いますか？
これは3つの要素のすべての組み合わせのコードであり、任意の数の要素のアルゴリズムが必要です。
import java.util.List;
import java.util.ArrayList;
public class combinatorics{
public static void main(String[] args) {
List<int[]> list = new ArrayList<int[]>();
int[] arr = {1,2,3,4,5};
combinations3(arr,list);
listToString(list);
}
static void combinations3(int[] arr, List<int[]> list){
for(int i = 0; i<arr.length-2; i++)
for(int j = i+1; j<arr.length-1; j++)
for(int k = j+1; k<arr.length; k++)
list.add(new int[]{arr[i],arr[j],arr[k]});
}
private static void listToString(List<int[]> list){
for(int i = 0; i<list.size(); i++){ //iterate through list
for(int j : list.get(i)){ //iterate through array
System.out.printf("%d ",j);
}
System.out.print("\n");
}
}
}
これは、すべてのkサブセットまたはk組み合わせを生成するというよく研究された問題であり、再帰なしで簡単に実行できます。
アイデアは、入力配列（からまでの番号）からの要素kのインデックスのシーケンスを昇順で維持するサイズの配列を持つことです。（サブセットは、最初の配列からこれらのインデックスでアイテムを取得することによって作成できます。）したがって、そのようなインデックスシーケンスをすべて生成する必要があります。0n - 1
最初のインデックスシーケンスはになり[0, 1, 2, ... , k - 1]、2番目のステップでに切り替わり[0, 1, 2,..., k]、次にに切り替わります[0, 1, 2, ... k + 1]。最後の可能なシーケンスはになります[n - k, n - k + 1, ..., n - 1]。
各ステップで、アルゴリズムは、インクリメントできる最終アイテムに最も近いものを探し、それをインクリメントして、そのアイテムまでのアイテムを埋めます。
説明するために、とを検討n = 7しk = 3ます。最初のインデックスシーケンスは[0, 1, 2]、それ以降も同様[0, 1, 3]です...ある時点で、次のようになります[0, 5, 6]。
[0, 5, 6] <-- scan from the end: "6" cannot be incremented, "5" also, but "0" can be
[1, ?, ?] <-- "0" -> "1"
[1, 2, 3] <-- fill up remaining elements
next iteration:
[1, 2, 3] <-- "3" can be incremented
[1, 2, 4] <-- "3" -> "4"
したがって、[0, 5, 6]が続き[1, 2, 3]、その後が続きます[1, 2, 4]。
コード：
int[] input = {10, 20, 30, 40, 50}; // input array
int k = 3; // sequence length
List<int[]> subsets = new ArrayList<>();
int[] s = new int[k]; // here we'll keep indices
// pointing to elements in input array
if (k <= input.length) {
// first index sequence: 0, 1, 2, ...
for (int i = 0; (s[i] = i) < k - 1; i++);
subsets.add(getSubset(input, s));
for(;;) {
int i;
// find position of item that can be incremented
for (i = k - 1; i >= 0 && s[i] == input.length - k + i; i--);
if (i < 0) {
break;
}
s[i]++; // increment this item
for (++i; i < k; i++) { // fill up remaining items
s[i] = s[i - 1] + 1;
}
subsets.add(getSubset(input, s));
}
}
// generate actual subset by index sequence
int[] getSubset(int[] input, int[] subset) {
int[] result = new int[subset.length];
for (int i = 0; i < subset.length; i++)
result[i] = input[subset[i]];
return result;
}
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加