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

Question

Нам даны массив -a и массив -b, состоящие из натуральных чисел.Как подсчитать все перестановки массива 'a', которые строго лексикографически меньше массива -b?

Массивы могут содержать до 10 ^ 5 целых чисел (положительных)

Пример:

1 2 3 лексикографически меньше 3 1 2

1 2 3 лексикографически меньше 1 4 5.

Я бы хотел, чтобы решение было на С ++.

Ввод: 3

1 2 3

2 1 3

Выход: 2

Только перестановки 1,2,3 и1,3,2 лексикографически меньше 2 1 3

Answer 1

Давайте просто займемся алгоритмом.Как только вы поймете это, реализация должна быть довольно простой.Похоже ли это на то, что вы ищете?

Псевдокод:

function get_perms(a,b)
    #count the number of digits in a that are <b[0]
    count = sum(a<b[0])
    Nperms = (len(a)-1)! #modify this formula as needed
    N = count*Nperms
    if sum(a==b[0]) > 0
        remove 1 b[0] from a
        # repeat the process with the substring assuming a[0]==b[0]
        N += sum(a==b[0])*get_perms(a,b[1:end])
    return N

main()
    get_perms(a,b)

Редактировать: Я немного искал.Я считаю, что это - это то, что вы ищете.