1, 2, …, n-ийг бүх боломжит дарааллаар нь бичих backtracking арга. used[] array аль тоо авагдсаныг санана.

IntermediateХугацаа: O(n! · n)Санах ой: O(n)

Эхлээд жижиг бодлого

1, 2, 3-ыг хэдэн янзаар эгнүүлж болох вэ? Эхний байранд 3 сонголт, хоёр дахьд үлдсэн 2, сүүлийнхэд 1 сонголт байна. Тиймээс 3 × 2 × 1 = 6.

Код тэднийг толь бичгийн дарааллаар хэвлэнэ: 1 2 3, 1 3 2, 2 1 3, 2 3 1, 3 1 2, 3 2 1.

Энгийн аргаас санаа руу

n = 3 бол гурван давхар loop бичээд ижил тоог алгасаж болно. Гэхдээ n өөрчлөгдөх бүрт loop-ын тоо өөрчлөгдөнө. Тиймээс байр бүрийг recursion ашиглан бөглөнө.

solve(k) нь p[k]-д тоо тавина. Ямар тоо аль хэдийн авагдсаныг used[] array санана. Чөлөөтэй x бүрийг тавиад solve(k + 1)-ийг дуудна. Буцаж ирээд used[x] = false болгож x-ийг дараагийн оролдлогод чөлөөлнө.

Нэр томьёо ба тэмдэглэгээ

p[k]
Бичиж буй сэлгэмэлийн k дэх байр.
used[x]
x одоогийн сэлгэмэлд аль хэдийн орсон эсэх.
сэлгэмэл (permutation)
1..n-ийг давталтгүйгээр нэг дараалалд байрлуулсан нь. n! ширхэг бий.
backtrack
used[x] = false; буюу сонголтоо болиулах.
p
0
1
2
used
0
1
0
2
0
3
n = 3

1-ээс 3 хүртэлх тоонуудыг бүх боломжит дарааллаар нь байрлуулъя. p бол бичиж буй дараалал. used[x] нь x аль хэдийн авагдсан эсэхийг хадгална.

Алхам 1 / 37
Хурд
  • Авсан тоо
  • Сая тавьсан
  • Буцааж чөлөөлсөн
  • Бэлэн сэлгэмэл
Слайд 1 / 7

Хэдэн янзаар эгнэх вэ?

Гурван найз зургаа авахуулахаар эгнэх гэж байна. Хэдэн янзаар зогсож болох вэ? Бүх дарааллыг нэг нэгээр нь бичье.

permutations.cpp
#include <bits/stdc++.h>
using namespace std;
int n, p[10];
bool used[10];
void solve(int k) {
if (k == n) {
for (int i = 0; i < n; i++) cout << p[i] << ' ';
cout << '\n';
return;
}
for (int x = 1; x <= n; x++) {
if (!used[x]) {
p[k] = x;
used[x] = true;
solve(k + 1);
used[x] = false;
}
}
}
int main() {
cin >> n;
solve(0);
return 0;
}

Юунд хэрэгтэй вэ?

n тооны бүх n! сэлгэмэлийг (permutation) гаргана. Нэг тоог хоёр удаа авахгүйн тулд used[] array-д тэмдэглэх аргыг сурна.

Яаж ажилладаг вэ?

1. solve(k) нь p[k]-д ямар тоо тавихыг шийднэ. 2. k == n бол бүх байр дүүрсэн. p array-г хэвлэнэ. 3. x = 1, 2, …, n бүрийг үзнэ. used[x] = false буюу x чөлөөтэй бол: 4. p[k] = x гэж тавиад used[x] = true болгоно. Дараа нь solve(k + 1)-ийг дуудна. 5. Буцаж ирээд used[x] = false болгож x-ийг чөлөөлнө (backtrack). Оролт: нэг тоо n. Сэлгэмэлүүд толь бичгийн дарааллаар хэвлэгдэнэ.

Яагаад зөв, хэр хурдан бэ?

p[0..k−1] нь давталтгүй, used нь яг тэдгээрийг тэмдэглэсэн байна. solve(k) нь чөлөөтэй тоо бүрийг p[k]-д нэг нэгээр нь тавьж үздэг тул сэлгэмэл бүр яг нэг удаа гарна. x жижгээс том руу явдаг тул толь бичгийн дарааллаар хэвлэгдэнэ.

n! сэлгэмэл, тус бүрийг хэвлэхэд n: хугацаа O(n · n!). n = 8 бол 40 320 сэлгэмэл, хурдан. n = 10 бол 3 628 800, хэвлэх нь л удаан. n = 12 бол 479 сая, хэт удаан.

Түгээмэл алдаа

  • used[x] = false; мөрийг мартах. Эхний сэлгэмэлийн дараа бүх тоо авагдсан хэвээр үлдэж, ганц л сэлгэмэл гарна.
  • used[] array-г n хэмжээтэй зарлах. x нь 1..n тул used[n] хэрэгтэй, хэмжээ нь n + 1 байх ёстой.
  • Том n дээр бүх сэлгэмэлийг гаргах гэж оролдох. n! маш хурдан өсдөг.

Хязгаарын тохиолдол

  • n = 1: ганц сэлгэмэл 1.
  • n = 2: 1 2, 2 1.
  • Тоонуудад давталт байвал (жишээ нь 1, 1, 2) энэ код ижил сэлгэмэлийг давтаж хэвлэнэ. Ялгаатайг нь хэрэгтэй бол давталтыг тусад нь шийднэ.

Өөрийгөө шалга

  1. n = 4 бол хэдэн сэлгэмэл гарах вэ? Тав дахь нь юу вэ?

    Хариу харах

    24. Тав дахь нь 1 4 2 3.

  2. n = 3 үед solve(3) хэдэн удаа дуудагдах вэ?

    Хариу харах

    6 удаа. Сэлгэмэл бүрт нэг.

Гурван дадлага

Hint-ээ нээхээс өмнө өөрөө оролдоорой.

  1. 1.n = 3 үед 1 3 2-ын дараа p, used хэрхэн өөрчлөгдөж 2 1 3 гарахыг бич.

    Hint харах

    k = 2, k = 1 байрнаас буцаж ирээд k = 0 байранд 2-ыг тавина.

    Хариу ба тайлбар

    2-ыг p[2]-оос, 3-ыг p[1]-ээс чөлөөлнө. p[1]-д тавих өөр тоо байхгүй тул k = 0 рүү буцна. 1-ийг чөлөөлөөд p[0]-т 2, p[1]-д 1, p[2]-т 3 тавина.

  2. 2.Энэ кодын оронд next_permutation ашиглаж ижил гаралт гарга.

    Hint харах

    Эхлээд array-г 1 2 … n гэж бөглө.

    Хариу ба тайлбар

    do { хэвлэх; } while (next_permutation(p, p + n));. Эрэмбэлэгдсэн array-гээс эхэлбэл толь бичгийн дарааллаар бүгд гарна.

  3. 3."aab" string-ийн ялгаатай сэлгэмэлүүдийг гарга. Хэд байх вэ?

    Hint харах

    Эрэмбэлээд, ижил үсгийг нэг байранд хоёр удаа тавихгүй байхыг шалга.

    Хариу ба тайлбар

    3: "aab", "aba", "baa". Нэг байрны loop дотор s[i] == s[i - 1] ба !used[i - 1] бол алгасна. Эсвэл next_permutation давталтыг өөрөө алгасдаг.

Жишээ

Оролт

3

Гаралт

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1