順列のアルゴリズムについて

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
m3908714035
記事: 17
登録日時: 5ヶ月前

順列のアルゴリズムについて

#1

投稿記事 by m3908714035 » 1ヶ月前

<QUESTION>
それぞれ同じ個数( 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;
	}
C++は少しかじっている程度なので、コード的に汚いと思われるところが多々あるかもしれません。理解しづらかったら申し訳ないです。様々な入力でデバックしてみましたが、 "vector erase iterator outside range" となってしまいました。エラーの意味は分かるのですが、なぜこうなってしまったのかもわかりません。
①解答を完成させるにはどうすればよいか ②そもそもこの考え方はあっているのか をご教示いただけたらと思います。

m3908714035
記事: 17
登録日時: 5ヶ月前

Re: 順列のアルゴリズムについて

#2

投稿記事 by m3908714035 » 1ヶ月前

修正しました。

コード:

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;
		bool bit_check;
		for (int target = 0; target < vi.size(); target++)
		{
			bit_check = false;
			std::cout << "vi: " << (std::bitset<12>)vi[target] << " | ";
			for (int time = 0; time < conceivable_gap.size(); time++)
			{
				bit_temp = 0;
				for (int bit_number = 0; bit_number < bit_number_max + 1; bit_number++)
				{
					if (check_bit_on(vi[target], bit_number))
					{
						make_bit_on(bit_temp, (bit_number + conceivable_gap[time]) % (bit_number_max + 1));
					}
				}
				auto iterator = std::find(vi.begin(), vi.end(), bit_temp);
				if (iterator != vi.end())
				{
					if (!bit_check)
					{
						_vi.push_back(bit_temp);
						std::cout << (std::bitset<12>)_vi[_vi.size() - 1] << std::endl;
					}
					bit_check = true;
					vi.erase(iterator);
				}
			}
			if (!bit_check)
			{
				_vi.push_back(bit_temp);
				std::cout << (std::bitset<12>)_vi[_vi.size() - 1] << std::endl;
			}
		}
		return;
	}
ex. i=6 に対しての出力
※本来ならば (12-1)!/6!6!=77個 だが出力は 164個

コード:

vi: 111111000000 | 111100000011
vi: 111110100000 | 111010000011
vi: 111101100000 | 110110000011
vi: 111011100000 | 101110000011
vi: 110111100000 | 111100000110
vi: 101111100000 | 111110000010
vi: 111110010000 | 111001000011
vi: 111101010000 | 110101000011
vi: 111011010000 | 101101000011
vi: 110111010000 | 111010000110
vi: 101111010000 | 111101000010
vi: 111100110000 | 110011000011
vi: 111010110000 | 101011000011
vi: 110110110000 | 110110000110
vi: 101110110000 | 111011000010
vi: 111001110000 | 100111000011
vi: 110101110000 | 101110000110
vi: 101101110000 | 110111000010
vi: 110011110000 | 111100001100
vi: 101011110000 | 101111000010
vi: 100111110000 | 111110000100
vi: 111110001000 | 111000100011
vi: 111101001000 | 110100100011
vi: 111011001000 | 101100100011
vi: 110111001000 | 111001000110
vi: 101111001000 | 111100100010
vi: 111100101000 | 110010100011
vi: 111010101000 | 101010100011
vi: 110110101000 | 110101000110
vi: 101110101000 | 111010100010
vi: 111001101000 | 100110100011
vi: 110101101000 | 101101000110
vi: 101101101000 | 110110100010
vi: 110011101000 | 111010001100
vi: 101011101000 | 101110100010
vi: 100111101000 | 111101000100
vi: 111100011000 | 110001100011
vi: 111010011000 | 101001100011
vi: 110110011000 | 110011000110
vi: 101110011000 | 111001100010
vi: 111001011000 | 100101100011
vi: 110101011000 | 101011000110
vi: 101101011000 | 110101100010
vi: 110011011000 | 110110001100
vi: 101011011000 | 101101100010
vi: 100111011000 | 111011000100
vi: 111000111000 | 100011100011
vi: 101100111000 | 110011100010
vi: 110010111000 | 101110001100
vi: 101010111000 | 101011100010
vi: 100110111000 | 110111000100
vi: 110001111000 | 111000110001
vi: 101001111000 | 100111100010
vi: 100101111000 | 101111000100
vi: 100011111000 | 111110001000
vi: 111010100100 | 101010010011
vi: 110110100100 | 110100100110
vi: 101110100100 | 111010010010
vi: 111001100100 | 100110010011
vi: 110101100100 | 101100100110
vi: 101101100100 | 110110010010
vi: 110011100100 | 111001001100
vi: 101011100100 | 101110010010
vi: 100111100100 | 111100100100
vi: 111010010100 | 101001010011
vi: 110110010100 | 110010100110
vi: 101110010100 | 111001010010
vi: 111001010100 | 100101010011
vi: 110101010100 | 101010100110
vi: 101101010100 | 110101010010
vi: 110011010100 | 110101001100
vi: 101011010100 | 101101010010
vi: 100111010100 | 111010100100
vi: 101100110100 | 110011010010
vi: 110010110100 | 101101001100
vi: 101010110100 | 101011010010
vi: 100110110100 | 110110100100
vi: 101001110100 | 100111010010
vi: 100101110100 | 101110100100
vi: 101011001100 | 101100110010
vi: 100111001100 | 111001100100
vi: 101010101100 | 101010110010
vi: 100110101100 | 110101100100
vi: 101001101100 | 100110110010
vi: 100101101100 | 101101100100
vi: 110100011100 | 100011100110
vi: 101100011100 | 110001110010
vi: 110010011100 | 100111001100
vi: 100110011100 | 110011100100
vi: 101001011100 | 100101110010
vi: 100101011100 | 101011100100
vi: 100001111100 | 111100100001
vi: 111100010010 | 110001001011
vi: 110010110010 | 110010110010
vi: 100011110010 | 111100101000
vi: 110010101010 | 101010101100
vi: 110001101010 | 101010110001
vi: 101001101010 | 100110101010
vi: 110100011010 | 100011010110
vi: 101100011010 | 110001101010
vi: 100110011010 | 110011010100
vi: 101001011010 | 100101101010
vi: 100001111010 | 111010100001
vi: 100111000110 | 111000110100
vi: 101001100110 | 100110011010
vi: 110100010110 | 100010110110
vi: 101100010110 | 110001011010
vi: 100110010110 | 110010110100
vi: 101001010110 | 100101011010
vi: 110001001110 | 001110110001
vi: 100011001110 | 110011101000
vi: 100001101110 | 101110100001
vi: 110000011110 | 011110110000
vi: 101000011110 | 100001111010
vi: 111110000001 | 100000011111
vi: 111101000001 | 000001111101
vi: 111011000001 | 110000011110
vi: 101111000001 | 110000011011
vi: 111001100001 | 100001111001
vi: 110101100001 | 100001110101
vi: 101101100001 | 100001101101
vi: 110011100001 | 111000011100
vi: 100111100001 | 111000011001
vi: 111100010001 | 010001111100
vi: 111010010001 | 100100011110
vi: 101110010001 | 100100011011
vi: 111001010001 | 010001111001
vi: 110101010001 | 010001110101
vi: 101101010001 | 010001101101
vi: 110011010001 | 110100011100
vi: 100111010001 | 110100011001
vi: 110010110001 | 101100011100
vi: 101001110001 | 100111000110
vi: 100011110001 | 111100011000
vi: 110101001001 | 001001110101
vi: 101101001001 | 001001101101
vi: 110011001001 | 110010011100
vi: 100111001001 | 110010011001
vi: 110010101001 | 101010011100
vi: 110001101001 | 101001110001
vi: 100011101001 | 111010011000
vi: 101010011001 | 101001100110
vi: 101001011001 | 100101100110
vi: 101001100101 | 100110010110
vi: 110100010101 | 100010101110
vi: 110010010101 | 100101011100
vi: 100110010101 | 110010101100
vi: 101001010101 | 100101010110
vi: 100011010101 | 110101011000
vi: 110001001101 | 001101110001
vi: 100011001101 | 110011011000
vi: 110000011101 | 011101110000
vi: 101000011101 | 100001110110
vi: 111000010011 | 100001001111
vi: 110100010011 | 100010011110
vi: 110010010011 | 010011110010
vi: 110001010011 | 010011110001
vi: 100011010011 | 010011100011
vi: 100010110011 | 101100111000
vi: 100010101011 | 101010111000
vi: 100010011011 | 100110111000
vi: 100100100111 | 100111100100
vi: 110000010111 | 010111110000
vi: 101000010111 | 100001011110

かずま

Re: 順列のアルゴリズムについて

#3

投稿記事 by かずま » 1ヶ月前

m3908714035 さんが書きました:
1ヶ月前
修正しました。
どういう修正をしたのかを具体的に書いてください。

おそらく、if (iterator == vi.end()) vi.erase(iterator);
で、存在しない要素を削除したのが間違いだったのでしょうが。
m3908714035 さんが書きました:
1ヶ月前
ex. i=6 に対しての出力
その出力を出すコンパイル可能なプログラムを貼り付けてください。
ヘッダのインクルードや main を含むものです。
m3908714035 さんが書きました:
1ヶ月前
※本来ならば (12-1)!/6!6!=77個 だが出力は 164個
i = 2 の場合の 1100 について考察してください。
(4-1)! / (2! * 2!) = 1.5個ではないはずです。
m3908714035 さんが書きました:
1ヶ月前

コード:

vi: 111111000000 | 111100000011
vi: 111110100000 | 111010000011
vi: 111101100000 | 110110000011
vi: 111011100000 | 101110000011
vi: 110111100000 | 111100000110
vi: 101111100000 | 111110000010
vi: 111110010000 | 111001000011
vi: 111101010000 | 110101000011
vi: 111011010000 | 101101000011
vi: 110111010000 | 111010000110
vi: 101111010000 | 111101000010
vi: 111100110000 | 110011000011
vi: 111010110000 | 101011000011
vi: 110110110000 | 110110000110
vi: 101110110000 | 111011000010
vi: 111001110000 | 100111000011
vi: 110101110000 | 101110000110
vi: 101101110000 | 110111000010
vi: 110011110000 | 111100001100
vi: 101011110000 | 101111000010
vi: 100111110000 | 111110000100
vi: 111110001000 | 111000100011
vi: 111101001000 | 110100100011
vi: 111011001000 | 101100100011
vi: 110111001000 | 111001000110
vi: 101111001000 | 111100100010
vi: 111100101000 | 110010100011
vi: 111010101000 | 101010100011
vi: 110110101000 | 110101000110
vi: 101110101000 | 111010100010
vi: 111001101000 | 100110100011
vi: 110101101000 | 101101000110
vi: 101101101000 | 110110100010
vi: 110011101000 | 111010001100
vi: 101011101000 | 101110100010
vi: 100111101000 | 111101000100
vi: 111100011000 | 110001100011
vi: 111010011000 | 101001100011
vi: 110110011000 | 110011000110
vi: 101110011000 | 111001100010
vi: 111001011000 | 100101100011
vi: 110101011000 | 101011000110
vi: 101101011000 | 110101100010
vi: 110011011000 | 110110001100
vi: 101011011000 | 101101100010
vi: 100111011000 | 111011000100
vi: 111000111000 | 100011100011
vi: 101100111000 | 110011100010
vi: 110010111000 | 101110001100
vi: 101010111000 | 101011100010
vi: 100110111000 | 110111000100
vi: 110001111000 | 111000110001
vi: 101001111000 | 100111100010
vi: 100101111000 | 101111000100
vi: 100011111000 | 111110001000
vi: 111010100100 | 101010010011
vi: 110110100100 | 110100100110
vi: 101110100100 | 111010010010
vi: 111001100100 | 100110010011
vi: 110101100100 | 101100100110
vi: 101101100100 | 110110010010
vi: 110011100100 | 111001001100
vi: 101011100100 | 101110010010
vi: 100111100100 | 111100100100
vi: 111010010100 | 101001010011
vi: 110110010100 | 110010100110
vi: 101110010100 | 111001010010
vi: 111001010100 | 100101010011
vi: 110101010100 | 101010100110
vi: 101101010100 | 110101010010
vi: 110011010100 | 110101001100
vi: 101011010100 | 101101010010
vi: 100111010100 | 111010100100
vi: 101100110100 | 110011010010
vi: 110010110100 | 101101001100
vi: 101010110100 | 101011010010
vi: 100110110100 | 110110100100
vi: 101001110100 | 100111010010
vi: 100101110100 | 101110100100
vi: 101011001100 | 101100110010
vi: 100111001100 | 111001100100
vi: 101010101100 | 101010110010
vi: 100110101100 | 110101100100
vi: 101001101100 | 100110110010
vi: 100101101100 | 101101100100
vi: 110100011100 | 100011100110
vi: 101100011100 | 110001110010
vi: 110010011100 | 100111001100
vi: 100110011100 | 110011100100
vi: 101001011100 | 100101110010
vi: 100101011100 | 101011100100
vi: 100001111100 | 111100100001
vi: 111100010010 | 110001001011
vi: 110010110010 | 110010110010
vi: 100011110010 | 111100101000
vi: 110010101010 | 101010101100
vi: 110001101010 | 101010110001
vi: 101001101010 | 100110101010
vi: 110100011010 | 100011010110
vi: 101100011010 | 110001101010
vi: 100110011010 | 110011010100
vi: 101001011010 | 100101101010
vi: 100001111010 | 111010100001
vi: 100111000110 | 111000110100
vi: 101001100110 | 100110011010
vi: 110100010110 | 100010110110
vi: 101100010110 | 110001011010
vi: 100110010110 | 110010110100
vi: 101001010110 | 100101011010
vi: 110001001110 | 001110110001
vi: 100011001110 | 110011101000
vi: 100001101110 | 101110100001
vi: 110000011110 | 011110110000
vi: 101000011110 | 100001111010
vi: 111110000001 | 100000011111
vi: 111101000001 | 000001111101
vi: 111011000001 | 110000011110
vi: 101111000001 | 110000011011
vi: 111001100001 | 100001111001
vi: 110101100001 | 100001110101
vi: 101101100001 | 100001101101
vi: 110011100001 | 111000011100
vi: 100111100001 | 111000011001
vi: 111100010001 | 010001111100
vi: 111010010001 | 100100011110
vi: 101110010001 | 100100011011
vi: 111001010001 | 010001111001
vi: 110101010001 | 010001110101
vi: 101101010001 | 010001101101
vi: 110011010001 | 110100011100
vi: 100111010001 | 110100011001
vi: 110010110001 | 101100011100
vi: 101001110001 | 100111000110
vi: 100011110001 | 111100011000
vi: 110101001001 | 001001110101
vi: 101101001001 | 001001101101
vi: 110011001001 | 110010011100
vi: 100111001001 | 110010011001
vi: 110010101001 | 101010011100
vi: 110001101001 | 101001110001
vi: 100011101001 | 111010011000
vi: 101010011001 | 101001100110
vi: 101001011001 | 100101100110
vi: 101001100101 | 100110010110
vi: 110100010101 | 100010101110
vi: 110010010101 | 100101011100
vi: 100110010101 | 110010101100
vi: 101001010101 | 100101010110
vi: 100011010101 | 110101011000
vi: 110001001101 | 001101110001
vi: 100011001101 | 110011011000
vi: 110000011101 | 011101110000
vi: 101000011101 | 100001110110
vi: 111000010011 | 100001001111
vi: 110100010011 | 100010011110
vi: 110010010011 | 010011110010
vi: 110001010011 | 010011110001
vi: 100011010011 | 010011100011
vi: 100010110011 | 101100111000
vi: 100010101011 | 101010111000
vi: 100010011011 | 100110111000
vi: 100100100111 | 100111100100
vi: 110000010111 | 010111110000
vi: 101000010111 | 100001011110
37行目の vi: 111100011000 | 110001100011 と
52行目の vi: 110001111000 | 111000110001 は
円順列として同じものですよね。
他にもたくさんあります。

101010101010 がありませんね。

m3908714035
記事: 17
登録日時: 5ヶ月前

Re: 順列のアルゴリズムについて

#4

投稿記事 by m3908714035 » 1ヶ月前

かずま さんが書きました:
1ヶ月前
どういう修正をしたのかを具体的に書いてください。
おそらく、if (iterator == vi.end()) vi.erase(iterator);
で、存在しない要素を削除したのが間違いだったのでしょうが。
おっしゃる通りです。投げやりな投稿失礼いたしました。
かずま さんが書きました:
1ヶ月前
その出力を出すコンパイル可能なプログラムを貼り付けてください。
ヘッダのインクルードや main を含むものです。
コード全体としては完成していませんが、下記のコードで動かしました。

コード:

#include <iostream>
#include <chrono>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <bitset>

using TIME_POINT = std::chrono::system_clock::time_point;
using MILLISECONDS = std::chrono::milliseconds;

/*
namespace SYSTEM
{
	void measure(TIME_POINT &_t)
	{
		_t = std::chrono::system_clock::now();
		return;
	}
	void elapse(double &_d, TIME_POINT t1, TIME_POINT t2)
	{
		_d = std::chrono::duration_cast<MILLISECONDS>(t2 - t1).count();
		return;
	}
}
*/

namespace FUNCTION
{
	void input(int &_i)
	{
		std::cin >> _i;
		return;
	}
	void align(std::string &_s, int i)
	{
		for (int time = 0; time < i; time++)
		{
			_s += "0";
		}
		for (int time = 0; time < i; time++)
		{
			_s += "1";
		}
		return;
	}
	void permutate(std::vector<int> &_vi, std::string s)
	{
		s.pop_back();
		std::string temp;
		do
		{
			temp = s + '1';
			reverse(temp.begin(), temp.end());
			_vi.push_back(stoi(temp, nullptr, 2));
		} while (next_permutation(s.begin(), s.end()));
		return;
	}
	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;
		bool bit_check;
		for (int target = 0; target < vi.size(); target++)
		{
			bit_check = false;
			std::cout << "vi: " << (std::bitset<12>)vi[target] << " | ";
			for (int time = 0; time < conceivable_gap.size(); time++)
			{
				bit_temp = 0;
				for (int bit_number = 0; bit_number < bit_number_max + 1; bit_number++)
				{
					if (check_bit_on(vi[target], bit_number))
					{
						make_bit_on(bit_temp, (bit_number + conceivable_gap[time]) % (bit_number_max + 1));
					}
				}
				auto iterator = std::find(vi.begin(), vi.end(), bit_temp);
				if (iterator != vi.end())
				{
					if (!bit_check)
					{
						_vi.push_back(bit_temp);
						std::cout << (std::bitset<12>)_vi[_vi.size() - 1] << std::endl;
					}
					bit_check = true;
					vi.erase(iterator);
				}
			}
			if (!bit_check)
			{
				_vi.push_back(bit_temp);
				std::cout << (std::bitset<12>)_vi[_vi.size() - 1] << std::endl;
			}
		}
		return;
	}
}

int main()
{
	int element_count;
	FUNCTION::input(element_count);
	
	// TIME_POINT time_start;
	// SYSTEM::measure(time_start);
	
	std::string all_element;
	FUNCTION::align(all_element, element_count);
	std::vector<int> temporary_permutation;
	FUNCTION::permutate(temporary_permutation, all_element);
	std::vector<int> answer;
	FUNCTION::search(answer, temporary_permutation, element_count);
			
	// TIME_POINT time_end;
	// SYSTEM::measure(time_end);
	// double time_elapsed;
	// SYSTEM::elapse(time_elapsed, time_start, time_end);
	return 0;
}
色々と抜けがあって大変お恥ずかしい限りです。今一度確認してみます。

かずま

Re: 順列のアルゴリズムについて

#5

投稿記事 by かずま » 4週間前

m3908714035 さんが書きました:
1ヶ月前
コード全体としては完成していませんが、下記のコードで動かしました。
次ように書いても、main の temporary_permutation には同じ値が入ります。

コード:

	void align(std::string &_s, int i)
	{
		_s = std::string(i, '1') + std::string(i, '0');
	}
	void permutate(std::vector<int> &_vi, std::string s)
	{
		do {
			_vi.push_back(stoi(s, nullptr, 2));
		} while (prev_permutation(s.begin() + 1, s.end()));
	}
同じ値なので align や permutate は元のままでもかまいません。

しかし、search の中身がさっぱり理解できません。

conceivavle_gap とは何でしょうか?
今、i = 6 で試しているようなので、i * 2 は 12 で、
その約数で、1 と 12 でない { 2, 3, 4, 6 } が入りますね。
そのあとはさっぱりわかりません。

ところで、string を stoi で 2進数にするいうアイデアを
頂戴し、次のようなコードが書いてみました。

コード:

#include <iostream>
#include <map>
#include <string>     // stoi
#include <algorithm>  // prev_permutation
using namespace std;

int main()
{
	map<int, bool> mib;
	int i;
	cout << "i = ", cin >> i;
	string s = string(i, '1') + string(i, '0');
	i *= 2;
	int m = (1 << i) - 1;
	do {
		int k = 0, b = stoi(s, nullptr, 2);
		while (k < i && mib.find((b>>k | b<<(i - k)) & m) == mib.end()) k++;
		if (k == i) cout << s << endl, mib[b] = true;
	} while (prev_permutation(s.begin() + 1, s.end()));
}
実行例

コード:

i = 4
11110000
11101000
11100100
11100010
11011000
11010100
11010010
11001100
11001010
10101010
これは、string を使う次のコードよりずいぶん速くなります。

コード:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>  // prev_permutation
using namespace std;

int main()
{
	vector<string> vs;
	int i;
	cout << "i = ", cin >> i;
	string s = string(i, '1') + string(i, '0');
	do {
		string t = s + s;
		auto it = vs.begin();
		while (it != vs.end()  && t.find(*it) == string::npos) ++it;
		if (it == vs.end()) cout << s << endl, vs.push_back(s);
	} while (prev_permutation(s.begin() + 1, s.end()));
}

かずま

Re: 順列のアルゴリズムについて

#6

投稿記事 by かずま » 3週間前

30桁 (i = 15)でも実行できるプログラムができました。
出力は、画面表示ではなく、当然ファイルにリダイレクト
するものとします。5170694行にもなりますから。

コード:

#include <iostream>
#include <string>     // stoi
#include <map>
#include <algorithm>  // fill, min
using namespace std;

class CircularPermutation {
	int n;  // number of all '1' and '0'
	int m;  // mask of n bits
	int f;  // first '1' string length
	string s;
	map<int, bool> a;  // all of found bit patterns

	void print(int p, char c, int j) {
		if (j > 0) fill(&s[p], &s[p + j], c);
		int k = 0, b = stoi(s, nullptr, 2);
		while (k < n && a.find((b>>k | b<<(n-k)) & m) == a.end()) k++;
		if (k == n) cout << s << endl, a[b] = true;
	}

	void generate(int p, int n1, int n0) {
		if (n1 == 0) print(p, '0', n0);
		else if (n0 > 0)
			for (int k = min(f, n1); k >= 0; k--) {
				fill(&s[p], &s[p + k], '1');
				s[p + k] = '0';
				generate(p + k + 1, n1 - k, n0 - 1);
			}
		else if (n1 <= f) print(p, '1', n1);
	}

public:
	CircularPermutation(int i) :
		n(i * 2), m((1<<n) - 1), s(string(i, '1') + string(i, '0'))
	{
		for (f = i; f > 0; f--)
			s[f] = '0', a.clear(), generate(f + 1, i - f, i - 2);
	}
};

int main()
{
	int i;
	while (cout << ">> i = ", cin >> i && i > 0 && i <= 15)
		CircularPermutation cp(i);
}
実行例

コード:

>> i = 4
11110000
11101000
11100100
11100010
11011000
11010100
11010010
11001100
11001010
10101010
>> i = 3
111000
110100
110010
101010
>> i = 2
1100
1010
>> i = 1
10
>> i = 0
分からないところは質問してくだされば解説します。

返信

“C言語何でも質問掲示板” へ戻る