为了好玩,我通过枚举所有排列来勾勒出一个关于 N 个皇后排列的问题。一切都很完美,获得了常规棋盘所需的 92 个排列。
我想得到一组排列——嗯,有多少根本不同的排列不是通过对称或旋转获得的。为此,我还添加map
了一个比较向量的比较器,如果可以从另一个获得,则在比较时表示false
。审查了测试示例 - 它似乎工作正常。但是map
排列结果是通过对称获得的——他说总共有 46 个组。这显然是错误的——应该是 12!
我只是看不到我的错误,有人可以帮助我了解我到底在哪里做错了吗?Comporator有问题吗?
这是代码,它很小:
#include <vector>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <map>
using namespace std;
// Создание всех возможных расстановок с помощью симметрий
vector<vector<int>> makeV(const vector<int>& a) {
const size_t N = a.size();
vector<vector<int>> p(7, vector<int>(N));
for (int i = 0; i < N; ++i) {
p[0][i] = int(N - 1 - a[i]); // H
p[1][N - 1 - i] = int(a[i]); // V
p[2][N - 1 - i] = int(N - 1 - a[i]); // O
p[3][a[i]] = int(i); // \s
p[4][a[i]] = int(N - 1 - i); // ->
p[5][N - 1 - a[i]] = int(i); // <-
p[6][N - 1 - a[i]] = int(N - 1 - i); // /s
}
return p;
}
// Класс для сравнения двух векторов (можно ли получить один
// из второго симметриями - тогда равны)
struct lessVec {
bool operator()(const vector<int>& a, const vector<int>& b) const {
if (a == b) return false;
vector<vector<int>> p = makeV(a);
// Если получается хоть одной симметрией - равны, вернуть false
for (int i = 0; i < 7; ++i) if (b == p[i]) return false;
// Обычное сравнение
return a < b;
}
};
// true, если есть пара бьющих ферзей
bool fight(const vector<int>& p) {
for (unsigned int i = 0; i < p.size() - 1; ++i) {
for (unsigned int j = i + 1; j < p.size(); ++j) {
if (int(j - i) == abs(p[j] - p[i])) return true;
}
}
return false;
}
// Решение для доски NxN
pair<int, int> solve(int N) {
map<vector<int>, int, lessVec> m; // Сбор групп решений
// Проверяю все перестановки
vector<int> p(N);
for (int i = 0; i < N; ++i) p[i] = i;
int count = 0; // Количество решений
do {
if (!fight(p)) {
++count;
m[p]++; // Сколько в группе решений
}
} while (next_permutation(p.begin(), p.end()));
return make_pair(count, int(m.size()));
}
int main() {
for (int i = 8; i <= 8; ++i) {
auto p = solve(i);
cout << setw(2) << i << " "
<< setw(7) << p.first << " "
<< setw(7) << p.second << endl;
}
}
您在比较器中有错误。例如,您可以想出四个不同的位置
a
,b
,c
,d
,a = b
,c = d
,a < c
。d < b
你在哪里可以推断出什么a < a
。正确的比较器可以这样安排:
让我们引入一个等价关系。如果一个位置可以通过旋转和反射转换为另一个位置,则两个位置是等效的。所有位置都可以分组到等价类中。在每个班级中,我们挑选出一个典型的代表。稍后,当我们需要比较两个元素时,我们将比较它们的规范代表。
选择规范代表的方式并不重要。重要的是两个等效位置具有相同的规范代表,而两个非等效位置具有不同的典型代表。例如,您可以选择通常意义上的班级中的最小位置。
由于每个元素都有一个规范代表,并且由于规范代表的顺序满足所有必需的属性(传递性、反自反性、不对称性),因此新顺序也得到了很好的定义。