Тэнцвэртэй хаалтын дараалал¶
Тэнцвэртэй хаалтын дараалал гэдэг нь зөвхөн хаалтуудаас тогтох тэмдэгт мөр бөгөөд энэ дараалалд тодорхой тоо ба математик үйлдлүүдийг оруулбал хүчинтэй математик илэрхийлэл гарна. Албан ёсоор тэнцвэртэй хаалтын дарааллыг дараах байдлаар тодорхойлж болно:
- $e$ (хоосон тэмдэгт мөр) нь тэнцвэртэй хаалтын дараалал.
- хэрэв $s$ нь тэнцвэртэй хаалтын дараалал бол $(s)$ мөн адил.
- хэрэв $s$ ба $t$ нь тэнцвэртэй хаалтын дараалал бол $s t$ мөн адил.
Жишээ нь $(())()$ нь тэнцвэртэй хаалтын дараалал боловч $())($ биш.
Мэдээж та олон төрлийн хаалттай бусад хаалтын дарааллыг мөн үүнтэй адил байдлаар тодорхойлж болно.
Энэ өгүүлэлд бид тэнцвэртэй хаалтын дараалалтай холбоотой зарим сонгодог бодлогыг авч үзнэ (энгийн байлгах үүднээс бид тэдгээрийг зүгээр л дараалал гэж нэрлэнэ): шалгах, дарааллын тоо, лексикографын дараагийн дарааллыг олох, тодорхой хэмжээтэй бүх дарааллыг үүсгэх, дарааллын индексийг олох, $k$-р дарааллыг үүсгэх. Мөн бид бодлогуудын хоёр хувилбарыг авч үзнэ: зөвхөн нэг төрлийн хаалт зөвшөөрөгдсөн энгийн хувилбар, ба олон төрөлтэй хэцүү тохиолдол.
Тэнцвэрийг шалгах¶
Бид өгөгдсөн тэмдэгт мөр тэнцвэртэй эсэхийг шалгахыг хүсэж байна.
Эхлээд зөвхөн нэг төрлийн хаалт байна гэж үзье. Энэ тохиолдолд маш энгийн алгоритм бий. $\text{depth}$ нь одоогийн нээлттэй хаалтын тоо байг. Эхэндээ $\text{depth} = 0$. Бид тэмдэгт мөрийн бүх тэмдэгтээр давтаж, хэрэв одоогийн хаалтын тэмдэгт нээх хаалт бол $\text{depth}$-г нэмэгдүүлэх, эс бөгөөс багасгана. Хэрэв ямар нэг үед $\text{depth}$ хувьсагч сөрөг болвол, эсвэл эцэст нь $0$-ээс ялгаатай бол тэмдэгт мөр тэнцвэртэй дараалал биш. Эс бөгөөс тийм.
Хэрэв хэд хэдэн төрлийн хаалт оролцвол алгоритмыг өөрчлөх хэрэгтэй. $\text{depth}$ тоолуурын оронд бид стек үүсгэх ба түүнд тааралдсан бүх нээх хаалтыг хадгална. Хэрэв одоогийн хаалтын тэмдэгт нээх хаалт бол бид түүнийг стект хийнэ. Хэрэв энэ нь хаах хаалт бол бид стек хоосон биш эсэх, стекийн орой дахь элемент одоогийн хаах хаалттай ижил төрлийн эсэхийг шалгана. Хэрэв хоёр нөхцөл хоёулаа хангагдвал бид стекээс нээх хаалтыг хасна. Хэрэв ямар нэг үед нөхцөлүүдийн нэг нь хангагдахгүй бол, эсвэл эцэст нь стек хоосон биш бол тэмдэгт мөр тэнцвэртэй биш. Эс бөгөөс тийм.
Тэнцвэртэй дарааллын тоо¶
Томьёо¶
Зөвхөн нэг төрлийн хаалттай тэнцвэртэй хаалтын дарааллын тоог Каталаны тоо ашиглан тооцоолж болно. $2n$ урттай ($n$ хос хаалт) тэнцвэртэй хаалтын дарааллын тоо нь:
Хэрэв бид $k$ төрлийн хаалт зөвшөөрвөл хос бүр $k$ төрлийн аль нэг (бусдаас үл хамааран) байж болох тул тэнцвэртэй хаалтын дарааллын тоо нь:
Динамик программчлал¶
Нөгөө талаас эдгээр тоог динамик программчлал ашиглан тооцоолж болно. $d[n]$ нь $n$ хос хаалттай зөв хаалтын дарааллын тоо байг. Эхний байрлалд үргэлж нээх хаалт байдгийг анхаарна уу. Мөн хожим хаа нэгтээ уг хосын харгалзах хаах хаалт байна. Энэ хосын дотор тэнцвэртэй хаалтын дараалал байх ба үүнтэй адил энэ хосын дараа тэнцвэртэй хаалтын дараалал байх нь тодорхой. Тиймээс $d[n]$-г тооцоолохын тулд бид энэ эхний хаалтын хосын дотор $i$ хос хаалттай хэдэн тэнцвэртэй дараалал, энэ хосын дараа $n-1-i$ хостой хэдэн тэнцвэртэй дараалал байгааг харна. Ингэснээр томьёо дараах хэлбэртэй болно:
Энэ рекуррентийн анхны утга нь $d[0] = 1$.
Лексикографын дараагийн тэнцвэртэй дарааллыг олох¶
Энд бид зөвхөн нэг хүчинтэй хаалтын төрөлтэй тохиолдлыг авч үзнэ.
Тэнцвэртэй дараалал өгөгдсөн үед бид дараагийн (лексикографын дарааллаар) тэнцвэртэй дарааллыг олох ёстой.
Энэ байрлал хүртэл нээх хаалтаас илүү хаах хаалт байх нөхцөлийг зөрчихгүйгээр хаах хаалтаар солиж болох хамгийн баруун талын нээх хаалтыг олох ёстой нь ойлгомжтой байх ёстой. Энэ байрлалыг сольсны дараа бид тэмдэгт мөрийн үлдсэн хэсгийг лексикографын хамгийн бага байдлаар дүүргэж болно: өөрөөр хэлбэл эхлээд аль болох олон нээх хаалтаар, дараа нь үлдсэн байрлалуудыг хаах хаалтаар дүүргэнэ. Өөрөөр хэлбэл бид аль болох урт угтварыг өөрчлөхгүй үлдээж, дагаврыг лексикографын хамгийн багаар сольно.
Энэ байрлалыг олохын тулд бид тэмдэгтээр баруунаас зүүн тийш давтаж, нээх ба хаах хаалтын баланс $\text{depth}$-г хадгална. Нээх хаалттай тааралдвал бид $\text{depth}$-г багасгах, хаах хаалттай тааралдвал нэмэгдүүлнэ. Хэрэв бид ямар нэг үед нээх хаалттай тааралдаж, энэ тэмдэгтийг боловсруулсны дараа баланс эерэг байвал бид өөрчилж болох хамгийн баруун талын байрлалыг олсон болно. Бид тэмдэгтийг өөрчилж, баруун талд нэмэх ёстой нээх ба хаах хаалтын тоог тооцоолж, тэдгээрийг лексикографын хамгийн бага байдлаар байрлуулна.
Хэрэв бид тохиромжтой байрлал олохгүй бол энэ дараалал аль хэдийн боломжит хамгийн их нь бөгөөд хариу байхгүй.
bool next_balanced_sequence(string & s) {
int n = s.size();
int depth = 0;
for (int i = n - 1; i >= 0; i--) {
if (s[i] == '(')
depth--;
else
depth++;
if (s[i] == '(' && depth > 0) {
depth--;
int open = (n - i - 1 - depth) / 2;
int close = n - i - 1 - open;
string next = s.substr(0, i) + ')' + string(open, '(') + string(close, ')');
s.swap(next);
return true;
}
}
return false;
}
Энэ функц дараагийн тэнцвэртэй хаалтын дарааллыг $O(n)$ хугацаанд тооцоолж, дараагийнх байхгүй бол false буцаана.
Бүх тэнцвэртэй дарааллыг олох¶
Заримдаа тодорхой $n$ урттай бүх тэнцвэртэй хаалтын дарааллыг олж гаргах шаардлагатай байдаг.
Тэдгээрийг үүсгэхийн тулд бид лексикографын хамгийн бага дараалал $((\dots(())\dots))$-ээс эхэлж, дараа нь өмнөх хэсэгт тайлбарласан алгоритмаар лексикографын дараагийн дараалуудыг үргэлжлүүлэн олж болно.
Гэвч хэрэв дарааллын урт тийм ч урт биш бол (жишээ нь $n$ нь $12$-оос бага) бид C++ STL-ийн next_permutation функцээр бүх сэлгэмэлийг тав тухтай үүсгэж, тус бүрийг тэнцвэртэй эсэхийг шалгаж болно.
Мөн тэдгээрийг динамик программчлалаар бүх дарааллыг тоолоход ашигласан санаагаар үүсгэж болно. Бид эдгээр санааг дараагийн хоёр хэсэгт авч үзнэ.
Дарааллын индекс¶
$n$ хос хаалттай тэнцвэртэй хаалтын дараалал өгөгдсөн. Бид $n$ хос хаалттай бүх тэнцвэртэй дарааллын лексикографоор эрэмбэлэгдсэн жагсаалт дахь түүний индексийг олох ёстой.
$d[i][j]$ туслах массивыг тодорхойлъё, энд $i$ нь хаалтын дарааллын урт (хагас тэнцвэртэй, хаах хаалт бүр харгалзах нээх хаалттай, гэхдээ нээх хаалт бүр заавал харгалзах хаах хаалттай биш), $j$ нь одоогийн баланс (нээх ба хаах хаалтын зөрүү). $d[i][j]$ нь параметрүүдэд тохирох ийм дарааллын тоо юм. Бид эдгээр тоог зөвхөн нэг хаалтын төрлөөр тооцоолно.
Эхлэлийн утга $i = 0$-ийн хувьд хариу ойлгомжтой: $d[0][0] = 1$, ба $j > 0$-ийн хувьд $d[0][j] = 0$. Одоо $i > 0$ гэе, бид дараалал дахь сүүлийн тэмдэгтийг харна. Хэрэв сүүлийн тэмдэгт нээх хаалт $($ байсан бол өмнөх төлөв нь $(i-1, j-1)$, хэрэв хаах хаалт $)$ байсан бол өмнөх төлөв нь $(i-1, j+1)$ байна. Тиймээс бид рекурсийн томьёог олж авна:
Сөрөг $j$-ийн хувьд $d[i][j] = 0$ байх нь ойлгомжтой. Тиймээс бид энэ массивыг $O(n^2)$-д тооцоолж болно.
Одоо өгөгдсөн дарааллын индексийг үүсгэе.
Эхлээд зөвхөн нэг төрлийн хаалт байг. Бид одоо хэр зэрэг үүрлэгдсэнийг хэлдэг $\text{depth}$ тоолуурыг ашиглаж, дарааллын тэмдэгтүүдээр давтана. Хэрэв одоогийн тэмдэгт $s[i]$ нь $($-тэй тэнцүү бол бид $\text{depth}$-г нэмэгдүүлнэ. Хэрэв одоогийн тэмдэгт $s[i]$ нь $)$-тэй тэнцүү бол бид $($-ээр эхэлдэг бүх боломжит төгсгөлийг (эдгээр нь лексикографын дарааллаар бага дараалал) харгалзан хариуд $d[2n-i-1][\text{depth}+1]$-г нэмж, дараа нь $\text{depth}$-г багасгах ёстой.
Одоо $k$ ялгаатай хаалтын төрөл байг.
Тиймээс бид $\text{depth}$-г дахин тооцоолохоос өмнө одоогийн тэмдэгт $s[i]$-г харахдаа одоогийн тэмдэгтээс бага бүх хаалтын төрлүүдийг туулж, энэ хаалтыг одоогийн байрлалд байрлуулахыг оролдож (шинэ баланс $\text{ndepth} = \text{depth} \pm 1$ олж авах), дарааллыг дуусгах аргын тоог ($2n-i-1$ урт, $ndepth$ баланс) хариуд нэмнэ:
Энэ томьёог дараах байдлаар гаргаж болно: Эхлээд бид олон хаалтын төрөл байгааг "мартаж", зүгээр л $d[2n - i - 1][\text{ndepth}]$ хариуг авна. Одоо бид $k$ төрлийн хаалттай бол хариу хэрхэн өөрчлөгдөхийг авч үзнэ. Бидэнд $2n - i - 1$ тодорхойгүй байрлал байгаа бөгөөд эдгээрийн $\text{ndepth}$ нь нээх хаалтуудын улмаас аль хэдийн урьдчилан тодорхойлогдсон. Гэвч бусад бүх хаалт ($(2n - i - 1 - \text{ndepth})/2$ хос) дурын төрлийн байж болох тул бид тоог $k$-ийн ийм зэргээр үржүүлнэ.
$k$-р дарааллыг олох¶
$n$ нь дараалал дахь хаалтын хосын тоо байг. Бид өгөгдсөн $k$-ийн хувьд бүх тэнцвэртэй дарааллын лексикографоор эрэмбэлэгдсэн жагсаалт дахь $k$-р тэнцвэртэй дарааллыг олох ёстой.
Өмнөх хэсэгт байсан шиг бид $d[i][j]$ туслах массив буюу $j$ балансаар $i$ урттай хагас тэнцвэртэй хаалтын дарааллын тоог тооцоолно.
Эхлээд бид зөвхөн нэг хаалтын төрлөөс эхэлнэ.
Бид үүсгэхийг хүсэж буй тэмдэгт мөрийн тэмдэгтүүдээр давтана. Өмнөх бодлогод байсан шиг бид $\text{depth}$ тоолуур буюу одоогийн үүрлэлтийн гүнийг хадгална. Байрлал бүрд бид нээх эсвэл хаах хаалт байрлуулах эсэхээ шийдэх ёстой. Нээх хаалт байрлуулахын тулд $d[2n - i - 1][\text{depth}+1] \ge k$ үнэн байх ёстой. Хэрэв тийм бол бид $\text{depth}$ тоолуурыг нэмэгдүүлж, дараагийн тэмдэгт рүү шилжинэ. Эс бөгөөс бид $k$-г $d[2n - i - 1][\text{depth}+1]$-ээр багасгаж, хаах хаалт байрлуулж, цааш шилжинэ.
string kth_balanced(int n, int k) {
vector<vector<int>> d(2*n+1, vector<int>(n+1, 0));
d[0][0] = 1;
for (int i = 1; i <= 2*n; i++) {
d[i][0] = d[i-1][1];
for (int j = 1; j < n; j++)
d[i][j] = d[i-1][j-1] + d[i-1][j+1];
d[i][n] = d[i-1][n-1];
}
string ans;
int depth = 0;
for (int i = 0; i < 2*n; i++) {
if (depth + 1 <= n && d[2*n-i-1][depth+1] >= k) {
ans += '(';
depth++;
} else {
ans += ')';
if (depth + 1 <= n)
k -= d[2*n-i-1][depth+1];
depth--;
}
}
return ans;
}
Одоо $k$ төрлийн хаалт байг. Шийдэл нь бид $d[2n-i-1][\text{ndepth}]$ утгыг $k^{(2n-i-1-\text{ndepth})/2}$-ээр үржүүлж, дараагийн тэмдэгтэд өөр өөр хаалтын төрөл байж болохыг харгалзан үзэх ёстойгоороо л бага зэрэг ялгаатай.
Дугуй ба дөрвөлжин гэсэн хоёр төрлийн хаалт ашигласан хэрэгжүүлэлт энд байна:
string kth_balanced2(int n, int k) {
vector<vector<int>> d(2*n+1, vector<int>(n+1, 0));
d[0][0] = 1;
for (int i = 1; i <= 2*n; i++) {
d[i][0] = d[i-1][1];
for (int j = 1; j < n; j++)
d[i][j] = d[i-1][j-1] + d[i-1][j+1];
d[i][n] = d[i-1][n-1];
}
string ans;
int shift, depth = 0;
stack<char> st;
for (int i = 0; i < 2*n; i++) {
// '('
shift = ((2*n-i-1-depth-1) / 2);
if (shift >= 0 && depth + 1 <= n) {
int cnt = d[2*n-i-1][depth+1] << shift;
if (cnt >= k) {
ans += '(';
st.push('(');
depth++;
continue;
}
k -= cnt;
}
// ')'
shift = ((2*n-i-1-depth+1) / 2);
if (shift >= 0 && depth && st.top() == '(') {
int cnt = d[2*n-i-1][depth-1] << shift;
if (cnt >= k) {
ans += ')';
st.pop();
depth--;
continue;
}
k -= cnt;
}
// '['
shift = ((2*n-i-1-depth-1) / 2);
if (shift >= 0 && depth + 1 <= n) {
int cnt = d[2*n-i-1][depth+1] << shift;
if (cnt >= k) {
ans += '[';
st.push('[');
depth++;
continue;
}
k -= cnt;
}
// ']'
ans += ']';
st.pop();
depth--;
}
return ans;
}