Найти все комбинации 3x3 отверстий

Я был на карнавале, где в каждом месте они отмечали вашу программу специальным ударным ударом. Пуансон - сетка пространств 3x3. В каждом пространстве есть либо штырь, который проколовает вашу бумагу, либо нет. Это заставило меня задаться вопросом, сколько разных шаблонов вы могли бы сделать с помощью этого инструмента. Моя первая мысль была: 2 ^ 9 = 512, но все 9 пробелов, являющихся бескамерными, на самом деле не являются ударами, так что действительно: 511.

Тогда сложность ударила меня. Тем более, что рабочие не так осторожны, когда они ударяют вашу бумагу, все они выглядят идентично:

x..  .x.  ...  etc.
.x.  x..  .x.
...  ...  ..x

Вопрос: Как можно записать тест для учета вращения и смещения?

Доверенность и мысли до сих пор:

  • Двоичный элемент чувствует себя как очевидная часть этого уравнения.
  • Когда найден уникальный шаблон, сохраните его в памяти, чтобы будущие шаблоны могли быть протестированы против него.
  • Есть 4 возможности поворота.
    Изменить: То, что я подразумеваю под" вращениями", это то, что вы можете принять любую форму и повернуть ее на 90 градусов. Рассмотрим шаблон, который является точкой в ​​верхнем левом углу. Вы можете поворачивать/поворачивать его на 90 градусов и получить точку в верхнем правом углу. Сделайте это снова, и это в правом нижнем углу. Снова и это в левом нижнем углу. Используя чистый расчет 2 ^ 9, это 4 разные комбинации. Однако для этой проблемы это именно те дубликаты, которые я пытаюсь вытеснить.
  • Для каждого вращения существует 25 способов перекрытия сетки 3х3:

Перекрытия:

/ = the spaces in the new one to test
\ = the spaces in a verified unique one

1               2               25
/ / / . . . .   . / / / . . .   . . . . . . .
/ / / . . . .   . / / / . . .   . . . . . . .
/ / X \ \ . .   . / X X \ . .   . . \ \ \ . .
. . \ \ \ . .   . . \ \ \ . .   . . \ \ \ . .
. . \ \ \ . .   . . \ \ \ . .   . . \ \ X / /
. . . . . . .   . . . . . . .   . . . . / / /
. . . . . . .   . . . . . . .   . . . . / / /
  • Наложение не нужно проверять, если какой-либо шаблон содержит контакт, который не находится в области перекрытия. Побитовое И может помочь здесь.
  • Если вы сделаете каждую позицию для каждого из двух шаблонов в строках, вы можете просто проверить равенство
  • Можно ли объединить эти две идеи для повышения эффективности?

Ответы

Ответ 1

Нам нужно рассматривать только шаблоны, которые имеют удары в первой строке и столбце. Если первая строка пуста, шаблон можно сдвинуть вверх. Если первый столбец пуст, шаблон можно сдвинуть влево. В любом случае мы можем получить аналогичную модель, которую мы рассматриваем.

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

Затем мы можем добавить это значение в хэш-набор, который будет сохранять только уникальные значения.

Пустой шаблон не включен, потому что все его строки пустые.

Чтобы реализовать это, мы кодируем шаблоны как последовательные биты:

012
345
678

Операции, которые нам понадобятся, в основном очень просты:

Test for an empty row:    (n & 7) == 0     // bits 0,1,2 not set
Test for an empty column: (n & 73) == 0    // bits 0,3,6 not set
Shift pattern up:         n -> (n >> 3)
Shift pattern left:       n -> (n >> 1)

Самая сложная часть - это поворот, который на самом деле просто переупорядочивает все бит:

n -> ((n & 1) << 2) + ((n & 2) << 4) + ((n & 4) << 6)
   + ((n & 8) >> 2) + (n & 16) + ((n & 32) << 2)
   + ((n & 64) >> 6) + ((n & 128) >> 4) + ((n & 256) >> 2);

В С#:

public static int Count3x3() {
    HashSet<int> patterns = new HashSet<int>();
    for (int i = 0; i < 512; i++) {
        if ((i & 7) == 0 || (i & 73) == 0)
            continue;
        int nLowest = i;
        int n = i;
        do {
            nLowest = Math.Min(nLowest, n);
            n = ((n & 1) << 2) + ((n & 2) << 4) + ((n & 4) << 6)
                + ((n & 8) >> 2) + (n & 16) + ((n & 32) << 2)
                + ((n & 64) >> 6) + ((n & 128) >> 4) + ((n & 256) >> 2);
            while ((n & 73) == 0)
                n >>= 1;
        } while (n != i);
        patterns.Add(nLowest);
    }
    return patterns.Count;
}

Эта функция возвращает 116. Время, затраченное на мою машину, составляло 0,023 мс.

EDIT. Вы можете получить дополнительное 7-кратное улучшение, используя 4 наблюдения:

  • Мы можем использовать простой посещенный массив вместо хеш-набора. Если ранее был замечен шаблон, мы не учитываем его. Это также устраняет необходимость отслеживать "самый низкий" шаблон во внутреннем цикле. Если шаблон был посещен, то также был посещен его самый низкий вращающийся шаблон.
  • Если у нас нет симметрии вращения на 180 градусов, то 3-й поворот не даст оригинального рисунка. 4-й поворот будет всегда, поэтому он не нужен.
  • Выражение вращения может быть слегка упрощено.

Итак, если мы применяем эти наблюдения и разворачиваем внутренний цикл do, мы получаем следующее:

static int Rotate(int n) {
    n = ((n & (1+32)) << 2) + ((n & 2) << 4) + ((n & 4) << 6)
        + ((n & (8+256)) >> 2) + (n & 16)
        + ((n & 64) >> 6) + ((n & 128) >> 4);
    while ((n & 73) == 0) 
        n >>= 1;
    return n;
}
public static int Count3x3_3() {
    bool[] visited = new bool[512];
    int count = 0, r;
    for (int i = 0; i < 512; i++) {
        if (visited[i])
            continue;
        if ((i & 7) == 0 || (i & 73) == 0)
            continue;
        count++;
        if ((r = Rotate(i)) == i) continue;
        visited[r] = true;
        if ((r = Rotate(r)) == i) continue;
        visited[r] = true;
        visited[Rotate(r)] = true;
    }
    return count;
}

Это работает примерно на 3 мкс на той же машине.

Ответ 2

Мое решение: 116 уникальных форм

При тестировании двух форм для равенства сравнение количества контактов экономит много времени. Но мой самый большой прорыв заключался в том, что все эти 25 позиций могут быть заменены следующим: для каждой из двух форм 3x3, которые нужно проверить на равенство, объедините строки двумя нулями, затем обрезайте ведущие и конечные нули. Конкретные нули должны предотвращать обертывание. Пример:

010 => 01000 => 0100010100000 => 1000101
101    10100
000    000

000 => 00000 => 0000001000101 => 1000101
010    01000
101    101

Затем просто проверьте результаты для равенства. Это 4 простых итерации (1 для каждого вращения) вместо 100 (25 позиций * 4 оборота) более сложных.

Время:
только строки:

  • грубая сила, все 25 позиций для каждого вращения: 2018мс
  • ... 00... 00... обрезано: 75 мс
  • дополнительная оптимизация: 59 мс

ООП и лучшее кэширование: 17 мс

Ответ 3

Во-первых, мы можем рассматривать два пуансона, которые эквивалентны, за исключением перевода, как вращения друг друга. Представьте, что шаблон пуансона находится на поверхности сферы: мы можем "перевести" его, вращая сферу вдоль горизонтальной и вертикальной осей (как это удерживается в нашей руке).

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

Теперь мы уменьшили проблему до "Сколько уникальных шаблонов пуансона существует на поверхности сферы, вплоть до вращения?" Для подсчета уникальных объектов до такой симметрии вам нужна не-Бернсайдская лемма. Эта книга является хорошим учебником.

Ответ 4

Я не думаю, что это похоже на сферный случай, так как вы не можете вращаться по краям? IE:

XOO
XXO
XOO

не совпадает с

OOX
XOX
OOX

Я пробовал подсчитывать вручную на бумаге, чтобы увидеть, что у меня есть. Рассмотрим случай 2x2 - у вас есть 1 с 0 точками, 1 с 1 точкой, 2 с 2 точками (смежные или диагональные), 1 с 3 точками и 1 с 4; в общей сложности 5 (или 4, если вы игнорируете пустой случай). Обратите внимание, что перечисление является симметричным, так как одинаково считать пустые пространства полными. Для случая 3x3 я получил следующее:

C(0) = 1
C(1) = 1
C(2) = 5
C(3) = 10
C(4) = 21

а затем по симметрии 21, 10, 5, 1, 1

Я получаю 76. Я мог бы легко ошибиться, особенно в случае 4/5.

Единственный способ, с помощью которого я могу автоматически перечислить их, - это перемещение и поворот шаблонов, чтобы увидеть, соответствуют ли они ранее перечисленным. Сдвиг является сложным, так как вы можете сдвинуться только до тех пор, пока не наброситесь на край.

Ответ 5

Стоит отметить, что если вам действительно нужна каждая форма, чтобы "выглядеть" уникальной, независимо от того, как она вращается или перемещается, у вас их очень мало. Например, один удар, независимо от того, где он находится в сетке, всегда будет выглядеть одинаково. Кроме того, предполагая квадратную сетку и круглые штыри и предполагая, что незначительные разности интервалов (& radic; 2) несущественны, то 2 отверстия по диагонали в строке будут выглядеть так же, как два соседних штыря, так как все зрители видят, что два отверстия близко друг к другу, Аналогично, 3 по диагонали будет выглядеть как 3 в прямой линии, что резко ограничивает ваши варианты.

Обратите внимание, что форма, вероятно, лучшее слово для того, что мы после комбинации , так как нам все равно, какова фактическая комбинация, форма находится на бумаге.

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

  • Если какой-либо угол пробивается, поверните сетку, пока перфорированный угол не окажется в верхнем левом углу.
  • В противном случае сдвиньте паттерн так далеко и влево, как он будет идти.
  • Повторите шаг 1
  • Если мы доберемся до этого, то мы знаем, что только верхняя средняя позиция пробита (поскольку мы знаем, что ни один из углов не является), и в этом случае мы поворачиваем рисунок на 45 градусов, делая верхнюю середину в верхнем левом углу, Что и требовалось доказать.

Я сделал очень быстрый поиск и поиск грубой силы для возможных фигур, и кажется, что список жизнеспособных вариантов настолько мал, что вы можете перечислить их всего за несколько минут.

Ответ 6

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

Выберите представление битовой строки сетки 3x3. Я выберу строку за строкой, сверху вниз. Установив бит, где его соответствующее отверстие пробито, мы теперь можем сопоставить 9-битные целые числа с пуансонами (и наоборот).

Для любого конкретного представления мы можем изобрести операции с битовыми играми, представляющие вращения и переводы. Некоторые переводы являются незаконными для выполнения некоторых шаблонов, поскольку мы хотим избежать "обертывания".

Подобно тому, как повороты и переводы являются обратимыми, так будут и наши операции. Если два движения отображают шаблон А в В, а затем от Б до С, мы можем, конечно, составить движения, чтобы сделать преобразование, взяв от А до С. Ничего не делая (преобразование идентичности) также законно, поэтому мы можем достичь А от А. Досягаемость поэтому преобразование является отношением эквивалентности на шаблонах пуансона, и поэтому эквивалентные шаблоны разбивают пространство.

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

Учитывая шаблон, как мы находим его наименьшего представителя? При проверке жадные алгоритмы не гарантируют работу. Мы можем достичь одного из множества эвристических алгоритмов оптимизации, или мы можем заметить, что мы всего лишь нажимаем 9 бит и исчерпывающе просматриваем пространство. Следует отметить, что, тем не менее, это позволяет легко вычислить один раз и запихнуть в таблицу поиска навсегда после.

Здесь исчерпывающий поиск. Обратите внимание, что при правильном кэшировании все еще довольно быстро (менее секунды).

#!/usr/bin/env ruby

require 'set'

class PunchPattern < String
  @@representatives = Hash.new do |h, k|
    equivalence_class = k.closure
    representative = equivalence_class.min

    k.closure.each do |node|
      h[node] = representative
    end

    representative
  end

  def initialize(s)
    raise "9 digits of 0 and 1, pls" unless s =~ /[01]{9}/
    super
  end

  def left
    return nil unless self =~ /0..0..0../
    PunchPattern.new([self[1...3], 0, self[4...6], 0, self[7...9], 0].join)
  end

  def right
    return nil unless self =~ /..0..0..0/
    PunchPattern.new([0, self[0...2], 0, self[3...5], 0, self[6...8]].join)
  end

  def up
    return nil unless self =~ /000....../
    PunchPattern.new([self[3...9], 0, 0, 0].join)
  end

  def down
    return nil unless self =~ /......000/
    PunchPattern.new([0, 0, 0, self[0...6]].join)
  end

  def turn
    PunchPattern.new([2, 5, 8, 1, 4, 7, 0, 3, 6].collect { |i| self[i].chr }.join)
  end

  def closure
    seen = Set.new([])
    frontier = Set.new([self])

    until frontier.empty?
      node = frontier.first
      frontier.delete(node)
      seen.add(node)

      %w{left right up down turn}.collect do |motion|
        node.send motion
      end.compact.each do |neighbor|
        frontier.add(neighbor) unless seen.include? neighbor
      end
    end

    seen
  end

  def representative
    self.class.representatives[self]
  end

  def self.representatives
    @@representatives
  end

end

(0...512).collect do |p|
  p = PunchPattern.new(p.to_s(2).rjust(9, '0'))
  [p.representative, p]
end.inject(Hash.new { |h, k| h[k] = [] }) do |h, pair|
  h[pair.first] << pair.last
  h
end.sort_by { |pair| pair.first }.each do |representative, patterns|
  puts patterns.collect { |p| p[0...3] + " " }.join
  puts patterns.collect { |p| p[3...6] + " " }.join
  puts patterns.collect { |p| p[6...9] + " " }.join
  puts
end

puts "#{PunchPattern.representatives.values.uniq.size} total congruence classes"

Выдает

$ ./congruence.rb 
000 
000 
000 

000 000 000 000 000 000 001 010 100 
000 000 000 001 010 100 000 000 000 
001 010 100 000 000 000 000 000 000 

000 000 000 000 000 000 000 001 010 011 100 110 
000 000 001 010 011 100 110 001 010 000 100 000 
011 110 001 010 000 100 000 000 000 000 000 000 

000 000 001 010 100 101 
000 101 000 000 000 000 
101 000 001 010 100 000 

000 000 001 010 100 111 
000 111 001 010 100 000 
111 000 001 010 100 000 

000 000 000 000 001 010 010 100 
001 010 010 100 010 001 100 010 
010 001 100 010 000 000 000 000 

000 000 000 000 000 000 000 000 001 010 010 011 011 100 110 110 
001 010 010 011 011 100 110 110 011 011 110 001 010 110 010 100 
011 011 110 001 010 110 010 100 000 000 000 000 000 000 000 000 

000 001 010 100 
001 100 000 000 
100 000 001 010 

000 000 001 010 011 100 101 110 
001 101 101 000 000 000 100 000 
101 100 000 011 001 110 000 010 

000 000 001 010 010 011 100 100 
001 011 110 001 010 100 010 100 
110 100 000 001 001 000 010 010 

000 000 001 010 011 100 110 111 
001 111 111 010 001 100 010 100 
111 100 000 011 001 110 010 000 

000 000 001 010 010 010 100 101 
010 101 010 001 100 101 010 010 
101 010 001 010 010 000 100 000 

000 000 001 010 010 010 100 111 
010 111 011 011 110 111 110 010 
111 010 001 010 010 000 100 000 

000 000 011 110 
011 110 011 110 
011 110 000 000 

000 000 010 011 011 100 101 110 
011 101 001 010 101 010 110 100 
101 110 011 001 000 110 000 010 

000 010 011 100 
011 011 110 110 
110 001 000 010 

000 000 010 011 011 100 110 111 
011 111 011 011 111 110 110 110 
111 110 011 001 000 110 010 000 

000 001 010 100 
100 000 000 001 
001 010 100 000 

000 000 001 001 010 010 100 110 
100 110 001 010 010 100 011 001 
011 001 010 010 100 100 000 000 

000 000 001 010 011 100 101 110 
100 101 000 000 000 101 001 000 
101 001 011 110 010 000 000 100 

000 000 001 010 011 100 110 111 
100 111 001 010 010 111 100 001 
111 001 011 110 010 000 100 000 

000 000 001 010 011 101 110 110 
101 110 010 100 001 011 010 101 
011 101 011 110 010 000 100 000 

000 011 101 110 
101 000 101 000 
101 011 000 110 

000 000 011 011 101 110 110 111 
101 111 001 010 111 010 100 101 
111 101 011 011 000 110 110 000 

000 001 010 110 
110 011 110 011 
011 010 100 000 

000 000 001 010 011 110 110 111 
110 111 011 110 011 110 111 011 
111 011 011 110 010 100 000 000 

000 011 110 111 
111 011 110 111 
111 011 110 000 

001 100 
000 000 
100 001 

001 100 101 101 
000 000 000 000 
101 101 001 100 

001 011 100 100 
000 000 001 100 
110 100 001 001 

001 100 101 111 
000 100 001 000 
111 101 001 100 

001 001 100 110 
001 100 000 000 
100 100 011 001 

001 100 101 111 
001 000 100 000 
101 111 100 001 

001 011 100 110 
001 100 100 001 
110 100 011 001 

001 100 111 111 
001 100 001 100 
111 111 001 100 

001 100 
010 010 
100 001 

001 100 101 101 
010 010 010 010 
101 101 001 100 

001 011 100 100 
010 010 011 110 
110 100 001 001 

001 100 101 111 
010 110 011 010 
111 101 001 100 

001 001 100 110 
011 110 010 010 
100 100 011 001 

001 100 101 111 
011 010 110 010 
101 111 100 001 

001 011 100 110 
011 110 110 011 
110 100 011 001 

001 100 111 111 
011 110 011 110 
111 111 001 100 

001 010 100 101 
100 000 001 000 
001 101 100 010 

001 010 010 100 
100 001 100 001 
010 100 001 010 

001 010 101 110 
100 100 001 001 
011 101 010 100 

001 101 101 110 
100 000 001 000 
101 011 100 101 

001 011 100 110 
100 001 001 100 
110 100 011 001 

001 101 110 111 
100 001 100 001 
111 011 101 100 

001 010 100 111 
101 000 101 000 
001 111 100 010 

001 010 010 110 
101 100 101 001 
010 011 100 010 

001 010 110 111 
101 100 101 001 
011 111 100 010 

001 110 
101 000 
100 011 

001 101 110 111 
101 101 000 000 
101 100 111 011 

001 011 110 110 
101 101 001 100 
110 100 011 011 

001 110 111 111 
101 100 001 101 
111 111 011 100 

001 010 100 101 
110 010 011 010 
001 101 100 010 

001 010 010 100 
110 011 110 011 
010 100 001 010 

001 010 101 110 
110 110 011 011 
011 101 010 100 

001 101 101 110 
110 010 011 010 
101 011 100 101 

001 011 100 110 
110 011 011 110 
110 100 011 001 

001 101 110 111 
110 011 110 011 
111 011 101 100 

001 010 100 111 
111 010 111 010 
001 111 100 010 

001 010 010 110 
111 110 111 011 
010 011 100 010 

001 010 110 111 
111 110 111 011 
011 111 100 010 

001 110 
111 010 
100 011 

001 101 110 111 
111 111 010 010 
101 100 111 011 

001 011 110 110 
111 111 011 110 
110 100 011 011 

001 110 111 111 
111 110 011 111 
111 111 011 100 

010 011 100 101 
001 100 001 100 
101 001 110 010 

010 010 011 100 
001 101 100 101 
110 001 010 010 

010 011 100 111 
001 101 101 100 
111 001 110 010 

010 011 100 101 
011 110 011 110 
101 001 110 010 

010 010 011 100 
011 111 110 111 
110 001 010 010 

010 011 100 111 
011 111 111 110 
111 001 110 010 

010 
101 
010 

010 010 011 110 
101 101 101 101 
011 110 010 010 

010 011 101 110 
101 100 101 001 
101 011 010 110 

010 011 110 111 
101 101 101 101 
111 011 110 010 

010 
111 
010 

010 010 011 110 
111 111 111 111 
011 110 010 010 

010 011 101 110 
111 110 111 011 
101 011 010 110 

010 011 110 111 
111 111 111 111 
111 011 110 010 

011 100 101 101 
000 001 000 100 
101 101 110 001 

011 100 
000 101 
110 001 

011 100 101 111 
000 101 101 000 
111 101 001 110 

011 100 101 111 
001 001 100 100 
101 111 110 001 

011 011 100 110 
001 100 101 101 
110 110 011 001 

011 100 111 111 
001 101 100 101 
111 111 110 001 

011 100 101 101 
010 011 010 110 
101 101 110 001 

011 100 
010 111 
110 001 

011 100 101 111 
010 111 111 010 
111 101 001 110 

011 100 101 111 
011 011 110 110 
101 111 110 001 

011 011 100 110 
011 110 111 111 
110 110 011 001 

011 100 111 111 
011 111 110 111 
111 111 110 001 

011 101 101 110 
100 001 100 001 
101 110 011 101 

011 101 110 111 
100 101 101 001 
111 011 101 110 

011 101 110 111 
101 101 001 100 
101 110 111 011 

011 110 
101 101 
110 011 

011 110 111 111 
101 101 101 101 
111 111 011 110 

011 101 101 110 
110 011 110 011 
101 110 011 101 

011 101 110 111 
110 111 111 011 
111 011 101 110 

011 101 110 111 
111 111 011 110 
101 110 111 011 

011 110 
111 111 
110 011 

011 110 111 111 
111 111 111 111 
111 111 011 110 

101 
000 
101 

101 101 101 111 
000 001 100 000 
111 101 101 101 

101 101 111 111 
001 100 001 100 
111 111 101 101 

101 
010 
101 

101 101 101 111 
010 011 110 010 
111 101 101 101 

101 101 111 111 
011 110 011 110 
111 111 101 101 

101 111 
101 000 
101 111 

101 111 111 111 
101 001 100 101 
111 111 111 101 

101 111 
111 010 
101 111 

101 111 111 111 
111 011 110 111 
111 111 111 101 

111 
101 
111 

111 
111 
111 

117 total congruence classes

.. для 117 классов.

Ответ 7

Я четко не понимаю эту часть о поворотах, но для этого сценария:

Есть 3x3 = 9 отверстий и 10 случаев, и каждый раз может иметь место только один случай:

Case 1 = no holes
Case 2 = one hole
...
Case 10 = 9 holes

Тогда это будет похоже на комбинационную формулу C (n, k):

Всего = C (9,0) + C (9,1) +.... + C (9,9)

это сумма k различных комбинаций n элементов.

Totol = 1 + 9 + 36 + 84 + 126 + 126 + 84 + 36 + 9 + 1 = 512

Я думаю, что вы правы, 512 кажется правильным и теоретически бесключевым также определяется как комбинация, если вы не хотите, чтобы он просто удалял его, чтобы получить 511.

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

Если бы они происходили синхронно, например, вычисляя комбинации для 3 сотрудников, пробивая бумагу один раз или вычисляя комбинации для маркировки бумаги 3 раза одним сотрудником, тогда она становится более сложной и должна быть 512 * 512 * 512 правило nxm.

Правило m * n на простом дисплее:

У меня 4 = m карманов и два = n рук:

my_left * 4 (карманы) = 4 my_right * 4 (карманы) = 4

total = 4 + 4 = 4 * 2 = m * n

Только одна рука может войти в карман за раз, или только одна комбинация одного занятого сопряжена только с одной комбинацией другого сотрудника, и это точная причина, по которой мы принимаем правило m * n.

Вот что я думаю, я не математик и не претендую на правильность 100%, это то, что я помню из курса вероятностей.

Я не утверждаю, что на 100% правильно, это то, что я помню для вероятностного курса.

Что касается перекрытия шаблонов, проверка наличия шаблона и т.д., я бы вообще не стал беспокоиться, так как в псевдокоде существует так много алгоритмов, которые генерируют комбинации. Поскольку они генерируют, тогда нет необходимости проверять перекрытия или что-то еще.

В конце концов, это означает, что generat означает, что он создан априори, чтобы найти все результаты, просто дайте ему запустить.

Я нашел один раз более редкий алгоритм, чем простые комбинации, и когда я включил его в php, он отлично справился с задачей, не нужно беспокоиться о перекрытиях или чем-то еще.