Làm cách nào để tìm tất cả các tập hợp con có thể có của một mảng nhất định?

Question

Tôi muốn trích xuất tất cả các tập con có thể của một mảng trong C# hoặc C++ và sau đó tính tổng của tất cả các phần tử tương ứng của các mảng con để kiểm tra xem có bao nhiêu phần tử bằng một số đã cho.

Điều tôi đang tìm kiếm là thuật toán. Tôi hiểu logic ở đây nhưng tôi đã không thể thực hiện điều này ngay bây giờ.

Answer 1

Xem xét một bộ S của N phần tử và một tập hợp con đã cho, mỗi phần tử có hoặc không thuộc về tập hợp con đó. Do đó, có thể là 2^N các tập con có thể (nếu bạn bao gồm bộ gốc và bộ trống), và có ánh xạ trực tiếp từ các bit trong biểu diễn nhị phân của x giữa 0 và 2^N với các phần tử trong bộ phụ x thứ S.

Khi bạn đã tìm hiểu cách liệt kê các phần tử của một tập con cụ thể, việc thêm các giá trị rất đơn giản.

Đối với việc tìm kiếm các tập con đó bằng tổng t cho lớn N, một tối ưu hóa có thể là để ghi lại những tập con mà vượt quá t, và không kiểm tra bất kỳ mà supersets thích hợp trong những người. Kiểm tra cho dù số thiết lập x là một superset của tập hợp y có thể đạt được với một hoạt động bitwise đơn và so sánh số nguyên.

Answer 2

Bạn;

A) Thực sự muốn tìm tất cả các tập con có thể có?

hoặc

B) Muốn tìm bao nhiêu yếu tố trong một mảng có thể được kết hợp để bằng một số lượng nhất định, và xem A) là một bước tiến trong việc giải pháp?

Nếu đó là A) thì điều đó khá đơn giản nhưng số lượng tập con có thể trở nên cực kỳ lớn rất nhanh.

Nếu đó là B) thì bạn nên sắp xếp mảng đầu tiên và làm việc từ đó.

Answer 3

Đây là một trong những dự án đại học của tôi 4/5 năm trước và tôi không thể nhắc thuật toán tốt. Như tôi thấy & bộ nhớ của tôi phục vụ nó sử dụng một mảng như tập hợp ban đầu và một bitmask để chỉ ra những yếu tố nào có mặt trong tập hợp con hiện tại.
đây là các mã un thử nghiệm từ kho lưu trữ:

#include <iostream> 

#ifndef H_SUBSET 
#define H_SUBSET 

template <class T> 
class Subset { 
    private: 
     int Dimension; 
     T *Set; 
     bool *Bitmask; 
    public: 
     Subset(T *set, int dim); 
     ~Subset(void); 
     void Show(void); 
     void NextSubset(void); 
     void EmptySet(void); 
     void FullSet(void); 
     int SubsetCardinality(void); 
     int SetCardinality(void); 
     T operator[](int index); 
};  

template <class T> 
int Subset<T>::SetCardinality(void) { 
    return Dimension; 
} 

template <class T> 
int Subset<T>::SubsetCardinality(void) { 
    int dim = 0; 
    for(int i = 0; i<Dimension; i++) { 
     if(Bitmask[i]) { 
      dim++; 
     } 
    } 
    return dim; 
} 

template <class T> 
void Subset<T>::EmptySet(void) { 
    for(int i = 0; i<Dimension; i++) { 
     Bitmask[i] = 0; 
    } 
    return; 
} 

template <class T> 
void Subset<T>::FullSet(void) { 
    for(int i = 0; i<Dimension; i++) { 
     Bitmask[i] = 1; 
    } 
    return; 
} 

template <class T> 
void Subset<T>::NextSubset(void) { 
    int i = Dimension - 1; 
    while(!Bitmask[i]&&i>=0) { 
     i--; 
     if(i<0) { 
      break; 
     } 
    } 
    if(i>=0) { 
     Bitmask[i] = !Bitmask[i]; 
    } 
    for(int j = i+1; j < Dimension; j++) { 
     Bitmask[j] = !Bitmask[j]; 
    } 
    return; 
} 

template <class T> 
void Subset<T>::Show(void) { 
    std::cout << "{ "; 
    for(int i=0; i<Dimension; i++) { 
     if(Bitmask[i]) { 
      std::cout << Set[i] << ", "; 
     } 
    } 
    std::cout << "}"; 
    return; 
} 

template <class T> 
Subset<T>::Subset(T *set, int dim) { 
    Set = new T[dim]; 
    Bitmask = new bool[dim]; 
    Dimension = dim; 
    for(int i=0; i<dim; i++) { 
     Set[i] = set[i]; 
     Bitmask[i] = true; 
    } 
} 

template <class T> 
Subset<T>::~Subset(void) { 
    delete [] Set; 
    delete [] Bitmask; 
} 
#endif // H_SUBSET 

Và nếu đó là bài tập ở nhà của bạn, bạn đang giết chết chính mình bro;)

Answer 4

gì bạn đang tìm kiếm được gọi là power set. Rosetta Code có nhiều triển khai khác nhau, nhưng đây là mã C++ của chúng (chúng sử dụng một vectơ thay vì một mảng, nhưng nó sẽ khá dễ dịch).

#include <iostream> 
#include <set> 
#include <vector> 
#include <iterator> 

typedef std::set<int> set_type; 
typedef std::set<set_type> powerset_type; 

powerset_type powerset(set_type const& set) 
{ 
    typedef set_type::const_iterator set_iter; 
    typedef std::vector<set_iter> vec; 
    typedef vec::iterator vec_iter; 

    struct local 
    { 
    static int dereference(set_iter v) { return *v; } 
    }; 

    powerset_type result; 

    vec elements; 
    do 
    { 
    set_type tmp; 
    std::transform(elements.begin(), elements.end(), 
        std::inserter(tmp, tmp.end()), 
        local::dereference); 
    result.insert(tmp); 
    if (!elements.empty() && ++elements.back() == set.end()) 
    { 
     elements.pop_back(); 
    } 
    else 
    { 
     set_iter iter; 
     if (elements.empty()) 
     { 
     iter = set.begin(); 
     } 
     else 
     { 
     iter = elements.back(); 
     ++iter; 
     } 
     for (; iter != set.end(); ++iter) 
     { 
     elements.push_back(iter); 
     } 
    } 
    } while (!elements.empty()); 

    return result; 
} 

int main() 
{ 
    int values[4] = { 2, 3, 5, 7 }; 
    set_type test_set(values, values+4); 

    powerset_type test_powerset = powerset(test_set); 

    for (powerset_type::iterator iter = test_powerset.begin(); 
     iter != test_powerset.end(); 
     ++iter) 
    { 
    std::cout << "{ "; 
    char const* prefix = ""; 
    for (set_type::iterator iter2 = iter->begin(); 
     iter2 != iter->end(); 
     ++iter2) 
    { 
     std::cout << prefix << *iter2; 
     prefix = ", "; 
    } 
    std::cout << " }\n"; 
    } 
} 

Output:

{ } 
{ 2 } 
{ 2, 3 } 
{ 2, 3, 5 } 
{ 2, 3, 5, 7 } 
{ 2, 3, 7 } 
{ 2, 5 } 
{ 2, 5, 7 } 
{ 2, 7 } 
{ 3 } 
{ 3, 5 } 
{ 3, 5, 7 } 
{ 3, 7 } 
{ 5 } 
{ 5, 7 } 
{ 7 }