Почему в алгоритме нахождения числа перестановок ищется сумма по модулю 2?

Question

[Ирина Грачева]

Задача:
найти количество перестановок после ровно k количества прилегающих перестановок
https://www.hackerrank.com/challenges/swappermutat...
https://www.tutorialspoint.com/program-to-find-num...

Алгоритм:

M = 10**9+7
   A = [1]
   for n in range(2,n+1):
      B = A.copy()
      A = [1]
      limit=min(k+1, n*(n-1)//2+1)
      print(f"limit {limit}")
      for x in range(1, limit):
         print(f"x {x}, B, {B}, A {A}")
         A.append((A[-1] + (B[x] if x<len(B) else 0) - (B[x-n] if 0<=x-n else 0)) % M )
      print(f"normalA {A} cut {A[k%2:k+1:2]}")      
   return sum(A[k%2:k+1:2]) % M,C[min(n-1,k)]

Дебаг:

limit 3

x 1, B, [1, 1], A [1]

x 2, B, [1, 1], A [1, 2]

normalA [1, 2, 2] cut [1, 2]

Ответ: 3

Обьясненеие:
[1, 2, 3] k=2 ==> [1, 2, 3], [2, 3, 1], [3, 1, 2] ==> 3

Другой код

def swapPermutation(n, k):
    s = [1] + [0] * k
    t = [1] + [0] * k
    for i in range(1, n):
        ss = sum(s[max(k-i, 0):k]) % p
        for j in range(k, 0, -1):
            s[j] = (s[j] + ss) % p
            if j > i:
                ss = (ss + s[j - i - 1] - s[j-1]) % p
            else:
                ss = (ss - s[j-1]) % p
        for j in range(k, 0, -1):
            t[j] = (t[j] + i * t[j-1]) % p
    return sum(s[k%2::2]) % p, sum(t) % p

Не улавливаю идею

Comments

[Ирина Грачева]

что такое s в коде? Какую функцию он выполняет?

Answer 1

[Wataru]

Тут считается динамическое программирование f(i,j) - количество перестановок из i элементов с j инверсиями.

База: F(0, 0) = 1, F(i, j) = 0
Переход: F(i,j) = sum_t=0..min(j, i-1) F(i-1, j-t)

Тут мы берем все перестановки из i элементов и группируем их в зависимости от того, где стоит максимальный элемент. Этот максимальный элемент добавляет t - от 0 до min(j, i-1) инверсий. Если мы его выкинем, останеся перестановка из i-1 элемента и, чтобы полная перестановка имела j инверсий, эта урезанная должна иметь j-t.

Оба кода хранят только одну последнюю строку и пересчитывают ее через сумму на предыдущей итерации.
Ведь
F(i,j) = F(i-1, j-i+1) + F(i-1, j-i+2) +... + F(i-1, j)
F(i,j-1) = F(i-1, j-i) + F(i-1, j-i+1) +... + F(i-1, j-1)
Вычтя второе уравнение из первого получаем: F(i,j) -F(i,j-1) = F(i-1, j) - F(i-1, j-i). Или F(i,j) = F(i-1, j) - F(i-1, j-i) + F(i,j-1). Это ровно формула в первом решении.

В первом коде A - это вычесляемая текущая строка, B - копия предыдущей строки.
Во втором коде s - это текущая строка и следующая вычесляется прямо в этом же массиве. В переменной ss поддерживается сумма F(i-1,j-i+1)+..+F(i-1, j-1).

Ответ к задаче - это F(n, k)+F(n,k-2)+F(n,k-4)+...+F(n, k %2), потому что за каждую операцию мы или делаем +1 или -1 к количеству инверсий. Можно сколько-то раз сделать +1 -1, а потом сделать сколько осталось +1 и мы получим перестановки с инверсиями от 0 до k но той же четности, что и k (потому что каждая -1 вместо +1 уменьшает количество инверсий на 2).

Comments

[Ирина Грачева]

Спасибо Огромное!
Супер!
а t[j] как считается - почему это количество уникальных последовательностей после k количества прилегающих перестановок