Как вычислить перестановки за линейное время с одной изюминкой
https://stackoverflow.com/questions/483890
-
20-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
У меня проблема с планированием ресурсов в 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.
Есть какие-нибудь мысли о том, как лучше подсчитать перестановки, чем пытаться перечислить их все?
Решение
Если вам просто нужно количество строк определенной длины, вы можете просто умножить матрицу совместимости на саму себя несколько раз и суммировать ее значения.
н = длина строки
А = матрица совместимости
количество возможных строк = сумма Ан-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
Исходная матрица (строка я, столбец дж) можно рассматривать как количество строк, начинающихся с символа я, и чьим следующим символом является символ дж.В качестве альтернативы вы можете увидеть это как количество строк длины 2, которые начинаются с символа я и заканчивается символом дж.
Умножение матриц сохраняет этот инвариант, поэтому после возведения в степень Ан-1 будет содержать количество строк, начинающихся с символа я, имеет длину н, и заканчивается символом дж.
Видеть Википедия:Возведение в степень возведением в степень за алгоритм более быстрого вычисления степеней матриц.
(Спасибо stefan.ciobaca)
Этот конкретный случай сводится к формуле:
количество возможных строк = ж(н) = 4 + Σк=1..н 2⌊к-1⁄2⌋ = ж(н-1) + 2⌊н-1⁄2⌋
n f(n)
---- ----
1 5
2 6
3 8
4 10
5 14
6 18
7 26
8 34
9 50
10 66
Другие советы
Вы просто хотите знать, сколько строк заданной длины вы можете построить с помощью правил данной матрицы?Если да, то такой подход должен работать:
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))
Ваш алгоритм кажется оптимальным.
Как вы используете эти перестановки?Вы собираете их в один список или используете по одному?Так как таких перестановок огромное количество, то плохая производительность может быть из-за большого использования памяти (если собирать их все) или просто это занимает очень много времени.Вы просто не можете выполнить миллиарды циклов за тривиальное время.
Ответ на комментарий:
Если вы просто хотите их посчитать, вы можете использовать динамическое программирование:
Пусть count[n][m] — массив, где count[l][j] — количество таких перестановок, длина которых равна l и заканчивается на j,
тогда count[l][i] = count[l-1][i1]+count[l-1][i2]+..., где i1, i2, ...— это цифры, которые могут предшествовать i (их можно сохранить в заранее рассчитанном массиве).
Каждую ячейку счетчика можно заполнить путем суммирования K чисел (K зависит от совместимой матрицы), поэтому сложность равна O (KMN), M — длина перестановки, а N — общее количество цифр.
Возможно, я этого не понимаю, но разве это не будет обеспечено наличием таблицы списков, в которой для каждой цифры есть список допустимых цифр, которые могут следовать за ней.
Тогда ваша процедура генерации будет принимать накопленный результат, номер цифры и текущую цифру.Что-то вроде:
// 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.
Я не совсем понимаю, о чем вы спрашиваете, но поскольку потенциально их может быть n!перестановок строки из n цифр, вы не сможете перечислить их быстрее, чем n!.Я не совсем уверен, как вы думаете, что получили время выполнения O(n^2).
