Generating all possible combinations

Question

I'm writing some code and ended up with this problem. I have N products and I have to form all possible combinations of these products, form a product catalog and find some properties, like price. In order to do this I have to form the catalog of products from the given products (exhaustively, but no duplicates allowed). Is there a standardized algorithm for doing this? Note that the catalogs can contain any positive number of products.

Answer 1

Combinations can be represented by a bit-vector. If a bit is set, the element is present in the combination.

So you simply have to enumarte all numbers from 1 to 2^N-1 (from 0000001, last element present till 1111111, all elements present), and will represent a possible combination.

Answer 2

A naive implementation to print all combination of characters from a give string:

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);
  }
}

Quite simple but may have performance problem. Take it if it could help.

If you're looking for permutation(I can't tell from your description), I implemented the algorithm in The Art of Computer Programming:

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]));
}

It's quite efficient and C++ stl algorithm uses the same algorithm.

Answer 3

You can do this in python, using itertools.combinations in following way:

import itertools

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

what gives as result:

('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')

Solution inspired by this answer of @dan-h.

Answer 4

The first few sections of The Art of Computer Programming, vol. 3, Sorting and Searching discusses Inversion and Permutation (of a set and multisets) in great detail. In this case it is important to dabble in theory a bit, see what's out there. The code will follow, but if this is "leisure time coding", why not do it including "leisure time theory" as well? Betcha it's going to be cool, you'll know the whats but you'll also know the whys!