Перечисление всех строк, соответствующих заданным ограничениям

Question

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

У меня есть алфавит из трех символов {-1, 0, 1}.

Мне нужно эффективно сгенерировать все строки длиной 24, которые в основном {0}, но содержат от нуля до восьми {1, -1} символов, распределенных в определенных шаблонах. (Шаблоны включают ограничения на количество и пары {-1}). Общее количество строк, соответствующих моим критериям, довольно скромное: около 128 000.

Итак, как называется этот класс задач / алгоритмов?

Answer 1

Я не уверен, что существует четко определенный " алгоритм класса " для этого это; это просто упражнение в комбинаторике. Вы можете сделать генерацию в три этапа:

<Ол>

Генерация всех 24-битных чисел с установленным 8 или менее битами (вы можете ускорить это, если предварительно вычислите некоторые таблицы поиска)

Для каждого 24-битного числа с установленным n битами повторяйте все n-битные числа

Если k-й бит n-битного числа равен 0, то k-й установленный бит 24-битного числа печатается как -1, в противном случае он печатается как 1

Чтобы объяснить шаги 2-3 немного лучше, скажем, что у вашего 24-битного числа установлено 4 бита, и оно выглядит как

0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0

Затем мы перебираем все 16 4-битных чисел от 0 0 0 0 до 1 1 1 1 и, например:

0 0 0 0 gives the string  0 0 0 -1 0 0 0 0 0 0 0 0 -1 -1 0 0 0 0 0 -1 0 0 0 0
0 1 1 0 gives the string  0 0 0 -1 0 0 0 0 0 0 0 0  1  1 0 0 0 0 0 -1 0 0 0 0
0 1 0 0 gives the string  0 0 0 -1 0 0 0 0 0 0 0 0  1 -1 0 0 0 0 0 -1 0 0 0 0
1 1 1 1 gives the string  0 0 0  1 0 0 0 0 0 0 0 0  1  1 0 0 0 0 0  1 0 0 0 0

Answer 2

Если вам нужно решить это только один раз, возможно, вы можете просто перебрать его и поместить результаты в таблицу поиска в вашем приложении. Для проверки требуется менее триллиона 24-битных последовательностей 0,1, -1.

Если, возможно, я неправильно делаю математику или вам нужно динамически решать проблему во время выполнения, я бы рассмотрел проблему как систему из 24 переменных, каждая из которых ограничена -1, 0, 1, и обозначил бы ее как < a href = "http://en.wikipedia.org/wiki/Constraint_satisfaction_problem" rel = "nofollow noreferrer"> Проблема удовлетворения ограничений , если предположить, что вы можете каким-то образом перечислить свои ограничения. Однако меня беспокоит то, что, поскольку вам требуется видеть все решения, а не просто подмножество, вы все равно можете застревать в процессе поиска проблемного пространства.

Этот документ кажется вам правильным: Перечисление всех решений проблем, связанных с удовлетворением ограничений . Хотя у меня нет доступа к полному тексту статьи, чтобы посмотреть, поможет ли это.

Возможно, я все вместе лаю не на том дереве, но, возможно, это отправная точка

Answer 3

Полностью отдельный ответ из моего последнего, поскольку рабочий код имеет тенденцию превосходить ссылки на исследовательские работы, я нашел этот код по адресу Физический форум и сам не могу за это поверить, я просто исправил его, чтобы он компилировался в g ++ и изменился на константы, чтобы искать 8 бит в 24. Он очень быстро перечисляет все 24 битовые строки с 8 битами, и их всего около 735 000. Эти «шаблоны» показывают единственные допустимые шаблоны для ваших ненулевых символов. Затем вам нужно будет взять каждый из этих 735 000 ответов и обойти знаки - / + и решить, соответствует ли каждый из них вашим критериям, но таким образом вы начинаете с 735 тысяч возможных решений вместо 200 миллиардов.

#include <stdio.h>

 int main()
 {
 int size = 24;
 int pop = 8;

 int n = ((1 << pop) - 1) << (size - pop);

 while(true) {
    printf( "%x\n",n);

    int lowest = n & -n;

     if(lowest > 1) {
        n = n ^ lowest ^ (lowest >> 1);
        continue;
     }

     int high = n & (n + lowest);
     if(high == 0) break;

     int low = n ^ high;

     low = (low << 2) + 3;

     while((low & high) == 0) low <<= 1;
     n = high ^ low;
  }
 }