生成所有可能的組合

Question

我正在編寫一些代碼，並以此問題結束。我有N種產品，我必須形成這些產品的所有可能組合，形成產品目錄並查找價格等一些屬性。爲了做到這一點，我必須從給定的產品形成產品目錄（詳盡，但不允許重複）。有沒有一個標準化的算法來做到這一點？請注意，目錄可以包含任何正數量的產品。

Answer 1

計算機編程藝術的第一部分，第一卷。 3，Sorting and Searching詳細討論了反轉和置換（集合和多集合）。在這種情況下，重要的是在理論上進行一點探索，看看有什麼。代碼將隨之而來，但如果這是「閒暇時間編碼」，爲什麼不包括「閒暇時間理論」呢？ Betcha它會很酷，你會知道最新的情況，但你也會知道原因！

Answer 2

組合可以用位向量表示。如果設置了一個位，則該元素存在於組合中。

所以你只需要從1到2^N-1（0000001，最後一個存在的元素直到1111111，存在的所有元素）都能啓動所有數字，並且表示可能的組合。

Answer 3

一個天真的實現打印字符的組合，都從一個給字符串：

void print_combination(char* str, char* buffer, int len, int num, int pos)                 
{ 
    if(num == 0) 
    { 
    std::cout << buffer << std::endl; 
    return; 
    } 

    for(int i = pos; i < len - num + 1; ++i) 
    { 
    buffer[num - 1] = str[i]; 
    print_combination(str, buffer, len, num - 1, i + 1); 
    } 
} 

int main() 
{ 
    char str[] = "abcde"; 
    char buffer[6]; 
    for(auto i = 1u; i <= sizeof(str); ++i) 
    { 
    buffer[i] = '\0'; 
    print_combination(str, buffer, 5, i, 0); 
    } 
} 

很簡單，但可能有性能問題。如果它可以幫助，就拿它。

如果你正在尋找置換（我無法從你的描述告訴），我實現的算法在計算機程序設計藝術：

template <typename Iter>                             
bool next_permutation(Iter start, Iter end) 
{ 
    if(start == end) 
    return false; 

    Iter i = start + 1; 
    if(i == end) 
    return false; 

    i = end - 1; 

    while(true) 
    { 
    Iter ii = i; 
    --i; 
    if(*i < *ii) 
    { 
     Iter j = end; 
     while(*i >= *--j); 
     std::iter_swap(i, j); 
     std::reverse(ii, end); 
     return true; 
    } 
    if(i == start) 
    { 
     std::reverse(start, end); 
     return false; 
    } 
    } 
} 

int main() 
{ 
    char str1[] = "abcde"; 
    do 
    { 
    std::cout << str1 << std::endl; 
    } while(next_permutation(&str1[0], &str1[5])); 
} 

這是非常有效和C++ STL算法使用相同的算法。

Answer 4

你可以在Python做到這一點，在下列方式使用itertools.combinations：

import itertools 

products = ['p1', 'p2', 'p3', 'p4'] 
for L in range(1, len(products)+1): 
     for subset in itertools.combinations(products, L): 
       print(subset) 

什麼讓作爲結果：

('p1',) 
('p2',) 
('p3',) 
('p4',) 
('p1', 'p2') 
('p1', 'p3') 
('p1', 'p4') 
('p2', 'p3') 
('p2', 'p4') 
('p3', 'p4') 
('p1', 'p2', 'p3') 
('p1', 'p2', 'p4') 
('p1', 'p3', 'p4') 
('p2', 'p3', 'p4') 
('p1', 'p2', 'p3', 'p4') 

解決方案通過this answer of @dan-h啓發。