わんくま勉強会東京82でごまかした8パズルのパターン数を調べてみたが間違ってた

Filed in C/C++, prog

 昨日のパターンを調べた件が会社のパズル詳しい人におかしいと突っ込まれたので考えてみた。

 偶置換を一個入れ替えると必ず奇置換なんだから確かに$\frac{8!}{2}$になるべき。
 ということでコード書き直し。要するに巡回置換作るところの添字の取り方がおかしかった。
 参照済みの添字の管理をもうちょっとうまくやれそうな気がするけどめんどくなったのでこれで。

 あと地味にalgorithmインクルードしてなかった (職場でIDEONに投げるまで気づかなかった)。

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
bool is_pazzleout(const std::vector<int>& seq)
{
std::vector<int> referenced(seq.size(), 0);
int sum = 0;
for (int i = 0; i < seq.size(); i = std::distance(referenced.begin(), std::find(referenced.begin(), referenced.end(), 0))) {
int f = i + 1;
std::set<int> cyclic;
cyclic.insert(f);
referenced[i] = f;
for (int j = i; f != seq[j]; j = seq[j] - 1) {
//            std::cout << "f: " << f << ", seq[" << j << "]: " << seq[j] << std::endl;
cyclic.insert(seq[j]);
referenced[seq[j] - 1] = seq[j];
}
sum += cyclic.size() - 1;
}
return sum % 2;
}
void print(const std::vector<int>& seq)
{
std::cout << "( ";
std::for_each(seq.begin(), seq.end(), [](int x) {
std::cout << x << " ";
});
std::cout << ")";
if (is_pazzleout(seq)) std::cout << "*";
std::cout << std::endl;
}
int main()
{
std::vector<int> complete;
for (int i = 1; i <= 8; ++i) {
complete.push_back(i);
}
do {
print(complete);
} while (std::next_permutation(complete.begin(), complete.end()));
return 0;
}


Warning: sprintf() [function.sprintf]: Too few arguments in /home/users/2/lolipop.jp-dp07042166/web/wordpress/wp-includes/widgets.php on line 1042
Oenology Post Formats
Click to view/hide

Warning: sprintf() [function.sprintf]: Too few arguments in /home/users/2/lolipop.jp-dp07042166/web/wordpress/wp-includes/widgets.php on line 1042
Posts Calendar
Click to view/hide
2013年6月
« 4月   10月 »
 1
2345678
9101112131415
16171819202122
23242526272829
30  

Warning: sprintf() [function.sprintf]: Too few arguments in /home/users/2/lolipop.jp-dp07042166/web/wordpress/wp-includes/widgets.php on line 1042
アーカイブ
Click to view/hide

Warning: sprintf() [function.sprintf]: Too few arguments in /home/users/2/lolipop.jp-dp07042166/web/wordpress/wp-includes/widgets.php on line 1042
最近の投稿
Click to view/hide