thuật toán kết hợp

Question

Tôi muốn tạo thuật toán sắp xếp đơn giản.

cho đầu vào "abcde", tôi muốn đầu ra bên dưới. bạn có thể cho tôi biết thuật toán cho điều đó không?

arr[0] = "a" 
arr[1] = "ab" 
arr[2] = "ac" 
arr[3] = "ad" 
arr[4] = "ae" 
arr[5] = "abc" 
arr[6] = "abd" 
arr[7] = "abe" 
... 
arr[n] = "abcde" 

arr[n+1] = "b" 
arr[n+2] = "bc" 
arr[n+3] = "bd" 
arr[n+4] = "be" 
arr[n+5] = "bcd" 
arr[n+5] = "bce" 
arr[n+5] = "bde" 
... 
arr[n+m] = "bcde" 
... 
... 

Answer 1

Thuật toán cho "Tạo bộ nguồn" từ một mảng là những gì bạn đang tìm kiếm. Bạn có thể dùng thử Google hoặc một số công cụ tìm kiếm khác để tìm thuật toán phù hợp nhất với nhu cầu của bạn.

Answer 2

Bạn đang mô tả một số power set. Dưới đây là một số mã C++:

#include <vector> 
#include <string> 
#include <algorithm> 
#include <functional> 
using namespace std; 

vector<string> string_powerset(string const &in) { 
    vector<string> result(1); // start output with one empty string 
    result.reserve(1 << in.size()); // output size = 2^(in.size()) 
    if (result.capacity() != 1<<in.size()) throw range_error("too big"); 

    for (string::const_iterator it = in.begin(); it != in.end(); ++ it) { 
     size_t middle = result.size(); // duplicate what we have so far 
     result.insert(result.end(), result.begin(), result.end()); 

      // append current character onto duplicated output 
     for_each(result.begin() + middle, result.end(), 
      bind2nd(mem_fun_ref(&string::push_back), * it)); 
    } 
    return result; 
} 

Thử nghiệm làm việc: v). Việc kiểm tra phạm vi không phải là tốt nhất, nhưng bất cứ điều gì.

Mã này sẽ có xu hướng tràn, do sự tăng trưởng theo cấp số mũ của bộ năng lượng, vì vậy bạn chỉ nên truyền chuỗi ngắn. Câu trả lời được đăng khác tránh được vấn đề này bằng cách tạo và trả về một chuỗi tại một thời điểm. Tuy nhiên, điều này dễ hiểu hơn và việc sử dụng một đoạn mã lớn hơn và khó hiểu hơn sẽ là tối ưu hóa sớm trừ khi bạn thực sự có sự cố tràn.

CHỈNH SỬA: I wrote up a next_subset answer và có vẻ không giống Ben.

Answer 3

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

template <typename Iterator> 
bool next_combination(const Iterator first, Iterator k, const Iterator last) 
{ 
    /* Credits: Mark Nelson http://marknelson.us */ 
    if ((first == last) || (first == k) || (last == k)) 
     return false; 
    Iterator i1 = first; 
    Iterator i2 = last; 
    ++i1; 
    if (last == i1) 
     return false; 
    i1 = last; 
    --i1; 
    i1 = k; 
    --i2; 
    while (first != i1) 
    { 
     if (*--i1 < *i2) 
     { 
     Iterator j = k; 
     while (!(*i1 < *j)) ++j; 
     std::iter_swap(i1,j); 
     ++i1; 
     ++j; 
     i2 = k; 
     std::rotate(i1,j,last); 
     while (last != j) 
     { 
      ++j; 
      ++i2; 
     } 
     std::rotate(k,i2,last); 
     return true; 
     } 
    } 
    std::rotate(first,k,last); 
    return false; 
} 

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

std::string s = "abcde"; 
for(std::size_t i = 1; i != s.size(); ++i) 
{ 
    do 
    { 
     std::cout << std::string(s.begin(),s.begin() + i) << std::endl; 
    } 
    while(next_combination(s.begin(),s.begin() + i,s.end())); 
} 

Lưu ý: Đó là bạn nên mong đợi để xem 2^n-1 kết hợp, nơi n là độ dài của mảng hoặc chuỗi.