Перестановки с ограничениями

Первая попытка, рассматривайте ее как простую задачу динамического программирования.

Таким образом, вы работаете слева направо, для каждой позиции в списке конвертов, для каждого возможного набора писем, которые вы можете оставить, определите количество способов, которыми вы могли бы добраться до этой точки. Двигаться вперед легко, вы просто берете набор, Вы знаете, сколько способов туда попасть, затем для каждой буквы, которую вы могли бы положить в следующий конверт, вы увеличиваете сумму полученного набора на число есть способы добраться до этой точки. Когда Вы дойдете до конца списка конвертов, вы найдете, сколько способов, чтобы осталось 0 букв, что и является вашим ответом.

В вашем втором примере это может развиваться следующим образом:

Step 0: next envelope 1
  {1: 2, 2: 2, 3: 1}: 1
    -> {1: 2, 2: 1, 3: 1}
    -> {1: 2, 2: 2}

Step 1: next envelope 1
  {1: 2, 2: 1, 3: 1}: 1
    -> {1: 2, 2: 1}
    -> {1: 2, 3: 1}
  {1: 2, 2: 2}: 1
    -> {1: 2, 2: 1}

Step 2: next envelope 2
  {1: 2, 2: 1}: 2
    -> {1: 1, 2: 1}
  {1: 2, 3: 1}: 1
    -> {1: 1, 3: 1}
    -> {1: 2}

Step 3: next envelope 2
  {1: 1, 2: 1}: 2
    -> {2: 1}
  {1: 1, 3: 1}: 1
    -> {1: 1}
    -> {3: 1}
  {1: 2}: 1
    -> {1: 1}

Step 4: next envelope 3
  {2: 1}: 2
    -> {}
  {1: 1}: 2
    -> {}
  {3: 1}: 1
    // Dead end.

Step 5:
  {}: 4

Это работает, и вы получите примерно тот вычислительный диапазон, который вы просили. В 15 у вас есть 2^15 = 32768 возможных подмножеств, отслеживать которые очень выполнимо. Где-то около 20 у вас начнет заканчиваться память хотя.

Можем ли мы улучшить это? Ответ в том, что мы можем. Подавляющее большинство нашей энергии тратится на то, чтобы вспомнить, например, использовали ли мы конверты с меткой 8 или конверты с меткой 9 до сих пор. Но нас это не волнует. То, что определяет, сколько способов есть, чтобы закончить, не является ли мы использовали Конверт 8 или 9. Но скорее по шаблону. Сколько существует этикеток, на которых осталось x конвертов и y букв. Не какие ярлыки какие, а просто сколько их.

Итак, если мы отслеживая только эту информацию, на каждом шаге мы можем захватить конверт с этикеткой, в которой осталось больше конвертов, и если есть галстук, мы выберем тот, в котором осталось меньше букв (и если есть еще галстук, нам действительно все равно, какой из них мы получим). И делать расчет, как и раньше, но с гораздо меньшим количеством промежуточных состояний. (Мы не заканчиваем с конвертами, выстроенными в ряд, как у вас. Но сделайте стабильную сортировку на последних письмах с конвертами, и вы получите обратно список, который вы выше.)

Будем использовать обозначение [x y]: z для обозначения того, что есть z этикетки с x конвертами и y буквами слева. И у нас есть список таких меток, тогда ваш пример 1 1 2 2 3 может быть представлен как {[2 2]: 2, [1 1]: 1}. И для перехода мы возьмем одну из меток [2 2] и либо используем букву из другой (давая нам переход к {[2 1]: 1, [1 2]: 1, [1 1]: 1}), либо возьмем одну из меток [2 2] и используем букву из метки [1 1] (давая нам переход к {[2 1]: 1, [1 2]: 1, [1 1]: 1}). {[2 2]: 1, [1 2]: 1, [1 0]: 1}).

Давайте проведем расчет. Я перечислю состояния, количество способов добраться туда и переходы, которые вы делаете:

Step 1:
  {[2 2]: 2, [1 1]: 1}: 1
    -> 1 * {[2 1]: 1, [1 2]: 1, [1 1]: 1}
    -> 1 * {[2 2]: 1, [1 2]: 1, [1 0]: 1}

Step 2:
  {[2 1]: 1, [1 2]: 1, [1 1]: 1}: 1
    -> 1 * {[1 1]: 3}
    -> 1 * {[1 1]: 1, [1 2]: 1, [1 0]: 1}
  {[2 2]: 1, [1 2]: 1, [1 0]: 1}: 1
    -> 1 * {[1 2]: 1, [1 1]: 1, [1 0]: 1}

Step 3:
  {[1 1]: 3}: 1
       // This is 2x because once the label is chosen, there are 2 letters to use.
    -> 2 * {[0 1]: 1, [1 0]: 1, [1 1]: 1}
  {[1 1]: 1, [1 2]: 1, [1 0]: 1}: 2
    -> 1 * {[1 0]: 1, [1 2]: 1, [0 0]: 1}
    -> 1 * {[1 1]: 2, [0 0]: 1}
  {[1 2]: 1, [1 1]: 1, [1 0]: 1}: 1
    -> 1 * {[1 1]: 2, [0 0]: 1}
    -> 1 * {[1 2]: 1, [1 0]: 1, [0 0]: 1}

Step 4:
  {[0 1]: 1, [1 0]: 1, [1 1]: 1}: 2
    -> 1 * {[1 1]: 1, [0 0]: 2}
    -> 1 * {[1 0]: 1, [0 1]: 1, [0 0]: 1}
  {[1 0]: 1, [1 2]: 1, [0 0]: 1}: 2
    -> 1 * {[1 1]: 1, [0 0]: 2}
  {[1 1]: 2, [0 0]: 1}: 2
    -> 1 * {[1 0]: 1, [0 1]: 1, [0 0]: 1}

Step 5:
  {[1 1]: 1, [0 0]: 2}: 4
    // dead end
  {[1 0]: 1, [0 1]: 1, [0 0]: 1}: 4
    -> 1 * {[0 0]: 3}

Итак, ответ-4.

Это может показаться сумасшедшим объемом работы-гораздо больше, чем перечисление. Так оно и было! Однако он масштабируется. Попробуйте его с 100 письмами и конвертами, и он должен работать быстро.