それぞれ同じ個数（ i個 ）の"1"と"0"からなる円順列の集合Aを列挙せよ。
※ 円順列は文字列であって数値ではない
この問題は数は少ないうちはまだしも、iが増えるにつれ爆発的に答えが増えてしまうのでC++を用いた回答を試みました。
// _vi -> 解答書き込み先
// vi -> 解答候補
// 一つの"1"を最高位に固定して後ろに next_permutation から作成した"1"（i-1個）と"0"（i個）からなる順列を付加
// 数値を用いて考えているのでなんとなく桁が分からなくならないように最高位に"1"を固定した
// i -> "1"と"0"それぞれの個数（"1"と"0"の個数は合わせて 2i 個ということ）
// したいこと: 解答候補 vi から円順列的に重複するものを消して &_vi に解答を書き込みたい
void search(std::vector<int> &_vi, std::vector<int> vi, int i)
{
// https://ameblo.jp/molossique/entry-11058325123.html より
// どれだけずらすかの候補⇔要素数の約数（ conceivable_gap ）を決定
std::vector<int> conceivable_gap;
for (int number = 2; pow(number, 2) <= i * 2; number++)
{
if (i * 2 % number == 0)
{
conceivable_gap.push_back(number);
if (number != 1 && pow(number, 2) != i * 2)
{
conceivable_gap.push_back(i * 2 / number);
}
}
}
sort(conceivable_gap.begin(), conceivable_gap.end());
// 私個人が分かりやすいように無名関数表記
auto check_bit_on = [](int bit, int number) { return bit & (1 << number); };
auto make_bit_on = [](int &_bit, int number) { _bit |= (1 << number); };
auto make_bit_off = [](int &_bit, int number) { _bit &= ~(1 << number); };
// 最も大きいビットが何番目にあるか確認
int bit_number_max = log2(vi[0]);
int bit_number_half = log2(vi[0]) / 2;
int bit_temp;
int new_bit_number;
// 第1ループでは候補の中でこれから考える対象を決定
for (int target = 0; target < vi.size(); target++)
{
// 第2ループではビットをずらす個数を決定
for (int time = 0; time < conceivable_gap.size(); time++)
{
// 第3ループではその値において注目するビットの位置を決定
for (int bit_number = 0; bit_number < bit_number_max; bit_number++)
{
// もしその位置のビットが立っていたら…
if (check_bit_on(vi[target], bit_number))
{
// ずらした後の新しいビットの位置を決定
new_bit_number = bit_number + conceivable_gap[time];
// 本来の桁から左にずれることになるビットは new_bit_number % bit_number_max 番へ
// つまり剰余を考えないと 10100 → 1010000 のままになるから左の 10 を右へ動かす
make_bit_on(bit_temp, new_bit_number % bit_number_max);
}
}
// 元々の候補の中に同じものがある = 円順列的には同じ
auto iterator = std::find(vi.begin(), vi.end(), bit_temp);
// あればそれを消して今考えている値を解答の配列へ
if (iterator == vi.end())
{
_vi.push_back(bit_temp);
vi.erase(iterator);
break;
}
}
}
return;
}
// どうにかして自分の考えが伝わるように書いた多大な説明書きを省いたver.
void search(std::vector<int> &_vi, std::vector<int> vi, int i)
{
std::vector<int> conceivable_gap;
for (int number = 2; pow(number, 2) <= i * 2; number++)
{
if (i * 2 % number == 0)
{
conceivable_gap.push_back(number);
if (number != 1 && pow(number, 2) != i * 2)
{
conceivable_gap.push_back(i * 2 / number);
}
}
}
sort(conceivable_gap.begin(), conceivable_gap.end());
auto check_bit_on = [](int bit, int number) { return bit & (1 << number); };
auto make_bit_on = [](int &_bit, int number) { _bit |= (1 << number); };
auto make_bit_off = [](int &_bit, int number) { _bit &= ~(1 << number); };
int bit_number_max = log2(vi[0]);
int bit_number_half = log2(vi[0]) / 2;
int bit_temp;
int new_bit_number;
for (int target = 0; target < vi.size(); target++)
{
for (int time = 0; time < conceivable_gap.size(); time++)
{
for (int bit_number = 0; bit_number < bit_number_max; bit_number++)
{
if (check_bit_on(vi[target], bit_number))
{
new_bit_number = bit_number + conceivable_gap[time];
make_bit_on(bit_temp, new_bit_number % bit_number_max);
}
}
auto iterator = std::find(vi.begin(), vi.end(), bit_temp);
if (iterator == vi.end())
{
_vi.push_back(bit_temp);
vi.erase(iterator);
break;
}
}
}
return;
}
①解答を完成させるにはどうすればよいか ②そもそもこの考え方はあっているのか をご教示いただけたらと思います。
メニュー
カレンダー
Clock
最新メンバー
投稿数
統計データ
Link to us
カウンター