CODEWITHSUNDEEP
algorithmcombinatorics
Malice
Malice

Reputation: 1482

Generating all possible combinations

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.

Upvotes: 2

Views: 9558

Answers (4)

Grzegorz Wierzowiecki
Grzegorz Wierzowiecki

Reputation: 10843

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.

Upvotes: 2

Dervin Thunk
Dervin Thunk

Reputation: 20140

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!

Upvotes: 1

Mu Qiao
Mu Qiao

Reputation: 7107

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.

Upvotes: 2

Karoly Horvath
Karoly Horvath

Reputation: 96306

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.

Upvotes: 5

Related Questions