algorithm - 文字セットのサブセットを作成するための最良の解決策は何ですか？

Question

私は「最良」が主観的であることを知っているので、あなたによると、次の問題の最良の解決策は何ですか？

長さnの文字列（「abc」など）が与えられた場合、文字列の適切なサブセットをすべて生成します。したがって、この例では、出力は{}、{a}、{b}、{c}、{ab}、{bc}、{ac}になります。{abc}。

どう思いますか？

Answer 1

パワーセットが必要です。再帰的かつ帰納的に計算できます。;-)

Answer 2

再帰的アプローチ -- 「abc」のサブセットには 2 つのタイプがあります。「bc」のサブセットと「a」に「bc」のサブセットを加えたものです。したがって、「bc」のサブセットを知っていれば、簡単です。

あるいは、長さ n の文字列には 2^n 個のサブセットがあります。したがって、ネストされた 2 つのループを記述します。i は 0 から 2^n -1 までカウントし (サブセットの場合)、j は 0 から n-1 までカウントします (i 番目のサブセットの文字の場合)。i の j 番目のビットが 1 の場合にのみ、文字列の j 番目の文字を出力します。

（まあ、「最高」は主観的だとおっしゃいましたが…）

Answer 3

サブセットに含まれる要素を示すものとして、2進表現の数値を解釈します。セットに3つの要素があると仮定しましょう。数値4は2進表記の0100に対応するため、これを2番目の要素のみを含むサイズ1のサブセットとして解釈します。このように、すべてのサブセットを生成すると、（2 ^ n）-1までカウントされます。

    char str [] = "abc";
    int n = strlen(str); // n is number of elements in your set

    for(int i=0; i< (1 << n); i++) { // (1 << n) is equal to 2^n
        for(int j=0; j<n; j++) { // For each element in the set
            if((i & (1 << j)) > 0) { // Check if it's included in this subset. (1 << j) sets the jth bit
                cout << str[j];
            }
        }
        cout << endl;
    }

Answer 4

def subsets(s):
    r = []
    a = [False] * len(s)
    while True:
        r.append("".join([s[i] for i in range(len(s)) if a[i]]))
        j = 0
        while a[j]:
            a[j] = False
            j += 1
            if j >= len(s):
                return r
        a[j] = True

print subsets("abc")

Answer 5

擬似コードを許してください...

int i = 0;
Results.push({});

While(i > Inset.Length) {
   Foreach(Set s in Results) {
    If(s.Length == i) {
       Foreach(character c in inSet)
          Results.push(s+c);
    }
    i++;
}