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 !

 

13 COMMENTS

  1. 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

  2. Ô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 đó. Có các lưu ý:
    + Ông A k được tính vào số lượng của quân
    + Mỗi người lính chỉ tham gia được vào tối đa 3 trận đánh. Sau 3 trận đánh nếu đi nhóm binh sĩ đó còn sống thì cũng giải tán.
    + Mỗi trận đánh thì tất cả số binh sĩ đều tham gia.
    + Đánh nhau chết theo tỉ lệ 1: 1. Ai tham gia trước sẽ bị chết trước

    Điều kiện input: số cổng =2 và <=1000
    Tìm chi phí nhỏ nhất để ông A có thể đi qua đoạn đường B

    VD: Có 7 cổng
    1 2 3 4 5 6 7
    Số binh sĩ 10 70 80 20 50 30 10
    Chi phí 100 5 15 60 90 80 10

    Có thể tính chi phí đi nhỏ nhất
    1 2 3 4 5 6 7
    Số binh sĩ 10 70 80 20 50 30 10
    Chi phí 100 5 15 60 90 80 10
    Chọn pp Pass Hire Hire Battle Battle Battle Pass
    Chi phí 100 110 140 150

  3. 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 = sc.nextInt();
    int b = sc.nextInt();
    Fire[a][b] = 1;
    sparks[i] = new XY(a,b);
    }
    h20s = sc.nextInt();
    H20 = new int[n+1][m+1];
    for(int i=1;i<=h20s;i++) {
    H20[sc.nextInt()][sc.nextInt()]=1;
    }
    exits = sc.nextInt();
    Exit = new int[n+1][m+1];
    for(int i=1;i<=exits;i++) {
    Exit[sc.nextInt()][sc.nextInt()] = 1;
    }
    Cacbol = new int[n+1][m+1];
    for(int i=1;i<=n;i++) {
    for(int j=1;j<=m;j++) {
    Cacbol[i][j]=sc.nextInt();
    }
    }
    visited = new int[n+1][m+1];
    for(int i=1;i<=fires;i++) {
    LoangLua(sparks[i]);
    }
    max=-1;
    road[1] = new XY(srow,scol);
    visited[srow][scol]=1;
    Try(1,new XY(srow,scol), Cacbol[srow][scol]);

    // for (int i = 1; i <= n; i++) {
    // for (int j = 1; j =1&&xy.x=1&&xy.y<=m;
    }
    static void LoangLua(XY xy) {
    for(int i=0;iFire[xy.x][xy.y]+1) {
    Fire[xy1.x][xy1.y]=Fire[xy.x][xy.y]+1;;
    LoangLua(xy1);
    }
    }
    }
    static void Try(int time,XY xy,int sum) {
    if(Fire[xy.x][xy.y] max) {
    max=sum;
    }
    }
    for(int i=0;i time+1) {
    visited[xy1.x][xy1.y]=1;
    if(H20[xy1.x][xy1.y]==1) {// ô nhảy đến tiếp theo là nước, thì thời gian nó ở sẽ là t+1 và t+2
    road[time+1] = road[time+2] = xy1;
    Try(time+2,xy1,sum+Cacbol[xy1.x][xy1.y]);
    } else{
    road[time+1] = xy1;
    Try(time+1,xy1,sum+Cacbol[xy1.x][xy1.y]);
    }
    visited[xy1.x][xy1.y] = 0;
    }
    }
    }
    }
    }

  4. 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

  5. 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 3 1 3 4 3
    4 4 4 4 1 3 1 1 2
    26 0 49 24
    41 2 1 0
    17 52 35 20
    0 0 49 48
    4 5 1 1
    1 3 2
    6 2 3 1 3 2 5 1 5 2 1 3 5
    2 1 5 1 3
    73 23 76 49 77
    69 75 16 25 42
    0 0 34 36 26
    73 0 0 32 72
    5 5 1 5
    1 4 2
    6 3 5 2 1 1 4 2 5 5 3 5 4
    2 1 1 1 4
    86 74 68 87 0
    91 25 14 24 74
    59 70 97 77 70
    68 0 85 80 27
    99 25 24 72 81
    5 5 1 1
    2 3 3 3 1
    4 1 4 2 1 2 3 1 5
    1 1 5
    94 22 26 33 44
    24 112 0 100 10
    0 10 0 0 107
    78 69 46 0 57
    105 109 103 0 82
    5 5 1 1
    2 2 4 3 4
    1 2 3
    7 5 1 1 5 1 4 3 1 1 3 4 5 5 2
    0 0 113 85 0
    4 0 52 0 0
    65 116 117 0 57
    31 101 2 32 76
    0 63 9 0 112
    5 6 5 1
    1 5 5
    5 3 6 2 2 3 1 1 3 4 3
    4 5 4 5 6 1 1 1 5
    141 94 134 73 105 148
    140 1 0 0 102 157
    38 43 33 0 75 18
    0 52 135 151 0 45
    0 29 0 0 0 114
    5 6 1 6
    2 3 2 1 1
    4 3 4 5 1 2 2 5 5
    6 3 6 5 6 2 1 4 6 1 2 3 1
    0 24 161 126 10 129
    0 162 33 44 52 0
    0 0 0 123 38 84
    91 53 0 0 86 149
    59 0 104 0 0 0
    5 6 5 5
    2 4 5 5 1
    11 3 3 5 6 1 5 4 4 3 6 2 5 1 6 4 3 3 1 4 6 2 6
    7 5 4 5 3 1 6 5 2 1 1 4 1 3 1
    6 29 105 12 0 165
    136 14 56 136 82 0
    0 30 25 37 90 0
    34 153 52 62 0 54
    0 34 56 124 13 28
    5 7 5 7
    1 3 5
    8 4 2 3 6 5 1 3 4 5 2 3 1 2 1 4 3
    2 5 3 1 1
    98 182 117 0 74 61 113
    0 77 58 0 84 155 0
    0 0 72 142 0 25 0
    134 0 0 161 0 170 193
    217 36 153 181 0 23 104
    6 7 6 2
    3 3 3 3 2 1 7
    3 1 2 4 3 4 4
    1 1 6
    126 47 44 0 21 81 0
    29 0 113 181 0 103 6
    198 0 0 227 201 16 0
    169 36 0 236 94 0 8
    32 114 38 184 0 69 238
    78 139 166 22 158 186 77
    6 8 2 8
    1 4 6
    14 4 1 1 3 1 4 4 3 2 3 2 5 3 2 6 3 2 1 3 1 6 4 1 2 3 7 5 3
    7 5 8 6 4 6 8 1 1 1 6 3 8 6 3
    10 45 0 216 238 96 84 189
    0 0 124 23 90 148 65 173
    134 166 32 80 99 111 9 105
    0 0 250 0 144 0 253 249
    0 0 249 232 58 8 170 94
    230 22 155 94 82 0 0 212
    6 8 1 2
    1 1 8
    7 5 2 5 1 4 5 3 3 4 1 6 5 4 8
    11 6 1 5 8 4 1 3 8 2 1 6 8 2 8 3 1 1 7 6 4 4 8
    157 33 170 151 0 272 189 0
    25 73 154 252 0 162 157 0
    84 70 277 259 0 87 230 138
    247 0 51 213 0 6 210 128
    241 143 225 201 70 118 141 276
    118 115 0 0 266 240 0 248
    6 8 5 8
    2 5 2 4 6
    12 3 1 1 8 3 8 6 4 2 8 3 5 1 4 4 3 2 4 3 7 1 2 6 5
    7 1 5 6 6 1 2 1 8 4 1 6 5 6 1
    0 278 71 73 120 26 290 78
    18 159 24 180 67 177 70 96
    222 119 256 0 183 132 41 213
    196 0 0 199 180 0 32 184
    0 0 206 0 282 223 105 295
    16 278 158 150 29 295 76 199
    6 8 5 1
    2 2 7 2 1
    12 6 3 3 7 6 6 2 5 1 8 5 6 2 8 4 2 1 5 3 8 2 3 5 4
    7 6 1 6 2 1 7 4 1 6 3 6 7 6 8
    256 42 130 191 305 241 311 208
    0 196 109 146 255 174 0 0
    257 23 31 295 26 141 41 135
    244 175 174 38 293 75 88 112
    200 78 0 1 55 276 201 0
    114 0 221 139 0 185 289 192
    6 8 5 1
    1 3 6
    8 6 8 5 6 5 3 5 7 4 7 1 2 1 7 2 5
    2 5 8 6 3
    328 88 238 0 225 159 0 0
    173 0 0 180 127 184 227 0
    194 12 68 165 31 0 97 288
    33 0 197 308 0 27 173 107
    93 321 207 0 4 55 0 224
    112 256 153 0 0 331 228 16

  6. 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 đó?

LEAVE A REPLY

Please enter your comment!
Please enter your name here