Tạo tất cả các tập con "độc đáo" của một tập (không phải là một Powerset)

Question

Hãy nói rằng chúng tôi có một Set S trong đó có một vài tập con:

- [a,b,c] 
- [a,b] 
- [c] 
- [d,e,f] 
- [d,f] 
- [e] 

Cũng giả sử rằng S chứa sáu yếu tố duy nhất: a, b, c, d, e và f .

Làm cách nào chúng tôi có thể tìm thấy tất cả các tập hợp con có thể có của S có chứa từng thành phần độc đáo của S chính xác một lần?

Kết quả của hàm/phương pháp nên được một cái gì đó như thế:

1. [[a,b,c], [d,e,f]];
2. [[a,b,c], [d,f], [e]];
3. [[a,b], [c], [d,e,f]];
4. [[a,b], [c], [d,f], [e]].

Có bất kỳ thực hành tốt nhất hoặc tiêu chuẩn nào cách để đạt được điều đó?

Tôi sẽ biết ơn về ví dụ về mã giả, Ruby hoặc Erlang.

Answer 1

Nghe có vẻ như những gì bạn đang tìm kiếm là partitions của một tập hợp/mảng.

Một cách để làm điều này là đệ quy:

• một mảng 1 phần tử [x] có chính xác một phân vùng
• nếu x là một mảng có dạng x = [đầu] + đuôi, sau đó các phân vùng của x được tạo ra bằng cách lấy từng phân vùng đuôi và thêm đầu vào mỗi phân đoạn có thể. Ví dụ, nếu chúng ta tạo ra các phân vùng của [3,2,1] thì từ phân vùng [[2,1]] của [2,1] chúng ta có thể thêm 3 đến [2,1] hoặc như một phần tử riêng biệt , cung cấp cho chúng tôi 2 phân vùng [[3,2,1] hoặc [[2,1], [3]] trong số 5 [1,2,3] có

Việc triển khai Ruby trông hơi như

def partitions(x) 
    if x.length == 1 
    [[x]] 
    else 
    head, tail = x[0], x[1, x.length-1] 
    partitions(tail).inject([]) do |result, tail_partition| 
     result + partitions_by_adding_element(tail_partition, head) 
    end 
    end 
end 

def partitions_by_adding_element(partition, element) 
    (0..partition.length).collect do |index_to_add_at| 
    new_partition = partition.dup 
    new_partition[index_to_add_at] = (new_partition[index_to_add_at] || []) + [element] 
    new_partition 
    end 
end 

Answer 2

Tại sao không sử dụng thuật toán tham lam?

1) loại thiết S giảm dần bằng cách sử dụng các tập con dài
2) cho i: = 0
3) thêm S [i] để giải pháp
4) tìm S [j] trong đó j> i như nó chứa các yếu tố mà không có trong giải pháp hiện tại
5) nếu bạn không thể tìm thấy yếu tố mô tả trong 4 sau đó
5.A) giải pháp rõ ràng
5.b) tăng i
5.C) nếu i> | S | sau đó phá vỡ, không có giải pháp tìm thấy; ( 5.d) goto 3

EDIT
Hmm, đọc lại bài viết của bạn và đi đến kết luận rằng bạn cần một Best-First search. Câu hỏi của bạn không phải là vấn đề phân vùng bởi vì những gì bạn cần cũng được gọi là Change-making problem nhưng trong trường hợp thứ hai, giải pháp đầu tiên được lấy là giải pháp tốt nhất - bạn thực sự muốn tìm tất cả các giải pháp và đó là lý do tại sao bạn nên là người giỏi nhất -phương pháp tiếp cận chiến lược tìm kiếm đầu tiên.

Answer 3

Có vẻ như bài tập "quay lại" cổ điển.

• # 1: Đặt hàng các bộ của bạn trở nên ôn hòa hơn, vì vậy nhạc nền sẽ không đưa ra giải pháp hai lần.
• # 2: current_set = [], set_list = []
• # 3: Loop Chạy qua tất cả các dấu có thứ tự thấp hơn so với giá trị cuối cùng trong set_list, (hoặc tất cả nếu set_list trống). Gọi nó là set_at_hand
• # 4: Nếu set_at_hand không có giao lộ với current_set
• # 4/true/1: Liên kết nó với current_set, cũng thêm vào set_list.
• # 4/true/2: current_set hoàn tất? true: thêm set_list vào danh sách các giải pháp đúng.sai: recurse đến # 3
• # 4/đúng/3: loại bỏ set_at_hand từ current_set và set_list
• # 5: Kết thúc vòng lặp
• # 6: trở

Answer 4

tạo ra tất cả các tập con

def allSubsets set 
    combs=2**set.length 
    subsets=[] 
    for i in (0..combs) do 
     subset=[] 
     0.upto(set.length-1){|j| subset<<set[j] if i&(1<<j)!=0} 
     subsets<<subset 
    end 
    subsets 
end 

Answer 5

hãy xem ở đây: https://github.com/sagivo/algorithms/blob/master/powerset.rb
đây là một thuật toán đơn giản mà tôi xây dựng để tìm ra một phần tử của một mảng.