生成所有可能的组合

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启发。