同じものを含む円順列の生成

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら　　※コードを貼り付ける場合は [code] と [/code] で囲って下さい。詳しくはこちら

トピックに返信する


答えを正確にご入力ください。答えられるかどうかでスパムボットか否かを判定します。
BBCode: ON
[img]: ON
[flash]: OFF
[url]: ON
スマイリー: OFF
トピックのレビュー
   

展開ビュー トピックのレビュー: 同じものを含む円順列の生成

Re: 同じものを含む円順列の生成

#4

by かずま » 5年前

m3908714035 さんが書きました: ↑
5年前
 t.find(s) == string::npos がイマイチぴんと来ていないのですが、t内でsが含まれるイテレータの位置＝string::findで値が見つからなかった場合に返す値(-1)⇔t内にsはないという認識でよいのでしょうか。
その認識でよいでしょう。
ただし、イテレータを返すのではありません。
t.find(s) は　s の中に t が見つかれば、その位置を整数値で返します。
見つからなければ string::npos を返します。
その値は、-1 を符号なしに変換した値(最大の整数値) です。
実際には、32ビットコンパイラでは 4294967295、
64ビットコンパイラでは 18446744073709551615 になるでしょう。
cout << string::npos で調べてみてください。

Re: 同じものを含む円順列の生成

#3

by m3908714035 » 5年前

回答ありがとうございます。
t.find(s) == string::npos がイマイチぴんと来ていないのですが、t内でsが含まれるイテレータの位置＝string::findで値が見つからなかった場合に返す値(-1)⇔t内にsはないという認識でよいのでしょうか。

Re: 同じものを含む円順列の生成

#2

by かずま » 5年前

生成した文字列を 2つ連結して、それを並べた文字列を用意すると、
新たな候補の文字列がそれに含まれるかどうかが判定できます。
2つ連結するのは円順列による一致を調べるためです。

コード: 

#include <iostream>
#include <string>
#include <algorithm>  // sort, next_permutation
using namespace std;

int main()
{
	string s, t = "";
	cout << ">> ";
	cin >> s;
	sort(begin(s), end(s));
	auto a = begin(s) + 1, b = end(s);
	do {
		if (t.find(s) == string::npos) {
			cout << s << endl;
			t += s + s + " ";
		}
	} while (next_permutation(a, b));
}
単純な方法なので、30桁は厳しいでしょう。

実行例

コード: 

>> 111111000000
000000111111
000001011111
000001101111
000001110111
000001111011
000001111101
000010011111
000010101111
000010110111
000010111011
000010111101
000011001111
000011010111
000011011011
000011011101
000011100111
000011101011
000011101101
000011110011
000011110101
000011111001
000100011111
000100101111
000100110111
000100111011
000100111101
000101001111
000101010111
000101011011
000101011101
000101100111
000101101011
000101101101
000101110011
000101110101
000101111001
000110001111
000110010111
000110011011
000110011101
000110100111
000110101011
000110101101
000110110011
000110110101
000110111001
000111000111
000111001011
000111001101
000111010011
000111010101
000111011001
000111100101
000111101001
001001001111
001001010111
001001011011
001001011101
001001100111
001001101011
001001101101
001001110011
001001110101
001010010111
001010011011
001010011101
001010100111
001010101011
001010101101
001010110011
001010110101
001011001011
001011001101
001011010011
001011010101
001100110011
001100110101
001101001101
001101010101
010101010101

同じものを含む円順列の生成

#1

by m3908714035 » 5年前

同じものを含む円順列を列挙したいです。
重複するものがなければ、高校数学的に一つを固定してnext_permitationでforしていけば円順列を作ることができますが、重複するものが出てくるとそう簡単には解けませんでした。
想定しているのは入力"111111000000（文字列, 桁数は30くらいまで）"を並び替えて円順列を出力するというものです。
自身で考えてはみたものの、さっぱりアイデアが思い浮かびません。
全て列挙して一つ一つ文字を右へずらし、ほかのものと被れば消去ということは考えましたが、当たり前のように時間がかかってしまいました。
良い方法があればご教示いただけると幸いです。

ページトップ