Расширение Кантора
вводить
Фактически, значение канторовского расширения последовательности состоит в том, чтобы найти ранг последовательности во всех перестановках от мала до велика. Другими словами, мы ранжируем все последовательности в соответствии с их размером и используем этот номер ранга в качестве его хэш-значения.Надо сказать, что это умное совпадение.
Вычислительные идеи
Предполагая, что текущая последовательность равна 321, спросите ее значение расширения Кантора cantor("321"), легко узнать, что во всех полных перестановках есть 5 меньших, чем она, мы сначала смотрим на самые высокие 3, если мы хотим это последовательность, чтобы быть меньше, Есть два случая:
-
Старший бит меньше 3, а задний бит необязателен.
Есть 2 меньше 3, первая позиция меньше 3, независимо от того, как расположены последние 2, сформированная последовательность должна быть меньше 321, поэтому число равно
-
Старший бит равен 3, а последний меньше 21, так же как и 321.
Конечным результатом является то, что два вышеуказанных случая складываются вместе.На самом деле, для каждого бита в последовательности есть несколько чисел, меньших его, и это число умножается на полное число перестановок оставшихся чисел.Наконец складываем до ответа. Всегда помните об истинном значении величины разложения Кантора, принцип его расчета очень прост для понимания.
Формула:
Реализация кода (С++)
// 我自己写的代码，不优美但是应该没啥问题
#include <iostream>
#include <algorithm>
using namespace std;
inline int fact(int x)
{
int res = 1;
for (int i = 2; i <= x; ++ i) res *= i;
return res;
}
inline int getHash(string str)
{
int n = str.length();
int hashcode = 0;
for (int i = 0; i < n; ++ i)
{
int cnt = 0;
for (int j = i + 1; j < n; ++ j)
if (str[j] < str[i]) ++ cnt;
hashcode += cnt * fact(n - i - 1);
}
return hashcode + 1;
}
int main()
{
string str = "123";
do
{
cout << str << ' ' << getHash(str) << endl;
} while (next_permutation(str.begin(), str.end()));
}
результат операции
Обратное разложение Кантора
вводить
Расширение Кантора состоит в том, чтобы найти номер последовательности, а обратное расширение Кантора состоит в том, чтобы спросить, что такое n-я последовательность.
Вычислительные идеи
Когда мы задаем последовательность от малой до n-й в полной перестановке, это означает, что мы знаемДля значения x в левой части, помимо условия x, на самом деле существует неявное условие того, что все значения факториала могут быть вычислены, поэтому нам нужно найти
Если мы рассматриваем красную часть как число, и теперь мы знаем x и (n-1)!, мы можем вычислить a[n] и красную часть соответственно делением и остатком Точно так же мы можем вычислить все a .
a[n] означает, что число a[n] в битах с 1-го по n-1 (321, левая сторона — старший бит, правая сторона — младший бит) меньше, чем число n-го бита , то есть в инкременте Найдите наименьшее число a[n] + 1 в последовательности и поставьте его на n-м месте
Реализация кода (С++)
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
inline int fact(int x)
{
int res = 1;
for (int i = 2; i <= x; ++ i) res *= i;
return res;
}
inline string uncantor(int n, int inx) // 求在长度为n的序列中，从小到达排列，排第inx的序列是多少(从1开始)
{
string res;
int vis[n * n];
memset(vis, 0, sizeof vis);
-- inx; // 比当前序列小的序列有inx个
for (int i = (n - 1); ~i; -- i)
{
int c = inx / fact(i), s = inx % fact(i);
int cnt = 0, num;
for (int j = 1; j <= n; ++ j)
{
if (!vis[j]) ++ cnt;
if (cnt == c + 1) // 找到第c+1小的数
{
num = j;
break;
}
}
vis[num] = 1;
res += num + '0';
inx = s;
}
return res;
}
int main()
{
for (int i = 1; i < 7; ++ i) cout << i << ' ' << uncantor(3, i) << endl;
return 0;
}
результат операции
Пример приложения Cantor Expand
Я наткнулся на эту точку знаний, потому чтоВосемь номеровЭтот вопрос, на самом деле, основным тестовым сайтом этого вопроса является bfs, Поскольку я недавно изучил смоделированную хеш-таблицу, я хочу попытаться заменить часть, использующую unordered_map в вопросе, на ручное хеширование. Проблема в процессе хеширования заключается в том, что когда выбранное нами постоянное число P мало, оно не может удовлетворять инъективному отношению от P к десятичному числу. Если оно слишком велико, его нельзя использовать в качестве нижнего индекса массива, и хеширование невозможно.
Расследование в P
| биты данных | Удовлетворить минимальное значение P инъективного |
|---|---|
| 1 | 1 |
| 2 | 2 |
| 3 | 2 |
| 4 | 4 |
| 5 | 5 |
| 6 | 6 |
| 7 | 7 |
| 8 | 8 |
| 9 | 9 |
Вроде бы разрядов данных несколько, а минимальное значение значения P, которое можно выбрать для достижения инъективности в процессе шестнадцатеричного преобразования, это несколько, не совсем понимаю, почему такая связь. Возвращаясь к этому вопросу, если мы используем постоянное число (P для всех цифр одно и то же) и хотим, чтобы 9 цифр удовлетворяли инъективному отношению, максимальное значение хеш-функции после отображения составляет 478222166, первое в стеке невозможно открыть такое большое пространство.Если он открыт в куче, размер также составляет 1824 МБ, и требования к пространству, указанные в заголовке, не могут быть выполнены.
решение
Можно обнаружить, что эти разные состояния подобны набору полных перестановок в одномерном состоянии, а расширение Кантора — биекция от полной перестановки к натуральному числу, цель — построить пространственное сжатие хеш-таблицы (чувство для этого такое же, как проблема)
Код
/**
* 写法1-手动哈希，字符串哈希方法在本道题中行不通，需要采用康托展开的方法
* 康托展开只是一种特殊的哈希方法
*/
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
const int N = 4e5 + 1, P = 7; // 总状态数最多也就9!(362880)种，二维下的种类数不太好想，一维下就很简单了，简单的排列问题
string q[N];
int dis[N];
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
inline int fact(int x) // fact(x)：计算x!
{
int res = 1;
for (int i = 2; i <= x; ++ i) res *= i;
return res;
}
inline int getHash(string str) // 采用康托展开的方法获取str的哈希值
{
int n = str.length();
int hashcode = 0;
// 计算str序列前比它小序列有多少个
for (int i = 0; i < n; ++ i)
{
int cnt = 0;
for (int j = i + 1; j < n; ++ j)
if (str[j] < str[i]) ++ cnt;
hashcode += cnt * fact(n - i - 1); // 之所以是加法，因为比当前这个序列小的可能是当前这一位小，后面随意，也可能是这位相等，后面小
}
return hashcode + 1; // +1只是为了我想满足康托展开的定义，不加1一样可以ac，这个位置让我进一步理解了哈希的实质
}
int bfs(string start)
{
int hh = 0, tt = -1;
memset(dis, -1, sizeof dis);
dis[getHash(start)] = 0;
q[++ tt] = start;
string end = "12345678x";
while (hh <= tt)
{
// 虽然现在的存储形式是字符串，但是我们需要把字符串转换为矩阵，经过变换后再变为字符串。不过这里的字符串和矩阵之间的转换并不能真的去做而是通过坐标的变换来实现
string t = q[hh ++];
//cout << getHash(t) << endl;
int k = t.find('x');
int x = k / 3, y = k % 3; // 从字符串映射到矩阵
if (t == end) return dis[getHash(t)];
for (int i = 0; i < 4; ++ i)
{
int a = x + dx[i], b = y + dy[i];
if (a >= 0 && a < 3 && b >= 0 && b < 3)
{
string tmp = t;
swap(tmp[k], tmp[a * 3 + b]); // 从矩阵映射到字符串
if (dis[getHash(tmp)] == -1) // 这个状态之前没有访问过
{
q[++ tt] = tmp;
dis[getHash(tmp)] = dis[getHash(t)] + 1;
}
}
}
}
return -1;
}
int main()
{
string c, start;
for (int i = 0; i < 9; ++ i)
{
cin >> c;
start += c;
}
cout << bfs(start) << endl;
return 0;
}
/**
* 写法2-手动哈希改为unordered_map
* 感觉哈希有问题，所以试了试用库函数，然后就ac了，果然还是有问题
* 之所以采用unorder_map而非map是因为map底层实现是红黑树，具有排序功能，unordered_map底层则是哈希表，本题中想用的就是哈希表，所以采用unordered_map
*/
#include <iostream>
#include <string>
#include <cstring>
#include <unordered_map>
using namespace std;
const int N = 4e5 + 1; // 总状态数最多也就9!(362880)种，二维下的种类数不太好想，一维下就很简单了，简单的排列问题
string q[N];
unordered_map<string, int> dis;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int bfs(string start)
{
int hh = 0, tt = -1;
dis[start] = 0;
q[++ tt] = start;
string end = "12345678x";
while (hh <= tt)
{
// 虽然现在的存储形式是字符串，但是我们需要把字符串转换为矩阵，经过变换后再变为字符串。不过这里的字符串和矩阵之间的转换并不能真的去做而是通过坐标的变换来实现
string t = q[hh ++];
int k = t.find('x');
int x = k / 3, y = k % 3; // 从字符串映射到矩阵
if (t == end) return dis[t];
for (int i = 0; i < 4; ++ i)
{
int a = x + dx[i], b = y + dy[i];
if (a >= 0 && a < 3 && b >= 0 && b < 3)
{
string tmp = t;
swap(tmp[k], tmp[a * 3 + b]); // 从矩阵映射到字符串
if (!dis.count(tmp)) // 这个状态之前没有访问过
{
q[++ tt] = tmp;
dis[tmp] = dis[t] + 1;
}
}
}
}
return -1;
}
int main()
{
string c, start;
for (int i = 0; i < 9; ++ i)
{
cin >> c;
start += c;
}
cout << bfs(start) << endl;
return 0;
}