Как найти количество перестановок числа?

Question

[New Developer]

Как найти количество уникальных перестановок числа, исключив комбинации, где 0 впереди ? Число может содержать до 10 цифр. Пример:
1200: [1200,1002,1020,2001,2010,2100,120,102,210,201,100,200,10,20,12,21,1,2] = 18
112: [112,121,211,12,21,11,1,2] = 8
102: [102,120,201,210,12,21,10,20,1,2] = 10
Какую литературу почитать ?

Answer 1

[Wataru]

Это комбинаторика.

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

Еще, в вашей формуле направшивается добавить пустое число ("") в ответ. Давайте разрешим его и вычтем в конце 1.

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

Поэтому пусть f(a0,a1,...a9) - сколько есть способов расставить некторые из a0 нулей, a1 единиц, a2 двоек, и т.д. (ноль может идти в начале, число может быть пустым).

Ответ к задаче f(a0,a1,...a9)-1-min(a0,1)*f(a0-1,a1,...a9). Последнее слагаемое считает варианты, начинающиеся с нуля. Оно не вычитается, если нулей в числе нет. -1 посередине вычитает пустое число из ответа (но ее нет в последнем слагаемом, ведь мы там еще 0 в начале приписываем и пустое число надо считать).

Теперь самое интересное, формула для f(a0,a1,...a9). Замкнутой формулы я не нашел, но придумал, как считать алгоритмом.

Можно все варинаты разделить по количеству символов в числе (n), от 0 до суммы a0...a9. Давайте подумаем, где могуть быть девятки? i <= a9 из них попадут в ответ. Они могут быть на C(n, i) позициях. Останется разместить остальные цифры на n-i позиций.

Вырисовывается следующее динамическое программирование:

F(i, n) - сколько способов разместить первые i цифр на n позициях (возможно, беря не все цифры).

F(i,n) = sum (j=0..min(a[i-1], n)) F(i-1, n-j)*C(n, j)
F(0, n>0) = 0
F(i,0) = 1.
Ответ - sum(k=0..a0+...+a9) F(9, k)

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

Не забудьте, что для подсчета второй динамики, для f(a0-1,...a9) надо будет полностью отчистить мемеоизацию, потому что массив a поменялся же.

Этот алгоритм работает за O(9*n), где n - длина входного числа.

Вот пример для входного числа 112: все цифры, которых в числе нет можно выкинуть из рассмотрения и работать с массивом a={2,1} (для всех десяти цифр слишком много писать).

F(0,0) = 1
F(0,1) = 0
F(0,2) = 0
F(0,3) = 0
F(1, 0) = 1
F(1,1) = F(0, 1)*C(1,0) + F(0,0)*C(1,1) = 1
F(1,2) = F(0,2)*C(2, 0)+ F(0,1)*C(2,1) + F(0,0)*C(2,2) = 1
F(1,3) = F(0,3)*C(3, 0)+ F(0,2)*C(3,1) + F(0,1)*C(3,2) = 0
F(2,0) = 1
F(2,1) = F(1,1)*C(1, 0) + F(1,0)*C(1,1) = 2
F(2,2) = F(1,2)*C(2, 0) + F(1,1)*C(2,1) = 3
F(2,3) = F(1,3)*C(3, 0) + F(1,2)*C(3,1) = 3

Ответ F(2,3)+F(2,2)+F(2,1)+F(2,0) = 3+3+2+1= 9.

Вычитаем 1 (пустое число) и получаем 8 чисел, как у вас в примере для 112.

Comments

[New Developer]

Не подскажете, существует ли способ для каждого размещения сразу вычитать все комбинации, начинающиеся с 0 ? Например для числа 1200 при количестве разрядов m=4 будет 4!/(2!(4-4)!) - ? = 6. А при m = 1 просто отфильтровать уникальные цифры за исключением 0.

[Wataru]

New Developer, Ну ведь я же и предлагаю вычитать эти, начинающиеся с нуля. Просто вычеркиваем один ноль и решаем ту же самую задачу.

Тут же не только количество разрядов нужно, еще имеет значение, какие и сколько цифр можно использовать. Например для 120 - ответ 5 (0, 01, 02, 012, 021). Для 220 - ответ 3 (0, 02, 022).

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