01/10/2018, 10:15

Backtracking how to understand

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);
  }

bi giờ mình muốn loại cái số 0 ở đầu trong đoạn code Try thì làm thế nào?
Tại sao x[i-1]+1
Tai sao n-k+i
Tại sao i==k
Sửa bài toán
cho n=3;k=2 ==> xuat ra [ 01, 02, 12 ] được không??

Gió viết 12:17 ngày 01/10/2018

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)));

Thuc Nguyen Tan viết 12:26 ngày 01/10/2018

      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ì ???

Nguyễn Đình Biển viết 12:30 ngày 01/10/2018

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.
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.
Do dãy chỉ tăng nên cấu hình cuối cùng lớn nhất là tại đó.
Tập hợp gồm k phần tử nên tới k rồi ko đệ quy nữa.
như câu 1 như đưa x[0] = -1 vàx[i] <= (n-k+i-1)