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

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

Для этих шаблонов нам нужно проверить, идентичны ли повернутые версии. Мы делаем это, применяя до трех поворотов на 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);

In C#:

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 наблюдения:

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

Итак, если мы применим эти наблюдения и развернем внутренний цикл 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 мкс на той же машине.

Мое решение: 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 мс

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

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

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

Я не думаю, что это похоже на случай со сферой, так как вы не можете вращаться по краям? 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.

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

Стоит отметить, что если вам действительно нужно, чтобы каждая фигура «выглядела» уникально, независимо от того, как она повернута или смещена, у вас очень мало выбора. Например, отдельный удар, независимо от того, ГДЕ он находится в сетке, всегда будет выглядеть одинаково. Кроме того, если принять квадратную сетку и круглые штифты и предположить, что незначительные различия в расстоянии (2) незначительны, тогда 2 отверстия по диагонали в ряду будут выглядеть так же, как два соседних штифта, поскольку все, что видит зритель, — это 2 отверстия, расположенные близко друг к другу. Точно так же 3 по диагонали будут выглядеть так же, как 3 по прямой, что резко ограничивает ваши возможности.

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

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

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

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

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

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

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

Точно так же, как повороты и перемещения обратимы, таковы же будут и наши операции. Если два движения отображают паттерн A в B, а затем B в C, мы, безусловно, можем скомпоновать движения, чтобы произвести преобразование, переводящее A в C. Ничегонеделание (преобразование идентичности) также допустимо, поэтому мы можем достичь A из A. Достижимость Таким образом, преобразование является отношением эквивалентности шаблонов высечки, и, таким образом, эквивалентные шаблоны разделяют пространство.

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

Учитывая шаблон, как нам найти его представителя с наименьшим весом? При проверке не гарантируется, что жадные алгоритмы будут работать. Мы можем обратиться к одному из бесчисленных алгоритмов эвристической оптимизации, или мы можем отметить, что мы перемещаем только 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 классов.

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

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

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

Тогда это будет выглядеть так с формулой комбинации C (n, k):

Итого = С(9,0)+С(9,1)+....+С(9,9)

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

Всего = 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

всего= 4+4=4*2=м*п

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

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

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

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

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

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