Cho một mảng có kích thước y, chứa các mảng có kích thước n, làm thế nào tôi có thể trả về tất cả các kết hợp logic bằng Ruby?

Question

Điều tôi muốn làm là xử lý n bộ, trong khi mã tôi cung cấp bên dưới hoạt động với 4 bộ chính xác.

def show_combinations 
    @combos = [] 
    ['A', 'no A'].each do |a| 
    ['B', 'no B'].each do |b| 
     ['C', 'no C'].each do |c| 
     ['D', 'no D'].each do |d| 
      @combos << [a, b, c, d] 
     end 
     end 
    end 
    end 
end 

Làm thế nào tôi có thể cấu trúc mã sau này để đối phó với các tình huống sau: Với tôi có một loạt các kích thước y chứa mảng kích thước n, tôi muốn trả lại tất cả các kết hợp. Điều quan trọng cần lưu ý là chỉ có một mục trong mỗi mảng phụ có thể có trong kết quả. (Chẳng hạn như "Hồ sơ hoàn thành" cũng không thể có trong kết quả với "Không hồ sơ hoàn thành")

Bối cảnh:

Một người sử dụng có thể có một số nhiệm vụ: ví dụ, "Toàn bộ hồ sơ" hoặc "Thiết lập Email "hoặc bất cứ điều gì. Những nhiệm vụ có thể được biểu diễn như thế này:

@task_states = [["Completed Profile, NOT Completed Profile"], ["Set up Email", "NOT set up Email"]] 

Sau đó, đi qua @task_states vào phương pháp, kết quả sẽ được này:

[ 
["Completed Profile", "Set up Email"], 
["Completed Profile", "NOT set up Email"], 
["NOT Completed Profile", "Set up Email"], 
["NOT Completed Profile", "NOT Set up Email"] 
] 

Vì vậy, một mảng của mảng đại diện cho tất cả các kết hợp. Rõ ràng là "Hồ sơ đã hoàn thành" cũng không được nằm trong cùng một mảng với "Hồ sơ chưa hoàn thành", v.v.

Cảm ơn!

Answer 1

Dường như bạn muốn tính toán sản phẩm Descartes của các mảng. Phương pháp mà tính sản phẩm Descartes là (không quá ngạc nhiên) gọi Array#product:

@task_states.first.product(*@task_states.drop(1)) 

Vì vậy, ví dụ:

['A', 'no A'].product(['B', 'no B'], ['C', 'no C'], ['D', 'no D']) 
#=> [[ "A", "B", "C", "D"], 
# [ "A", "B", "C", "no D"], 
# [ "A", "B", "no C", "D"], 
# [ "A", "B", "no C", "no D"], 
# [ "A", "no B", "C", "D"], 
# [ "A", "no B", "C", "no D"], 
# [ "A", "no B", "no C", "D"], 
# [ "A", "no B", "no C", "no D"], 
# ["no A", "B", "C", "D"], 
# ["no A", "B", "C", "no D"], 
# ["no A", "B", "no C", "D"], 
# ["no A", "B", "no C", "no D"], 
# ["no A", "no B", "C", "D"], 
# ["no A", "no B", "C", "no D"], 
# ["no A", "no B", "no C", "D"], 
# ["no A", "no B", "no C", "no D"]] 

Answer 2

Bằng mọi cách, sử dụng Array#product, nhưng như trong thường được các trường hợp với Ruby , có nhiều cách khác. Đây là hai.

arr = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] 

Sử dụng toán học để tính toán mỗi arr.size**arr.first.size kết hợp

def cartesian_product(arr) 
    n, m = arr.size, arr.first.size 
    (0..n**m-1).map do |x| 
    (n-1).downto(0).map do |i| 
     x, r = x.divmod(m) 
     arr[i][r] 
    end.reverse 
    end 
end 

cartesian_product arr 
    #=> [[1, 4, 7], [1, 4, 8], [1, 4, 9], [1, 5, 7], [1, 5, 8], [1, 5, 9], 
    # [1, 6, 7], [1, 6, 8], [1, 6, 9], 
    # [2, 4, 7], [2, 4, 8], [2, 4, 9], [2, 5, 7], [2, 5, 8], [2, 5, 9], 
    # [2, 6, 7], [2, 6, 8], [2, 6, 9], 
    # [3, 4, 7], [3, 4, 8], [3, 4, 9], [3, 5, 7], [3, 5, 8], [3, 5, 9], 
    # [3, 6, 7], [3, 6, 8], [3, 6, 9]] 

Sử dụng đệ quy

def cartesian_product(arr) 
    first, *rest = arr 
    return first.map { |o| [o] } if rest.empty? 
    c = cartesian_product(rest) 
    first.flat_map { |o| c.map { |a| [o] + a } } 
end 

cartesian_product arr 
    #=> same as above 

Trong ứng dụng này mỗi phần tử (mảng) của arr không chứa các bản sao. Trong tình huống khác, nơi các bản sao có thể có mặt (và nơi các sản phẩm trả lại không phải để chứa bản sao), ta nên đầu tiên tính

arr_without_dups = arr.map(&:uniq) 

và sau đó tính toán các kết hợp từ arr_without_dups.

Answer 3

Trong khi các câu trả lời được cung cấp là tuyệt vời và Jörg là câu trả lời tôi chấp nhận, tôi muốn chia sẻ câu trả lời mà một trong những người bạn của tôi đã cung cấp cho tôi trong trường hợp bất kỳ ai khác gặp phải câu hỏi này. Về cơ bản nó là câu trả lời của Jörg nhưng với chiều sâu hơn một chút.

sản phẩm Descartes gì bạn đang yêu cầu được gọi là Cartesian Product và nó đã được xây dựng với Array#product.

Ví dụ:

[0, 1].product([0, 1]) 
# => [[0, 0], [0, 1], [1, 0], [1, 1]] 

Chú ý rằng điều này cho chúng ta tất cả các số 2-bit có thể, từ 00-11

Bạn có thể cung cấp cho mảng # sản phẩm bất kỳ số lượng các mảng:

[0, 1].product([0, 1], [0, 1]) 
# => [[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]] 

Lưu ý rằng điều này cho chúng ta tất cả các số có thể có 3 bit, từ 000-111.

Vấn đề của bạn Nhìn vào vấn đề chính xác của bạn:

["A", "no A"].product(["B", "no B"], ["C", "no C"], ["D", "no D"]) 
=> [["A", "B", "C", "D"], 
["A", "B", "C", "no D"], 
["A", "B", "no C", "D"], 
["A", "B", "no C", "no D"], 
["A", "no B", "C", "D"], 
["A", "no B", "C", "no D"], 
["A", "no B", "no C", "D"], 
["A", "no B", "no C", "no D"], 
["no A", "B", "C", "D"], 
["no A", "B", "C", "no D"], 
["no A", "B", "no C", "D"], 
["no A", "B", "no C", "no D"], 
["no A", "no B", "C", "D"], 
["no A", "no B", "C", "no D"], 
["no A", "no B", "no C", "D"], 
["no A", "no B", "no C", "no D"]] 
gives you all the possible combinations from "ABCD" to "noA noB noC noD" 

giải pháp Generic Chúng ta có thể làm cho công việc này với bất kỳ mảng chung của mảng bằng cách tận dụng các ký hiệu * điều hành.

def combinations(arrays) 
    first, *rest = arrays 
    first.product(*rest) 
end 

Sau đó chúng ta có thể nói:

arrays_to_combine = [["A", "no A"], ["B", "no B"], ["C", "no C"], ["D", "no D"]] 
combinations(arrays_to_combine) 
=> [["A", "B", "C", "D"], 
["A", "B", "C", "no D"], 
["A", "B", "no C", "D"], 
["A", "B", "no C", "no D"], 
["A", "no B", "C", "D"], 
["A", "no B", "C", "no D"], 
["A", "no B", "no C", "D"], 
["A", "no B", "no C", "no D"], 
["no A", "B", "C", "D"], 
["no A", "B", "C", "no D"], 
["no A", "B", "no C", "D"], 
["no A", "B", "no C", "no D"], 
["no A", "no B", "C", "D"], 
["no A", "no B", "C", "no D"], 
["no A", "no B", "no C", "D"], 
["no A", "no B", "no C", "no D"]] 

Đặc biệt cảm ơn Joel Quenneville của Thoughtbot vì đã giúp tôi với điều này cũng như phần còn lại của những người cung cấp câu trả lời.