Как рассчитать перестановки в линейное время, с изюминкой

Question

У меня есть проблема с планированием ресурсов в Java, где необходимо упорядочить объекты, но есть ограничения на то, какие ресурсы могут быть рядом друг с другом. Хорошая аналогия - это строка «цифр», где рядом могут быть только определенные цифры. Мое решение было рекурсивным и прекрасно работает для небольших строк, но время выполнения равно O (X ^ N), где X - количество возможных цифр (основание), а N - длина строки. Это быстро становится неуправляемым.

Используя приведенную ниже матрицу совместимости, вот несколько примеров допустимых строк
Длина 1: 0, 1, 2, 3, 4
Длина 2: 02, 03, 14, 20, 30, 41
Длина 3: 020, 030, 141, 202, 203, 302, 303, 414

     0  1  2  3  4
   ---------------------
0|  0  0  1  1  0
1|  0  0  0  0  1
2|  1  0  0  0  0
3|  1  0  0  0  0
4|  0  1  0  0  0

Мое решение для подсчета всех строк длины N было начать с пустой строки, переставить первую цифру и сделать рекурсивный вызов для всех строк длины N-1. Рекурсивные вызовы проверяют последнюю добавленную цифру и пробуют все перестановки, которые могут быть рядом с этой цифрой. Были сделаны некоторые оптимизации, чтобы я не пытался переставлять 00, 01, 04 каждый раз, например - только 02, 03, но производительность все еще остается низкой, поскольку он масштабируется от базовой 5 (пример) до базовой 4000.

Есть какие-нибудь мысли о лучшем способе подсчета перестановок, кроме попыток перечислить их все?

Answer 1

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

n = длина строки
A = матрица совместимости
количество возможных строк = сумма A ^{n -1}

Несколько примеров:

n = 1
| 1 0 0 0 0 |
| 0 1 0 0 0 |
| 0 0 1 0 0 |
| 0 0 0 1 0 |
| 0 0 0 0 1 |
sum: 5

n = 3
| 2 0 0 0 0 |
| 0 1 0 0 0 |
| 0 0 1 1 0 |
| 0 0 1 1 0 |
| 0 0 0 0 1 |
sum: 8

n = 8
| 0 0 8 8 0 |
| 0 0 0 0 1 |
| 8 0 0 0 0 |
| 8 0 0 0 0 |
| 0 1 0 0 0 |
sum: 34

Исходная матрица (строка i , столбец j ) может рассматриваться как число строк, начинающихся с символа i , и следующий символ которых является символом j . В качестве альтернативы вы можете увидеть его как число строк длиной 2 , которые начинаются с символа i и заканчиваются символом j .

Матричное умножение сохраняет этот инвариант, поэтому после возведения в степень A ^{n -1} будет содержать количество строк, начинающихся с символа i , имеет длину n и оканчивается символом j .

См. Википедия: Вычисление в квадрате для алгоритма для более быстрого вычисления степеней матрицы.

(спасибо stefan.ciobaca)

Этот конкретный случай сводится к формуле:

количество возможных строк = f ( n ) = 4 + & Sigma; _{k = 1 .. n} 2 ^{& lfloor; k -1 & frasl; ₂ & rfloor;} = f ( n -1) + 2 ^{n -1 & frasl; ₂ & rfloor;}

n       f(n)
----    ----
   1       5
   2       6
   3       8
   4      10
   5      14
   6      18
   7      26
   8      34
   9      50
  10      66

Answer 2

Вы хотите знать, сколько строк заданной длины вы можете построить с помощью правил в данной матрице? Если так, то такой подход должен работать:

n = 5
maxlen = 100

combine = [
      [0, 0, 1, 1, 0],
      [0, 0, 0, 0, 1],
      [1, 0, 0, 0, 0],
      [1, 0, 0, 0, 0],
      [0, 1, 0, 0, 0]
   ]

# counts of strings starting with 0,1,...,4, initially for strings of length one:
counts = [1, 1, 1, 1, 1]

for size in range(2, maxlen+1):
   # calculate counts for size from count for (size-1)
   newcount = []
   for next in range(n):
      total = 0
      for head in range(n):
         if combine[next][head]:
            # |next| can be before |head|, so add the counts for |head|
            total += counts[head]
      # append, so that newcount[next] == total
      newcount.append(total)
   counts = newcount
   print "length %i: %i items" % (size, sum(counts))

Answer 3

Ваш алгоритм кажется оптимальным.

Как вы используете эти перестановки? Вы накапливаете их в одном списке или используете по одному? Поскольку таких перестановок огромное количество, низкая производительность может быть вызвана большим использованием памяти (если вы собираете их все) или просто занимает много времени. Вы просто не можете делать миллиарды циклов в тривиальное время.

Ответ на комментарий:

Если вы просто хотите их посчитать, то вы можете использовать динамическое программирование:

Пусть count [n] [m] - массив, где count [l] [j] - количество таких перестановок, длина которых равна l и заканчивается j,

затем count [l] [i] = count [l-1] [i1] + count [l-1] [i2] + ..., где i1, i2, ... - цифры, которые могут предшествовать я (это может быть сохранено в предварительно рассчитанном массиве).

Каждая ячейка счетчика может быть заполнена суммированием K чисел (K зависит от совместимой матрицы), поэтому сложность составляет O (KMN), M - это длина перестановки, а N - общее количество цифр.

Answer 4

Я не совсем уверен, что вы спрашиваете, но так как потенциально есть п! перестановки строки из n цифр, вы не сможете перечислить их быстрее, чем n !. Я не совсем уверен, как вы думаете, вы получили время выполнения O (n ^ 2).

Answer 5

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

Тогда ваша процедура генерации примет накопленный результат, цифру и текущую цифру. Что-то вроде:

// not really Java - and you probably don't want chars, but you'll fix it
void GenerateDigits(char[] result, int currIndex, char currDigit)
{
    if (currIndex == kMaxIndex) {
        NotifyComplete(result);
        return;
    }
    char[] validFollows = GetValidFollows(currDigit); // table lookup
    foreach (char c in validFollows) {
        result[currIndex] = c;
        GenerateDigits(result, currIndex+1, c);
    }
}

Сложность возрастает как функция количества генерируемых цифр, но эта функция зависит от общего числа действительных подписок для любой одной цифры. Если общее число повторений одинаково для каждой цифры, скажем, k, то время для генерации всех возможных перестановок будет O (k ^ n), где n - количество цифр. Извините, я не могу изменить математику. Время создания n цифр в базе 10 составляет 10 ^ n.