5

パワーセットでセットを見つけようとしていますn-th。つまり、べき集合は次の順序で生成されます。n-th最初はサイズで、次に辞書式順序で生成されます。したがって、のべき集合の集合のインデックスは次のようになります[a, b, c]。

0 - []
1 - [a]
2 - [b]
3 - [c]
4 - [a, b]
5 - [a, c]
6 - [b, c]
7 - [a, b, c]

解決策を探しているときに見つけたのは、要素のリストのn番目の順列を返すアルゴリズムだけでした。たとえば、ここにあります。

コンテキスト：

要素のベクトルのべき集合全体を取得しようとしていますVが、一度に1つのセットでこれを行う必要があります。

要件：

  • 同時に維持できるのは2つのベクトルのみです。最初のベクトルはリスト内の元のアイテムを含み、2番目のベクトルn-thはのべき集合からのセットVを持ちます。そのため、n-th setここで関数を使用します。
  • これは、ソリューションの空間で線形時間ではなく実行する必要があります。つまり、すべてのセットをリストすることはできず、 n-th1つを選択します。
  • 私の最初のアイデアは、ビットを使用して位置を表し、必要なものの有効なマッピングを取得することです。これは、投稿した「不完全な」ソリューションです。
4

3 に答える 3

5

関数の閉じた形式はありませんが、ビットハッキングの非ループnext_combination関数があります。それが役立つ場合は、歓迎します。ビット マスクを何らかの整数型に適合させることができると想定していますが、これは、64 要素セットに2 64の可能性があることを考えると、おそらく不合理な想定ではありません。

コメントにあるように、この「辞書式順序付け」の定義は少し奇妙だと思います [], [a], [ab], [abc], [ac], [b], [bc], [c]。しかし、以前は「最初にサイズで、次に辞書式」の列挙を行う必要がありました。

// Generate bitmaps representing all subsets of a set of k elements,
// in order first by (ascending) subset size, and then lexicographically.
// The elements correspond to the bits in increasing magnitude (so the
// first element in lexicographic order corresponds to the 2^0 bit.)
//
// This function generates and returns the next bit-pattern, in circular order
// (so that if the iteration is finished, it returns 0).
//
template<typename UnsignedInteger>
UnsignedInteger next_combination(UnsignedInteger comb, UnsignedInteger mask) {
  UnsignedInteger last_one = comb & -comb;
  UnsignedInteger last_zero = (comb + last_one) &~ comb & mask;
  if (last_zero) return comb + last_one + (last_zero / (last_one * 2)) - 1;
  else if (last_one > 1) return mask / (last_one / 2);
  else return ~comb & 1;
}

5 行目は、(拡張された) 正規表現の置換に相当するビット ハッキングを実行しています。これは01、文字列の最後を見つけて反転し、後続のすべての s を右端まで10シフトします。1

s/01(1*)(0*)$/10\2\1/

6行目は、これを実行して（前のものが失敗した場合のみ）、もう1つ追加し、 sを右端まで1シフトします。1

s/(1*)0(0*)/\21\1/

その説明が役立つか妨げになるかはわかりません:)

これは手っ取り早い汚いドライバーです (コマンドライン引数はセットのサイズで、デフォルトは 5 で、符号なし long の最大ビット数です):

#include <iostream>

template<typename UnsignedInteger>
std::ostream& show(std::ostream& out, UnsignedInteger comb) {
  out << '[';
  char a = 'a';
  for (UnsignedInteger i = 1; comb; i *= 2, ++a) {
    if (i & comb) {
      out << a;
      comb -= i;
    }
  }
  return out << ']';
}

int main(int argc, char** argv) {
  unsigned int n = 5;
  if (argc > 1) n = atoi(argv[1]);
  unsigned long mask = (1UL << n) - 1;
  unsigned long comb = 0;
  do {
    show(std::cout, comb) << std::endl;
    comb = next_combination(comb, mask);
  } while (comb);
  return 0;
}

列挙のサイズを考えると、この関数が 64 を超える要素のセットに役立つとは信じがたいですが、3 つの要素のすべてのサブセットなど、一部の限定された部分を列挙するのに役立つ場合があります。この場合、ビットハッカーが実際に役立つのは、変更が 1 つの単語に収まる場合のみです。幸いなことに、これは簡単にテストできます。上記のように、ビットセットの最後の単語に対して、last_zeroゼロであるかどうかのテストまで、計算を実行するだけです。(この場合、 bitand を行う必要はありません。mask実際、セットのサイズを指定する別の方法を選択する必要があるかもしれません。)last_zeroが 0 であることが判明した場合 (これは実際にはかなりまれです)、次のことを行う必要があります。他の方法で変換しますが、原則は同じです:0に先行する最初のものを見つけます10(が単語の末尾にあり、次の単語の先頭にある場合に注意してください1)。を に変更し01、移動する必要がある の10数を把握し、それらを最後まで移動します。1

于 2013-02-05T21:39:02.613 に答える
4

要素のリストを考慮するL = [a, b, c]と、のべき集合は次のL式で与えられます。

P(L) = {
    [],
    [a], [b], [c],
    [a, b], [a, c], [b, c],
    [a, b, c]
}

各位置を少し考えると、次のようなマッピングが得られます。

id  | positions - integer | desired set
 0  |  [0 0 0]  -    0    |  []
 1  |  [1 0 0]  -    4    |  [a]
 2  |  [0 1 0]  -    2    |  [b]
 3  |  [0 0 1]  -    1    |  [c]
 4  |  [1 1 0]  -    6    |  [a, b]
 5  |  [1 0 1]  -    5    |  [a, c]
 6  |  [0 1 1]  -    3    |  [b, c]
 7  |  [1 1 1]  -    7    |  [a, b, c]

ご覧のとおり、idは整数に直接マップされていません。適切なマッピングを適用する必要があるため、次のようになります。

id  | positions - integer |  mapped  - integer
 0  |  [0 0 0]  -    0    |  [0 0 0] -    0
 1  |  [1 0 0]  -    4    |  [0 0 1] -    1
 2  |  [0 1 0]  -    2    |  [0 1 0] -    2
 3  |  [0 0 1]  -    1    |  [0 1 1] -    3
 4  |  [1 1 0]  -    6    |  [1 0 0] -    4
 5  |  [1 0 1]  -    5    |  [1 0 1] -    5
 6  |  [0 1 1]  -    3    |  [1 1 0] -    6
 7  |  [1 1 1]  -    7    |  [1 1 1] -    7

これを解決する試みとして、私はマッピングを行うために二分木を使用することを思いつきました-誰かがそれからの解決策を見ることができるように私はそれを投稿しています：

                                        #
                          ______________|_____________
        a               /                             \
                  _____|_____                   _______|______
        b        /           \                 /              \
              __|__         __|__           __|__            __|__
        c    /     \       /     \         /     \          /     \
           [ ]     [c]    [b]   [b, c]    [a]   [a, c]    [a, b]  [a, b, c]
index:      0       3      2       6       1      5         4         7
于 2013-02-05T17:42:13.953 に答える
2

セットのサイズが N であるとします。

したがって、サイズ k の (N choose k) 個のセットがあります。n が負になるまで、n から off (N choose k) を差し引くだけで、適切な k (つまり、n 番目のセットのサイズ) を非常に迅速に見つけることができます。これにより、問題は N セットの n 番目の k サブセットを見つけることに軽減されます。

Nセットの最初の（N-1はk-1を選択）kサブセットには、最小の要素が含まれます。したがって、n がより小さい場合 (N-1 は k-1 を選択)、最初の要素を選択し、セットの残りを再帰します。それ以外の場合は、(N-1 個の k 個を選択) 他のセットの 1 つがあります。最初の要素を破棄し、n から (N-1 choose k-1) を減算し、再帰します。

コード：

#include <stdio.h>

int ch[88][88];
int choose(int n, int k) {
 if (n<0||k<0||k>n) return 0;
 if (!k||n==k) return 1;
 if (ch[n][k]) return ch[n][k];
 return ch[n][k] = choose(n-1,k-1) + choose(n-1,k);
}

int nthkset(int N, int n, int k) {
 if (!n) return (1<<k)-1;
 if (choose(N-1,k-1) > n) return 1 | (nthkset(N-1,n,k-1) << 1);
 return nthkset(N-1,n-choose(N-1,k-1),k)<<1;
}

int nthset(int N, int n) {
 for (int k = 0; k <= N; k++)
  if (choose(N,k) > n) return nthkset(N,n,k);
  else n -= choose(N,k);
 return -1; // not enough subsets of [N].
}

int main() {
 int N,n;
 scanf("%i %i", &N, &n);
 int a = nthset(N,n);
 for (int i=0;i<N;i++) printf("%i", !!(a&1<<i));
 printf("\n");
}
于 2013-02-05T21:16:07.810 に答える