n 要素セットのすべての k 要素サブセットを反復するアルゴリズムを探しています。これらすべてのサブセットを明示的に生成したくありません。
これを行う簡単なアルゴリズムがあります。つまり、対応するビット ベクトルを辞書順に並べ替えてから、現在のサブセットから次のサブセットに移動します。
それにもかかわらず、各ステップで 2 ビットのみを切り替えるアルゴリズムを探しています。そのようなコードは「グレイコード」と呼ばれていることを読みましたが、問題のアルゴリズムが見つかりませんでした。
これには簡単な実装がありますか？
これは完全な答えにはなりませんが、コメントにも収まりません。
必要なグレーコードとの関係はミラーリングです。グレイ コードが新しいビットを設定するたびに、その下のすべてのビットがその時点から逆方向に進みます(そのビットがクリアされるか、反転が反転するビットより上になるまで)。
辞書式順序でこれを再現するには、各スワップ後に残りのビットを反復処理する順序を逆にする必要があります。
これを反復変換として実装し、通常の順序を取り、1 から 0 への遷移が発生するたびに残りのビットの順序を繰り返し逆にすることができる場合があります。