Liệt kê các hoán vị tổ hợp sử dụng code c++

13
12141
Liệt kê các hoán vị tổ hợp sử dụng code c++
Liệt kê các hoán vị tổ hợp sử dụng code c++

Bài toán: Viết chương trình liệt kê các hoán vị của {1,2,…,n}.

  • Input

  •  
  • Ouput

Giới thiệu bài toán liệt kê hoán vị tổ hợp

Hoán vị tổ hợp là gì ?

Hoán vị là một dãy theo thứ tự chứa mỗi phần tử của một tập hợp một và các phần tử đó chỉ xuất hiện một lần duy nhất.

Ví dụ: A {1, 2, 3} thì {1, 2, 3} hoặc {2, 1, 3} được gọi là một hoán vị không lặp của A.

Bài toán này chúng ta chỉ làm về hoán vị không lặp.

Bài toán liệt kê hoán vị tổ hợp

Yêu cầu của bài toán là chúng ta phải nhập một số nguyên dương n, sau đó chương trình phải liệt kê tất cả các hoán vị của 1,2,3…n

Giả sử với n = 3:

  • Khi đó hoán vị đầu tiên sẽ là 1 2 3
  • Hoán vị tiếp theo sẽ phải lớn hơn hoán vị ban đầu 1 3 2
  • Tương tự như vậy hoán cuối cùng sẽ là hoán vị lớn nhất 3 2 1

Hướng dẫn giải bài toán liệt kê hoán vị tổ hợp

Sử dụng phương pháp quay lui để giải quyết bài toán

Chúng ta sẽ dùng một mảng A[n+1] lưu các hoán vị, khi đó các hoán vị sẽ được biểu diễn như sau:

A[1], A[2], A[3], …,A[n].

Trong đó A[i] ≠ A[j] Với mọi i,j ∈ [1,n] và i ≠ j.

Để xác nhận một phần tử chỉ được dùng một lần ta sẽ dùng mảng Bool để lưu đánh dấu. Nếu phần tử chưa sử dụng thì sẽ có giá trị là 0 ngược lại sẽ có giá trị là 1. Ban đầu ta khởi tạo tất cả các phần tử trong mảng đều có giá trị là 0.

Ý tưởng của phương pháp quay lui là chúng ta sẽ chọn ra một phần tử chưa sử dụng. Lưu phần tử đó vào một cấu hình tổ hợp, sau đó đánh dấu nó đã sử dụng. Ta sẽ lặp lại công việc như trên đến khi đủ cấu hình cho một tổ hợp thì sẽ xuất ra màn hình. Sau khi xuất ra ta lại quay trở lại bước trước đó để đánh dấu là nó chưa được chọn.

Ta có thể hình dung bài toán như hình vẽ sau: Với n=3 thì bài toán trở thành liệt kê các hoán vị của các phần tử 1, 2, 3. Các hoán vị được liệt kê theo thứ tự từ điển tăng dần như hình vẽ sau:

hoán vị
Liệt kê hoán vị

Code tham khảo

 

Bài viết của mình đến đây là kết thúc. Cám ơn các bạn đã theo dõi !

 

avatar

Website này sử dụng Akismet để hạn chế spam. Tìm hiểu bình luận của bạn được duyệt như thế nào.

  Subscribe  
newest oldest most voted
Notify of
hahahihi
Guest
hahahihi

tuyet voi ong mat troi

hahahihi
Guest
hahahihi

that tuyet voi

hahahihi
Guest
hahahihi

kien thuc qua hay

Manh
Guest
Manh

Mình có bài toán này nhờ bạn giải giúp
dãy gồm 5 chữ số 0-0-0-3-5
nếu dùng ánh xạ thì sẽ ra kết quả trùng nhau
ví dụ số hoán vị số 0 tại vị trí 1 và vị trí 3 thì sẽ ra kết quả trùng nhau là 00035
Vậy làm thế nào để tránh các kết quả trùng nhau đó?

son
Guest
son

aaaaaaaaaaaaaaaaaaaaaaaa

son
Guest
son

dasfkdjjfsdjvbjsvjk
sdfsdsvnnm

son
Guest
son

50 4 4 1 1 1 4 2 2 2 2 3 2 6 4 1 2 1 4 4 1 4 3 1 1 3 0 11 17 7 3 0 9 1 2 6 0 8 0 0 2 0 4 4 4 4 1 2 3 6 4 1 3 1 1 2 1 4 1 1 2 4 2 1 1 2 4 27 13 3 21 0 13 0 29 15 0 39 38 24 4 29 35 4 4 1 1 2 2 4 4 2 6 2 2 3 2 2 1 3… Read more »

son
Guest
son

Case #1
35
Case #2
102
Case #3
69
Case #4
172
Case #5
185
Case #6
219
Case #7
100
Case #8
538
Case #9
362
Case #10
342
Case #11
-1
Case #12
-1
Case #13
278
Case #14
2371
Case #15
866
Case #16
639
Case #17
856
Case #18
896
Case #19
1939
Case #20
1829
Case #21
3459
Case #22
794
Case #23
2237
Case #24
2375
Case #25
2897
Case #26
4979
Case #27
-1
Case #28
5123
Case #29
7052
Case #30
-1
Case #31
3742
Case #32
-1
Case #33
4483
Case #34
-1
Case #35
6129
Case #36
1259
Case #37
1109
Case #38
8367
Case #39
-1
Case #40
1046

son
Guest
son

package Hugo; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Scanner; public class Solution { static int n,m,srow,scol,max; static int Fire[][]; static XY sparks[],road[]; static int fires,h20s,exits; static int H20[][],Exit[][],Cacbol[][],visited[][]; static int dx[]= {1,-1,0,0}; static int dy[]= {0,0,1,-1}; public static void main(String[] args) throws FileNotFoundException { System.setIn(new FileInputStream(“src/Hugo/input.txt”)); Scanner sc = new Scanner(System.in); int testcase = sc.nextInt(); for(int t=1;t<=testcase;t++) { n = sc.nextInt(); m = sc.nextInt(); srow = sc.nextInt(); scol = sc.nextInt(); Fire = new int [n+1][m+1]; sparks = new XY[m*n+1]; road = new XY[1000000]; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { Fire[i][j]=1000000; } } fires = sc.nextInt(); for(int i=1;i<=fires;i++) { int a =… Read more »

adasd
Guest
adasd

code c++ ko chạy dc dù t xài pascal

son
Guest
son

Ông A cần đi qua 1 đoạn đường B. Trên đoạn đường đi qua có N cổng. Tại mỗi cổng có 1 số lượng binh sĩ và giá để đi qua cổng đó. Muốn đi qua mỗi cổng ông A có 3 cách lựa chọn. 1. Pass Trả số tiền quy định ở cổng đó để được đi qua 2. Hire Trả gấp đôi số tiền ở cổng đó để thuê số binh sĩ gộp vào đoàn quân của mình 3. battle Điều kiện để đánh nhau là số quân của ông A >= số lượng lính tại cổng đó.… Read more »

son
Guest
son

input
5
7
10 100
70 5
80 15
20 60
50 90
30 80
10 10
9
600 800
300 400
300 400
1000 400
300 600
100 300
600 300
600 500
1000 300
11
1000 10
700 900
400 500
300 10
900 900
300 10
50 900
50 900
700 900
500 900
50 10
20
896 546
543 216
454 310
408 367
40 602
252 582
954 627
850 234
763 479
232 278
301 538
528 508
936 154
629 443
758 336
432 700
882 256
278 738
517 882
317 136
20
410 610
831 909
675 629
421 774
386 869
544 219
492 414
996 557
499 482
231 285
804 978
304 881
489 911
75 315
927 648
252 914
330 396
937 133
495 882
813 717

son
Guest
son

output
#1 150
#2 3000
#3 2370
#4 4721
#5 8231