Backtracking how to understand

#1

Mình có làm một file trên punker về xuất danh sách tổ hợp chập k của n phần tử, các bạn xem link bên dưới
Vi du backtracking

kết quả chạy ra là:

[[0,1,2],[0,1,3],[0,1,4],[0,2,3],[0,2,4],[0,3,4]]

this is code

   $scope.liet_ke_to_hop_chap_k_of_n_phan_tu = function() {
    //cho n=3,k=2 ; liet ke nhu sau 12,13,23...			
    function Try(i) {
      var j;
      for (j = x[i - 1] + 1; j <= n - k + i; j++) {
        x[i] = j; //thử cho giá trị nhỏ nhất
        if (i == k) { //in ra//cũng như đệ qui thôi, phải có điểm kết thúc
          $scope.print(x);
        } else {
          Try(i + 1); //thử với giá trị kế tiếp
        }
      }
    }
    var x = [];
    x[0] = 0;
    var n = 4;
    var k = 2;
    Try(1);
  }
  1. bi giờ mình muốn loại cái số 0 ở đầu trong đoạn code Try thì làm thế nào?
  2. Tại sao x[i-1]+1
  3. Tai sao n-k+i
  4. Tại sao i==k
  5. Sửa bài toán
    cho n=3;k=2 ==> xuat ra [ 01, 02, 12 ] được không??
#2
  1. Muốn bỏ 0 ở đầu $scope.ds.push(JSON.parse(JSON.stringify(x.slice(1))));
  • Vì khi xuất tổ hợp theo thứ tự tăng dần, số sau không bé hơn số trước
  • n - k + i vì nếu số sau lớn hơn số trước, nên số xếp sau sẽ được cộng ít nhất k - i đơn vị để số cuối cùng không lớn hơn n, Cái này có 2 mục đích:
  • Ngăn mọi x[i] <= n
  • Không cần kiểm tra các tổ hợp có thõa mãn hay không (nếu Điều kiện # n - k + i)
  • i == k vì chọn tổ hợp chập k của n phần tử
  • $scope.ds.push(JSON.parse(JSON.stringify(x.slice(1).map(x = > x - 1)));
1 Like
#3 
      function Try(i) {
      var j;
      for (j = x[i - 1] + 1; j <= n - k + i; j++) {
        x[i] = j; //thử cho giá trị nhỏ nhất
        if (i == k) { //in ra//cũng như đệ qui thôi, phải có điểm kết thúc
          alert(JSON.stringify(x));
        } else {
          Try(i + 1); //thử với giá trị kế tiếp
        }
      }
    }
    var x = [];
    x[0] = 0;
    var n = 4;
    var k = 2;
    Try(1);

Mình muốn nó bắt đầu bằng số không;
cho n=3; k=2 ---->xuat ra la 01,02,12
chứ không phải 12,13,23

splice chỉ là để chữa cháy thôi : nhưng hình như phải splice(0,1);

Mình muốn custom là để nắm cấu trúc của nó: Chẳng hạn tại sao Try(1) mà không là Try(0)

Mình đang lý luận thế này nhé:
n=3;k=2 {1,2,3}
Gọi xi là giá trị của phần tử thứ i trong x
==> xi-1+1 <= xi <= n-k+i điều này giải thích được tại sao j=x[i-1]+1;j<= n-k+i; j++
===>còn cái dòng i==k thì ???

#4
  1. Print từ x[1] trở đi, thực chất x[0] thêm vào để x[1] có thể chạy được (vìx[i-1] = x[0] khi i =1) chứ không phải là nghiệm(cấu hình) của bài toán.
  2. Tránh trường hợp lặp như 2,3 và 3,2 thì đưa nó về dãy chỉ tăng x[i+1] > x[i] với mọi i.
  3. Do dãy chỉ tăng nên cấu hình cuối cùng lớn nhất là tại đó.
  4. Tập hợp gồm k phần tử nên tới k rồi ko đệ quy nữa.
  5. như câu 1 như đưa x[0] = -1 vàx[i] <= (n-k+i-1)
#5

Bây giờ nâng cấp bài toán lên một tí
Cho array : a=[5,10,15] in ra (5,10) (5,15) (10,15)
thì phải làm sao?

#6

Coi hàm đơn ánh.Thay vì đưa ra x[i] thì đưa ra array[x[i]] thôi

#7

hay, chuyển về bài toán nguyên thủy, xem như tổ hợp của các index, thank you.

I demo your idea demo of backtracking combination word

Có hào hứng thì optimine lại nhé. happy coding!!!

Bi giờ anh em nào hào hứng thì làm bài : Cho con Mã chạy lung tung trên bàn cờ không ngứt %
How to start?

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?