Задача о пакете пакетов

Представьте, что Вы вернулись из магазина и, после размещения всех покупок, у Вас осталась куча полиэтиленовых пакетов, которые Вы затолкали друг в друга и получили пакет пакетов.

Вы понимаете, что существуют разные способы сделать это, например, 3 пакета можно разместить так:

((())) 

- русский стиль, все пакеты "матрёшкой" засунуты один в один.

(()()) 

- демократический стиль, пакеты равноправно разместились во внешнем пакете.

Для 4 пакетов имеем уже 4 способа:

(((())))
((())())
((()()))
(()()())

Вопрос: сколько есть способов получить пакет из n пакетов? Хотелось бы также напечатать все конфигурации, "скобочное" представление в этой задаче весьма удобно.

Математически каждая конфигурация из n пакетов - это дерево с n узлами, где пакет представляет собой узел дерева, а пакет с его содержимым образует поддерево. Самый внешний пакет - это корневой узел. К счастью, уже известна последовательность OEIS A000081, которая показывает количество наших деревьев с n узлами (n = 0, 1, ...). Видно, что значения элементов последовательности довольно быстро растут.

Ниже показана консольная программа на C++, которая выводит для заданного n все конфигурации пакетов и подсчитывает их количество. Если для больших значений n возникнет переполнение, возможно, нужно больше памяти для вектора offset в функции init. Программа не контролирует значение n и не работает при n, меньшем 1. Проверялась в актуальной сборке Visual Studio 2019.

#include <iostream>
#include <vector>
std::vector <long> treeList;
std::vector <int> offset;

void init (int n) {
 int n2 = n * 2 + 1;
 for (int i = 0; i < n2; i++) 
  offset.push_back( i == 1 ? 1 : 0);
}

void append (long t) {
 treeList.push_back(1 | (t << 1));
}

void show(long t, int l) {
 while (l-- > 0) {
  std::cout << (t % 2 == 1 ? '(' : ')');
  t >>= 1;
 }
}

void listTrees(int n) {
 int n1 = n + 1;
 for (int i = offset[n]; i < offset[n1]; i++) {
  show (treeList[i], 2 * n);
  std::cout << std::endl;
 }
}

void assemble (int n, long t, int sl, int pos, int rem) {
 if (rem == 0) {
  append(t);
  return;
 }
 auto pp = pos;
 auto ss = sl;
 if (sl > rem) {
  ss = rem;
  pp = offset[ss];
 }
 else if (pp >= offset[ss + 1]) {
  ss--;
  if (ss == 0) {
   return;
  }
  pp = offset[ss];
 }
 assemble (n, t << (2 * ss) | treeList[pp], ss, pp, rem - ss);
 assemble (n, t, ss, pp + 1, rem);
}

void makeTrees(int n) {
 if (offset[n + 1] != 0) return;
 if (n > 0) makeTrees(n - 1);
 assemble(n, 0, n - 1, offset[n - 1], n - 1);
 offset[n + 1] = treeList.size();
}

void test(int n) {
 append(0);
 makeTrees(n);
 listTrees(n);
 std::cout << "Number of " << n << "-trees = " << offset[n + 1] - offset[n] << std::endl;
}

int main() {
 const int n = 13;
 init(n);
 test(n);
 return 0;
}

07.11.2021, 14:29 [669 просмотров]