Подсчет перестановок строк

Question

Мне нужна помощь с проблемой.Если задана входная строка с повторениями, скажем «aab», как посчитать количество различных перестановок этой строки.Можно использовать одну формулу: n! / N1! N2! ..... nr!.

Однако для вычисления этих ni требуется время O (rn) и O (n), если мы используем таблицу поиска.

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

Заранее спасибо.

Answer 1

нет. различных перестановок будет n!/(c1!*c2*..*cn!) здесь n - длина строки

ck обозначает нет. вхождения каждого отдельного символа.

Например: строка: aabb n = 4 ca = 2, cb = 2
Раствор = 4! / (2! * 2!) = 6

Answer 2

Вы можете вести подсчет количества ходов для каждого персонажа и наращивать результат по мере продвижения. Это невозможно сделать лучше, чем O (n), поскольку, не глядя на каждый символ в строке, вы не сможете узнать, сколько в нем каждого символа.

Я написал некоторый код на Python с несколькими простыми модульными тестами. Код тщательно избегает больших промежуточных значений, когда результат будет небольшим (на самом деле, переменная result никогда не превышает len (s), умноженный на конечный результат). Если вы собираетесь кодировать это на другом языке, например, C, то вы можете использовать массив размером 256, а не defaultdict.

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

from collections import defaultdict

def permutations(s):
    seen = defaultdict(int)
    for c in s:
        seen[c] +=  1
    result = 1
    n = 0
    for k, count in seen.iteritems():
        for j in xrange(count):
            n += 1
            result *= n
            result //= j + 1
    return result

test_cases = [
    ('abc', 6),
    ('aab', 3),
    ('abcd', 24),
    ('aabb', 6),
    ('aaaaa', 1),
    ('a', 1)]
for s, want in test_cases:
    got = permutations(s)
    if got != want:
        print 'permutations(%s) = %s want %s' % (s, got, want)

Answer 3

Если вы хотите сделать это для очень больших строк, рассмотрите возможность использования гамма-функции (с гаммой (n + 1) = n!), Которая быстрее при больших n и все же дает вам точность с плавающей запятой даже в тех случаях, когда вы получите переполнение int.

Если у вас есть арифметика произвольной точности, вы, вероятно, можете уменьшить усилие до O (r + n), используя тот факт, что вы можете, например, напишите 1 * 2 * 3 * 1 * 2 * 3 * 4 * 1 * 2 * 3 * 4 * 5 * 6 * 7 как (1 * 2 * 3) ^ 3 * 4 ^ 2 * 6 * 7. Конечный результат будет по-прежнему иметь цифры O (rn), а потребление времени O (rn) все равно будет сохраняться, поскольку стоимость умножения увеличивается с увеличением числа.

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

Answer 4

Вам нужны приблизительные ответы или точные?Какую часть этого расчета вы считаете медленным?

Если вам нужны приблизительные ответы, используйте гамма-функцию, как предложил @Yannick Versley.

Если вам нужны точные ответы, вот как ябуду делать этоСначала я выясню основную факторизацию ответа, а затем умножу эти факторы.Это позволяет избежать разделения.Трудная часть выяснения первичной факторизации - это выяснение первичной факторизации n!.Для этого вы можете использовать трюк.Предположим, что p является простым числом, а k является целой частью n/p'. Then the number of times that p divides n! is k plus the number of times that p divides k . Proceed recursively and it is quick to see that, for instance, the number of times that 3 is a factor of 80! is 26 + 8 + 2 = 36`.Поэтому после того, как вы найдете простые числа до 'n', нетрудно найти простую факторизацию 'n!'.

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

Создайте массив из основных факторов.Смешайте это (чтобы смешать большие и маленькие факторы).Затем, если у вас есть как минимум 2 фактора в вашем массиве, возьмите первые два, умножьте их, вставьте в конец.Если у вас осталось одно число, это ваш ответ.

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

Answer 5

Как говорит @MRalwasser, число перестановок должно быть n !.Вы можете сгенерировать эти перестановки довольно просто, но время выполнения будет экспоненциальным, потому что вы должны экспоненциально набрать много выходных строк.(Быстрый способ показать O ( n !) = O (2 ⁿ ) с помощью формулы Стирлинга .)