私は面接のために勉強していて、オンラインの「数学」カテゴリでこの質問を見つけました。
指定されたセットのべき乗セットを生成します。
int A[] = {1,2,3,4,5};
int N = 5;
int Total = 1 << N;
for ( int i = 0; i < Total; i++ ) {
for ( int j = 0; j < N; j++) {
if ( (i >> j) & 1 )
cout << A[j];
}
cout <<endl;
}
明確な答えは望まないでください。この問題に取り組む方法についての説明とヒントが欲しいだけです。
Google でパワー セット アルゴリズムを確認しましたが、この問題に対処する方法がまだわかりません。
また、誰かが質問が求めていることを繰り返してもらえますか.
ありがとうございました。
Power set of a set A is the set of all of the subsets of A.
世界で最も友好的な定義ではありませんが、例が役立ちます：
例えば。の{1, 2}場合、サブセットは次のとおりです。{}, {1}, {2}, {1, 2}
したがって、パワーセットは{{}, {1}, {2}, {1, 2}}
この決定をビット (1/0) で示します。
したがって、 を生成する{1}には、ピック1アンド ドロップします2(10)。
同様の行で、すべてのサブセットのビット ベクトルを記述できます。
繰り返しますが、元のセットの要素の一部またはすべてを含めることによって形成された場合のサブセット。したがって、サブセットを作成するには、各要素に移動し、それを保持するか削除するかを決定します。これは、要素ごとに 2 つの決定があることを意味します。したがって、セットの場合、異なるサブセット2^Nに対応する異なる決定になる可能性があります。2^N
ここから拾えるかどうかを確認してください。
次のパワーセットを作成します
{"A", "B", "C"}。
擬似コード:
val set = {"A", "B", "C"}
val sets = {}
for item in set:
for set in sets:
sets.add(set + item)
sets.add({item})
sets.add({})
アルゴリズムの説明:
1)sets空のセットに初期化します: {}.
2）各アイテムを繰り返します{"A", "B", "C"}
3）あなたのそれぞれsetを繰り返しますsets。
3.1) のコピーである新しいセットを作成しますset。
3.2) を に追加itemしnew setます。
3.3) を に追加new setしsetsます。
4) を に追加itemしますsets。
4) 反復が完了します。に空のセットを追加しますresultSets。
チュートリアル:
sets各反復後の内容を見てみましょう。
反復 1、項目 = "A":
sets = {{"A"}}
反復 2、項目 = "B":
sets = {{"A"}, {"A", "B"}, {"B"}}
反復 3、項目 = "C":
sets = {{"A"}, {"A", "B"}, {"B"}, {"A", "C"}, {"A", "B", "C"}, {"B", "C"}, {"C"}}
反復が完了し、空のセットを追加:
sets = {{"A"}, {"A", "B"}, {"B"}, {"A", "C"}, {"A", "B", "C"}, {"B", "C"}, {"C"}, {}}
セットのサイズは 2^|set| です。= 2^3 = 8 これは正しいです。
Java での実装例:
public static <T> List<List<T>> powerSet(List<T> input) {
List<List<T>> sets = new ArrayList<>();
for (T element : input) {
for (ListIterator<List<T>> setsIterator = sets.listIterator(); setsIterator.hasNext(); ) {
List<T> newSet = new ArrayList<>(setsIterator.next());
newSet.add(element);
setsIterator.add(newSet);
}
sets.add(new ArrayList<>(Arrays.asList(element)));
}
sets.add(new ArrayList<>());
return sets;
}
入力： [A, B, C]
出力：[[A], [A, C], [A, B], [A, B, C], [B], [B, C], [C], []]
さて、すべてのサブセットを生成する必要があります。サイズ n のセットには、2 n 個のサブセットがあります。
1 つの方法は、0 から 2 n - 1 までの数値を反復処理し、それぞれを 2 進数のリストに変換することです。ここで、0手段はその要素を除外し、1手段はそれを含めます。
もう 1 つの方法は、再帰、分割、および征服です。
C# ソリューション
時間の複雑さと空間の複雑さ: O(n*2^n)
public class Powerset
{
/*
P[1,2,3] = [[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]
*/
public List<List<int>> PowersetSoln(List<int> array)
{
/*
We will start with an empty subset
loop through the number in the array
loop through subset generated till and add the number to each subsets
*/
var subsets = new List<List<int>>();
subsets.Add(new List<int>());
for (int i = 0; i < array.Count; i++)
{
int subsetLen = subsets.Count;
for (int innerSubset = 0; innerSubset < subsetLen; innerSubset++)
{
var newSubset = new List<int>(subsets[innerSubset]);
newSubset.Add(array[i]);
subsets.Add(newSubset);
}
}
return subsets;
}
}
最高評価の回答を実装すると、このようなものが得られます。
def printPowerSet(set,set_size):
# set_size of power set of a set
# with set_size n is (2**n -1)
pow_set_size = (int) (math.pow(2, set_size));
counter = 0;
j = 0;
# Run from counter 000..0 to 111..1
for counter in range(0, pow_set_size):
for j in range(0, set_size):
# Check if jth bit in the
# counter is set If set then
# pront jth element from set
if((counter & (1 << j)) > 0):
print(set[j], end = "");
print("");
サンプル Java コード:
void printPowerSetHelper(String s, String r) {
if (s.length() > 0) {
printPowerSetHelper(s.substring(1), r + s.charAt(0));
printPowerSetHelper(s.substring(1), r);
}
if (r.length() > 0) System.out.println(r);
}
void printPowerSet(String s) {
printPowerSetHelper(s,"");
}