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

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

　偶置換を一個入れ替えると必ず奇置換なんだから確かに$\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;
}