c++ - 単一のセットからすべてのサブセットを生成する

Question

1つのセットからすべてのサブセットを生成するコードを理解しようとしていました。これがコードです

#include <stdio.h>

/* Applies the mask to a set like {1, 2, ..., n} and prints it */
void printv(int mask[], int n) {
    int i;
    printf("{ ");
    for (i = 0; i < n; ++i)
        if (mask[i])
            printf("%d ", i + 1); /*i+1 is part of the subset*/
    printf("\\b }\\n");
}

/* Generates the next mask*/
int next(int mask[], int n) {
    int i;
    for (i = 0; (i < n) && mask[i]; ++i)
        mask[i] = 0;

    if (i < n) {
        mask[i] = 1;
        return 1;
    }
    return 0;
}

int main(int argc, char *argv[]) {
    int n = 3;

    int mask[16]; /* Guess what this is */
    int i;
    for (i = 0; i < n; ++i)
        mask[i] = 0;

    /* Print the first set */
    printv(mask, n);

    /* Print all the others */
    while (next(mask, n))
        printv(mask, n);

    return 0;
}

for (i = 0; (i < n) && mask[i]; ++i)次の関数内のこの行の背後にあるロジックがわかりません。ここで次のマスクはどのように生成されますか？

コードとアルゴリズムはここで見ました：http： //compprog.wordpress.com/2007/10/10/generated-subsets/

score 6 · Accepted Answer

これは、バイナリでのカウントの実装にすぎません。基本的な考え方は、最下位（最後）のゼロを1に変更し、その後のすべてのゼロをゼロに変更することです。「次の」マスクは、2進数として解釈された場合、前のマスクよりも「1つ多く」なります。

配列は自分の場所が最初に配置されるため、従来の数値表記とは逆になります。

ブール値の配列を使用する代わりに、1つの数値と++演算子の2進表現のビットを使用することもできます。

int next(int &mask, int n) { // using C++ reference
    if ( mask == ( 1u << n ) - 1 ) return 0;
    ++ mask;
    return 1;
}

void printv(int mask, int n) {
    int i;
    printf("{ ");
    for (i = 0; i < n; ++i)
        if (mask & ( 1 << i ) )
            printf("%d ", i + 1); /*i+1 is part of the subset*/
    printf("\\b }\\n");
}

質問にそのようにタグを付けたので、私は少しC ++を使用しましたが、投稿されたコードはプレーンCです。

score 2 · Accepted Answer

昨年、私は第6回ITATコンペティションのC言語コンテストに参加し、マスクを使用してすべての組み合わせを生成することで2番目の問題を解決しました（ただし、その問題の最適な解決策ではない可能性があります）。

のすべてのサブセットを導出しようとすると{a,b,c}、次のようになります。

あなたは最初の要素を取るかもしれないし、取らないかもしれませんa。
2番目の要素を取る場合と取らない場合がありますb。
についても同じですc。

したがって、3つのテイクまたはノーテイクの選択肢のセットになります。これは、バイナリまたはブール値で表すことができます。で取得することを表し、。1で取得しないことを表します0。

次の8つのマスクを取得します:(の順序でa,b,c）

000 100 010 110 001 101 011 111

次のマスクを生成するには110：

要素0は1です。に切り替えます0。
要素1は1です。に切り替えます0。
要素2は0です。に切り替えます1。
001これで、サブセットを生成する次のマスクができました{c}。

for (i = 0; (i < n) && mask[i]; ++i)まさにそれをします。

要素0から開始します。
while（iマスクの長さを超えず、要素iは1）
0iを、および++ iに反転する本文コードを実行します（次の要素に移動します）。goto 2（チェック）。

現在のマスクが111（最後のマスク）の場合、next()関数は単に1ENDを示すために戻ります。

（PSゼロ以外の整数は常に真を表します。）

score 0 · Accepted Answer

質問のループは配列の先頭から始まり、0が検出されるまですべての1を0に設定します。次のステートメントは、この0を1に設定します（可能な場合）。つまり、次のようになります。0,0,0-> 1,0,0-> 0,1,0-> 1,1,0-> 0,0,1 ...私はハードコアCプログラマーではありませんが、私はこれは、ビットフィールドを使用し、1ずつ繰り返しインクリメントすることで簡単に実行できたと思います。

score 0 · Accepted Answer

for (i = 0; (i < n) && mask[i]; ++i)

にとって：
0から開始し、毎回iを1ずつ増やします
iがn未満で、位置iのマスク配列のビットが設定されている間は停止しないでください

それは本当に簡単です：forステートメントの3つの部分：初期状態。終了条件; 手術。

したがって、for (i=0; i < 5; i++)平均が0から始まり、5未満にならなくなるまで、毎回iを1ずつインクリメントすることを理解できれば、質問したより複雑なforループを理解できます。

この場合、ループを通過して、設定されていないマスクの最初の要素を探し、各要素をクリアしてから、他の操作を実行します。つまり、マスクビットが設定されておらず、最後に到達した場合です。アレイの。配列の1つの要素のみを順番に1に設定して、結果を取得する簡単な方法のように思えます：100、010、001

c++ - 単一のセットからすべてのサブセットを生成する

4 に答える 4

Related

Reference