0

関数があり、ループ内で呼び出され、ループごとに一連の整数を生成できます。次に例を示します。

ループ 1 の{1 1 1 2}
結果: ループ 2 の{1 1 1 3}
結果: ループ 3 の{2 1 1 3}
結果: ループ 4 の結果:{3 1 3 2}

また、この関数は重複結果を生成する場合があります。たとえば、結果 2 と結果 3 は同じです。これらの結果をデータ構造内に配置する必要がありますが、重複を配置できません。結果 2 が結果 3 と同じ場合、それらの 1 つだけを保持する必要がありCます。

4

2 に答える 2

1

アイテムの範囲が十分に小さい場合は、列挙の手段としてビットマップを使用できます。たとえば、1〜32の範囲の整数のセットを表す場合、必要なのはビットマップとして使用される32ビット整数だけです。

00000001 00000001 00000000 00000000    - for set {8,16}
       ^        ^
       8        16

等

範囲が大きい場合は、バイトの配列を使用します。各ビットは、この位置の値がセットに存在するかどうかを表します。

#define MAXVAL 1024

typedef unsigned char bitmap_t[];
byte bitmap[1 + MAXVAL / CHAR_BIT] = { 0 };
// CHAR_BIT is defined in limit.h and is equal to count of bits in a byte

void insert(bitmap_t bitmap, unsigned val) {
  assert(val < MAXVAL);
  bitmap[val / CHAR_BIT] |= (1 << (val % CHAR_BIT);
}

int is_present(bitmap_t bitmap, unsigned val) {
  assert(val < MAXVAL);
  return bitmap[ val / CHAR_BIT ] & (1 << (val % CHAR_BIT));
}
于 2012-11-01T18:52:52.683 に答える
0

C++ では、これは簡単です。std::sets の aを使用するだけstd::tupleです。C では、すべての機能を自分で実装するか、適切なライブラリを見つける必要がありますが、全体的なアプローチは同じです。

于 2012-11-01T18:33:58.543 に答える