Sản phẩm Descartes của các đối tượng trong javascript

Question

Tôi cần tạo một tập hợp đầy đủ các biến thể dựa trên danh sách N thuộc tính, trong khi vẫn giữ nguyên tên thuộc tính.

var input = [ 
    { 'colour' : ['red', 'green'] }, 
    { 'material' : ['cotton', 'wool', 'silk'] }, 
    { 'shape' : ['round', 'square', 'rectangle'] } 
]; 

var expected = [ 
    { 'colour': 'red', 'material': 'cotton', 'shape': 'round' }, 
    { 'colour': 'red', 'material': 'cotton', 'shape': 'square' }, 
    { 'colour': 'red', 'material': 'cotton', 'shape': 'rectangle' }, 
    { 'colour': 'red', 'material': 'wool', 'shape': 'round' }, 
    { 'colour': 'red', 'material': 'wool', 'shape': 'square' }, 
    { 'colour': 'red', 'material': 'wool', 'shape': 'rectangle' }, 
    { 'colour': 'red', 'material': 'silk', 'shape': 'round' }, 
    { 'colour': 'red', 'material': 'silk', 'shape': 'square' }, 
    { 'colour': 'red', 'material': 'silk', 'shape': 'rectangle' }, 
    { 'colour': 'green', 'material': 'cotton', 'shape': 'round' }, 
    { 'colour': 'green', 'material': 'cotton', 'shape': 'square' }, 
    { 'colour': 'green', 'material': 'cotton', 'shape': 'rectangle' }, 
    { 'colour': 'green', 'material': 'wool', 'shape': 'round' }, 
    { 'colour': 'green', 'material': 'wool', 'shape': 'square' }, 
    { 'colour': 'green', 'material': 'wool', 'shape': 'rectangle' }, 
    { 'colour': 'green', 'material': 'silk', 'shape': 'round' }, 
    { 'colour': 'green', 'material': 'silk', 'shape': 'square' }, 
    { 'colour': 'green', 'material': 'silk', 'shape': 'rectangle' } 
]; 

Có rất nhiều thuật toán xung quanh cho các sản phẩm tiêu chuẩn của mảng, nhưng tôi dường như không tìm thấy thuật toán nào cho các đối tượng bảo tồn khóa.

Hiệu suất không phải là mối lo ngại lớn vì sẽ không bao giờ có nhiều hơn một tá giá trị cho mỗi thuộc tính. Đơn đặt hàng không phải khớp chính xác với số expected.

Tôi đã thực hiện một nỗ lực ban đầu dựa trên các thuật toán tiêu chuẩn cho các danh sách, nhưng tôi đang gặp khó khăn:

function cartesianProduct(input, current) { 
    if (!input || input.length < 1) { 
     return []; 
    } 

    var head = input[0]; 
    var tail = input.slice(1); 
    var output = []; 

    for (var key in head) { 
     for (var i = 0; i < head[key].length; i++) { 
      if (typeof current == 'undefined') { 
       var current = {}; 
      } 

      current[key] = head[key][i]; 
      var productOfTail = cartesianProduct(tail, current); 
      output.push(current); 
      console.log(current); 
     } 
    } 

    return output; 
} 

console.log(cartesianProduct(input)); 

Answer 1

Khi bạn thoát khỏi ' 'i' là một vấn đề toàn cầu var', bạn có thể nhận được kết quả với mã này ví dụ:

var input = [ 
    { 'colour' : ['red', 'green'] }, 
    { 'material' : ['cotton', 'wool', 'silk'] }, 
    { 'shape' : ['round', 'square', 'rectangle'] } 
]; 

function cartesianProduct(input, current) { 
    if (!input || !input.length) { return []; } 

    var head = input[0]; 
    var tail = input.slice(1); 
    var output = []; 

    for (var key in head) { 
     for (var i = 0; i < head[key].length; i++) { 
      var newCurrent = copy(current);   
      newCurrent[key] = head[key][i]; 
      if (tail.length) { 
       var productOfTail = 
         cartesianProduct(tail, newCurrent); 
       output = output.concat(productOfTail); 
      } else output.push(newCurrent); 
     } 
    }  
    return output; 
} 

function copy(obj) { 
    var res = {}; 
    for (var p in obj) res[p] = obj[p]; 
    return res; 
} 


console.log(cartesianProduct(input));