Генерация всех возможных комбинаций

Question

Я пишу код и столкнулся с этой проблемой. У меня есть N продуктов, и я должен сформировать все возможные комбинации этих продуктов, сформировать каталог продуктов и найти некоторые свойства, такие как цена. Для этого мне нужно сформировать каталог товаров из указанных товаров (исчерпывающе, но дубликаты не допускаются). Есть ли стандартизированный алгоритм для этого? Обратите внимание, что каталоги могут содержать любое положительное количество товаров.

Answer 1

Комбинации могут быть представлены битовым вектором.Если бит установлен, элемент присутствует в комбинации.

Так что вам просто нужно перечислить все числа от 1 до 2 ^ N-1 (от 0000001, последний элемент присутствует до 1111111, все элементы присутствуют)и будет представлять возможную комбинацию.

Answer 2

Вы можете сделать это в Python, используя itertools.combination следующим образом:

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

Решение, вдохновленное этим ответом @ dan-h .

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

Первые несколько разделов «Искусство компьютерного программирования», вып.3, Сортировка и поиск обсуждают инверсию и перестановку (множества и мультимножеств) в деталях.В этом случае важно немного поиграть в теории, посмотреть, что там.Код будет следовать, но если это «кодирование свободного времени», почему бы не сделать это, включая «теорию свободного времени»?Дык, это будет круто, вы будете знать, что, но вы также будете знать, почему!