再帰は、このタスクの友です。
要素ごとに、それが現在のサブセットにあるかどうかを「推測」し、その推測と、選択できる小さなスーパーセットを使用して再帰的に呼び出します。「はい」と「いいえ」の両方の推測に対してこれを行うと、可能なすべてのサブセットが得られます。
特定の長さに自分を抑えることは、stop 節で簡単に行うことができます。
Java コード:
private static void getSubsets(List<Integer> superSet, int k, int idx, Set<Integer> current,List<Set<Integer>> solution) {
//successful stop clause
if (current.size() == k) {
solution.add(new HashSet<>(current));
return;
}
//unseccessful stop clause
if (idx == superSet.size()) return;
Integer x = superSet.get(idx);
current.add(x);
//"guess" x is in the subset
getSubsets(superSet, k, idx+1, current, solution);
current.remove(x);
//"guess" x is not in the subset
getSubsets(superSet, k, idx+1, current, solution);
}
public static List<Set<Integer>> getSubsets(List<Integer> superSet, int k) {
List<Set<Integer>> res = new ArrayList<>();
getSubsets(superSet, k, 0, new HashSet<Integer>(), res);
return res;
}
呼び出し:
List<Integer> superSet = new ArrayList<>();
superSet.add(1);
superSet.add(2);
superSet.add(3);
superSet.add(4);
System.out.println(getSubsets(superSet,2));
生成されます:
[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
セットのビット ベクトル表現を使用し、std::next_permutation が 0000.1111 に対して行うのと同様のアルゴリズムを使用します (0 が nk、1 が k)。各順列は、サイズ k のサブセットに対応します。
私の解決策を確認してください：-
private static void printPermutations(List<Integer> list, int subSetSize) {
List<Integer> prefixList = new ArrayList<Integer>();
printPermutations(prefixList, list, subSetSize);
}
private static void printPermutations(List<Integer> prefixList, List<Integer> list, int subSetSize) {
if (prefixList.size() == subSetSize) {
System.out.println(prefixList);
} else {
for (int i = 0; i < list.size(); i++) {
Integer removed = list.remove(i);
prefixList.add(removed);
printPermutations(prefixList, list, subSetSize);
prefixList.remove(removed);
list.add(i, removed);
}
}
}
これは文字列順列に似ています:-
private static void printPermutations(String str) {
printAllPermutations("", str);
}
private static void printAllPermutations(String prefix, String restOfTheString) {
int len = restOfTheString.length();
System.out.println(prefix);
for (int i = 0; i < len; i++) {
printAllPermutations(prefix + restOfTheString.charAt(i), restOfTheString.substring(0, i) + restOfTheString.substring(i + 1, len));
}
}
これはpythonの反復バージョンです。その本質は、可能なすべての組み合わせを返す increment_counters() 関数です。C(n,r) 回呼び出す必要があることはわかっています。
def nchooser(n,r):
"""Calculate the n choose r manual way"""
import math
f = math.factorial
return f(n) / f(n-r) / f(r)
def increment_counters(rc,r,n):
"""This is the essense of the algorithm. It generates all possible indexes.
Ex: for n = 4, r = 2, rc will have values (0,1),(0,2),(0,3),(1,2),(1,3),(2,3).
You may have better understanding if you print all possible 35 values for
n = 7, r = 3."""
rc[r-1] += 1 # first increment the least significant counter
if rc[r-1] < n: # if it does not overflow, return
return
# overflow at the last counter may cause some of previous counters to overflow
# find where it stops (ex: in n=7,r=3 case, 1,2,3 will follow 0,5,6)
for i in range(r-2,-1,-1): # from r-2 to 0 inclusive
if rc[i] < i+n-r:
break
# we found that rc[i] will not overflow. So, increment it and reset the
# counters right to it.
rc[i] += 1
for j in range(i+1,r):
rc[j] = rc[j-1] + 1
def combinations(lst, r):
"""Return all different sub-lists of size r"""
n = len(lst)
rc = [ i for i in range(r) ] # initialize counters
res = []
for i in range(nchooser(n,r)): # increment the counters max possible times
res.append(tuple(map(lambda k: lst[k],rc)))
increment_counters(rc,r,n)
return res
これは F# での実装です。
// allSubsets: int -> int -> Set<Set<int>>
let rec allSubsets n k =
match n, k with
| _, 0 -> Set.empty.Add(Set.empty)
| 0, _ -> Set.empty
| n, k -> Set.union (Set.map (fun s -> Set.add n s) (allSubsets (n-1) (k-1)))
(allSubsets (n-1) k)
F# REPL で試すことができます。
> allSubsets 3 2;;
val it : Set<Set<int>> = set [set [1; 2]; set [1; 3]; set [2; 3]]
> allSubsets 4 2;;
val it : Set<Set<int>> = set [set [1; 2]; set [1; 3]; set [1; 4]; set [2; 3]; set [2; 4]; set [3; 4]]
この Java クラスは、同じアルゴリズムを実装しています。
import java.util.HashSet;
import java.util.Set;
public class AllSubsets {
public static Set<Set<Integer>> allSubsets(int setSize, int subsetSize) {
if (subsetSize == 0) {
HashSet<Set<Integer>> result = new HashSet<>();
result.add(new HashSet<>());
return result;
}
if (setSize == 0) {
return new HashSet<>();
}
Set<Set<Integer>> sets1 = allSubsets((setSize - 1), (subsetSize - 1));
for (Set<Integer> set : sets1) {
set.add(setSize);
}
Set<Set<Integer>> sets2 = allSubsets((setSize - 1), subsetSize);
sets1.addAll(sets2);
return sets1;
}
}
F# や Java が気に入らない場合は、この Web サイトにアクセスしてください。さまざまなプログラミング言語での特定の問題の解決策がリストされています。
これは、パワーセット内のすべてのセットのバイナリ表現を使用して、Simple が話していると私が思うものの Java バージョンです。Abhiloop Sarkar が行った方法と似ていますが、バイナリ値を表すだけの場合は、文字列よりもブール配列の方が理にかなっていると思います。
private ArrayList<ArrayList<Object>> getSubsets(int m, Object[] objects){
// m = size of subset, objects = superset of objects
ArrayList<ArrayList<Object>> subsets = new ArrayList<>();
ArrayList<Integer> pot = new ArrayList<>();
int n = objects.length;
int p = 1;
if(m==0)
return subsets;
for(int i=0; i<=n; i++){
pot.add(p);
p*=2;
}
for(int i=1; i<p; i++){
boolean[] binArray = new boolean[n];
Arrays.fill(binArray, false);
int y = i;
int sum = 0;
for(int j = n-1; j>=0; j--){
int currentPot = pot.get(j);
if(y >= currentPot){
binArray[j] = true;
y -= currentPot;
sum++;
}
if(y<=0)
break;
}
if(sum==m){
ArrayList<Object> subsubset = new ArrayList<>();
for(int j=0; j < n; j++){
if(binArray[j]){
subsubset.add(objects[j]);
}
}
subsets.add(subsubset);
}
}
return subsets;
}