Kết hợp vectơ điện toán hiệu quả

Question

Tôi đang nghiên cứu vấn đề nghiên cứu vì tò mò, và tôi không biết cách lập trình logic mà tôi đã ghi nhớ. Hãy để tôi giải thích cho bạn:

Tôi đã Bốn vectơ, nói ví dụ,

v1 = 1 1 1 1 
v2 = 2 2 2 2 
v3 = 3 3 3 3 
v4 = 4 4 4 4 

Bây giờ những gì tôi muốn làm là để thêm chúng kết hợp khôn ngoan, có nghĩa là,

v12 = v1+v2 
v13 = v1+v3 
v14 = v1+v4 
v23 = v2+v3 
v24 = v2+v4 
v34 = v3+v4 

Đến bước này, điều đó là tốt. Vấn đề là bây giờ tôi muốn thêm từng vectơ này một vectơ từ v1, v2, v3, v4 mà nó chưa thêm vào trước đó. Ví dụ:

v3 và v4 chưa được thêm vào v12, vì vậy tôi muốn tạo v123 và v124. Tương tự như vậy đối với tất cả các vectơ như,

v12 should become: 
v123 = v12+v3 
v124 = v12+v4 

v13 should become: 
v132 // This should not occur because I already have v123 
v134 

v14 should become: 
v142 // Cannot occur because I've v124 already 
v143 // Cannot occur 

v23 should become: 
v231 // Cannot occur 
v234 ... and so on. 

Điều quan trọng là tôi không phải làm tất cả chỉ một lúc khi bắt đầu. Ví dụ, tôi có thể làm (4 chọn 3) 4C3 và kết thúc nó, nhưng tôi muốn làm từng bước một ở mỗi lần lặp.

Làm cách nào để lập trình chương trình này?

P .: Tôi đang cố gắng làm việc trên phiên bản sửa đổi của thuật toán apriori trong khai phá dữ liệu.

Answer 1

Trong C++, được đưa ra sau thói quen:

template <typename Iterator> 
inline bool next_combination(const Iterator first, 
            Iterator k, 
          const Iterator last) 
{ 
    /* Credits: Thomas Draper */ 
    if ((first == last) || (first == k) || (last == k)) 
     return false; 
    Iterator itr1 = first; 
    Iterator itr2 = last; 
    ++itr1; 
    if (last == itr1) 
     return false; 
    itr1 = last; 
    --itr1; 
    itr1 = k; 
    --itr2; 
    while (first != itr1) 
    { 
     if (*--itr1 < *itr2) 
     { 
     Iterator j = k; 
     while (!(*itr1 < *j)) ++j; 
     std::iter_swap(itr1,j); 
     ++itr1; 
     ++j; 
     itr2 = k; 
     std::rotate(itr1,j,last); 
     while (last != j) 
     { 
      ++j; 
      ++itr2; 
     } 
     std::rotate(k,itr2,last); 
     return true; 
     } 
    } 
    std::rotate(first,k,last); 
    return false; 
} 

Sau đó bạn có thể tiến hành làm như sau:

int main() 
{ 
    unsigned int vec_idx[] = {0,1,2,3,4}; 

    const std::size_t vec_idx_size = sizeof(vec_idx)/sizeof(unsigned int); 

    { 
     // All unique combinations of two vectors, for example, 5C2 
     std::size_t k = 2; 
     do 
     { 
     std::cout << "Vector Indicies: "; 
     for (std::size_t i = 0; i < k; ++i) 
     { 
      std::cout << vec_idx[i] << " "; 
     } 
     } 
     while (next_combination(vec_idx, 
           vec_idx + k, 
           vec_idx + vec_idx_size)); 
    } 

    std::sort(vec_idx,vec_idx + vec_idx_size); 

    { 
     // All unique combinations of three vectors, for example, 5C3 
     std::size_t k = 3; 
     do 
     { 
     std::cout << "Vector Indicies: "; 
     for (std::size_t i = 0; i < k; ++i) 
     { 
      std::cout << vec_idx[i] << " "; 
     } 
     } 
     while (next_combination(vec_idx, 
           vec_idx + k, 
           vec_idx + vec_idx_size)); 
    } 

    return 0; 
} 

** Lưu ý 1: * Bởi vì giao diện hướng iterator cho next_combination thường lệ, bất kỳ vùng chứa STL nào hỗ trợ lặp lại chuyển tiếp thông qua trình lặp cũng có thể được sử dụng, chẳng hạn như std::vector, std::deque và std::list chỉ để đặt tên một vài.

Lưu ý 2: Vấn đề này rất phù hợp cho việc áp dụng các kỹ thuật ghi nhớ. Trong bài toán này, bạn có thể tạo một bản đồ và điền vào nó với tổng số tiền của các kết hợp đã cho. Trước khi tính toán tổng của một tập hợp các vectơ đã cho, bạn có thể tra cứu để xem liệu bất kỳ tập con nào của các khoản tiền đã được tính toán và sử dụng các kết quả đó chưa.Mặc dù bạn đang thực hiện tổng kết khá rẻ và nhanh, nếu tính toán bạn đang thực hiện phức tạp và tốn thời gian hơn nhiều, kỹ thuật này chắc chắn sẽ giúp mang lại một số cải tiến hiệu suất chính.

Answer 2

1. Duy trì danh sách tất cả để chọn hai giá trị.
2. Tạo vectơ các tập hợp sao cho tập hợp bao gồm các phần tử từ vectơ gốc với các phần tử 4C2. Lặp lại các vectơ gốc và cho mỗi vectơ, thêm/tạo một tập hợp với các phần tử từ bước 1. Duy trì một vectơ các bộ và chỉ khi bộ không có, thêm kết quả vào vectơ.
3. Sum lên vector bộ bạn thu được ở bước 2.

Nhưng khi bạn chỉ định, dễ nhất là 4C3.

Đây là nội dung được viết bằng Python. Bạn có thể áp dụng nó để C++

import itertools 

l1 = ['v1','v2','v3','v4'] 
res = [] 
for e in itertools.combinations(l1,2): 
    res.append(e) 

fin = [] 
for e in res: 
    for l in l1: 
     aset = set((e[0],e[1],l)) 
     if aset not in fin and len(aset) == 3: 
      fin.append(aset) 
print fin 

này sẽ cho kết quả:

[set(['v1', 'v2', 'v3']), set(['v1', 'v2', 'v4']), set(['v1', 'v3', 'v4']), set(['v2', 'v3', 'v4'])] 

Đây là kết quả tương tự như 4C3.

Answer 3

Có lẽ tôi hiểu lầm, nhưng điều này không tương đương với việc tạo tất cả các tập con (bộ nguồn) 1, 2, 3, 4 và sau đó cho mỗi phần tử của bộ nguồn, tổng hợp vectơ? Ví dụ:

//This is pseudo C++ since I'm too lazy to type everything 
//push back the vectors or pointers to vectors, etc. 
vector< vector<int> > v = v1..v4; 

//Populate a vector with 1 to 4 
vector<int> n = 1..4 

//Function that generates the power set {nil, 1, (1,2), (1,3), (1,4), (1,2,3), etc. 
vector< vector <int> > power_vec = generate_power_set(n); 

//One might want to make a string key by doing a Perl-style join of the subset together by a comma or something... 
map< vector <int>,vector<int> > results; 
//For each subset, we sum the original vectors together 
for subset_iter over power_vec{ 
    vector<int> result; 
    //Assumes all the vecors same length, can be modified carefully if not. 
    result.reserve(length(v1)); 
    for ii=0 to length(v1){ 
     for iter over subset from subset_iter{ 
      result[ii]+=v[iter][ii]; 
     } 
    } 
    results[*subset_iter] = result; 
} 

Nếu đó là ý tưởng bạn đã có trong tâm trí, bạn vẫn cần một chức năng thiết lập quyền lực, nhưng mã đó là dễ dàng để tìm thấy nếu bạn tìm kiếm thiết lập quyền lực. Ví dụ: Obtaining a powerset of a set in Java.

Answer 4

Tôi nghĩ rằng vấn đề này có thể được giải quyết bằng cách đánh dấu har kết hợp nào đã xảy ra.

Suy nghĩ đầu tiên của tôi là bạn có thể sử dụng mảng 3 chiều để đánh dấu sự kết hợp nào đã xảy ra. Nhưng đó không phải là rất tốt.

Làm thế nào về một mảng bit (chẳng hạn như số nguyên) để gắn cờ? Chẳng hạn như:

Num 1 = 2^0 for vector 1 
Num 2 = 2^1 for vector 2 
Num 4 = 2^2 for vector 3 
Num 8 = 2^3 for vector 4 

Khi bạn soạn thư, chỉ cần thêm tất cả số đại diện. Ví dụ, vector 124 sẽ có giá trị: 1 + 2 + 8 = 11. Giá trị này là duy nhất cho mọi kết hợp.

Đây chỉ là suy nghĩ của tôi. Hy vọng nó sẽ giúp bạn một cách nào đó.

EDIT: Có thể tôi không đủ rõ ràng về ý tưởng của mình. Tôi sẽ cố gắng giải thích rõ hơn một chút:

1) Chỉ định cho mỗi véc tơ một số đại diện. Số này là id của một vectơ và nó là duy nhất. Hơn nữa, tổng của mỗi tập con của số đó là duy nhất, có nghĩa là nếu chúng ta có tổng số k đại diện là M; chúng ta có thể dễ dàng biết rằng các vectơ nào tham gia vào tổng.

Chúng tôi thực hiện điều đó bằng cách chỉ định: 2^0 cho véc tơ 1; 2^1 cho véc tơ 2; 2^2 cho véc tơ 3, v.v ...

Với mỗi M = tổng (2^x + 2^y + 2^z + ...) = (2^x HOẶC 2^y HOẶC 2^z HOẶC ...). Chúng ta biết rằng vector (x + 1), (y + 1), (z +1) ... tham gia vào tổng. Điều này có thể dễ dàng được kiểm tra bằng cách thể hiện số ở chế độ nhị phân.

Ví dụ, chúng ta biết rằng:

2^0 = 1 (nhị phân) 2^1 = 10 (nhị phân) 2^2 = 100 (nhị phân) ...

Vì vậy, nếu chúng ta có tổng là 10010 (nhị phân), chúng ta biết rằng vectơ (số: 10) và vectơ (số: 10000) tham gia vào tổng.

Và tốt nhất, tổng ở đây có thể được tính toán bởi toán tử "HOẶC", cũng dễ hiểu nếu bạn biểu thị số nhị phân.

2) Bằng cách sử dụng các sự kiện trên, mỗi lần trước khi bạn đếm tổng số vectơ của mình, trước tiên bạn có thể thêm/HOẶC số đại diện của chúng. Và bạn có thể theo dõi chúng trong một cái gì đó giống như một mảng tra cứu. Nếu tổng số đã tồn tại trong mảng tra cứu, bạn có thể bỏ qua nó. Bằng cách đó bạn có thể giải quyết vấn đề.