Ответ 1

Решение нуждается в некоторых объяснениях.  Обозначим число перестановок с n элементами, имеющими ровно k инверсий  через я (n, k)

Теперь я (n, 0) всегда 1. Для любого n существует одна и только одна перестановка, которая имеет 0  инверсии, т.е. когда последовательность все больше сортируется

Теперь я (0, k) всегда 0, так как у нас нет самой последовательности

Теперь, чтобы найти я (n, k), возьмем пример последовательности, содержащей 4 элемента  {1,2,3,4}

для n = 4 ниже перечислены перестановочные и сгруппированные по числу инверсий

|___k=0___|___k=1___|___k=2___|___k=3___|___k=4___|___k=5___|___k=6___|
| 1234    | 1243    | 1342    | 1432    | 2431    | 3421    | 4321    |
|         | 1324    | 1423    | 2341    | 3241    | 4231    |         |
|         | 2134    | 2143    | 2413    | 3412    | 4312    |         |
|         |         | 2314    | 3142    | 4132    |         |         |
|         |         | 3124    | 3214    | 4213    |         |         |
|         |         |         | 4123    |         |         |         |
|         |         |         |         |         |         |         |
|I(4,0)=1 |I(4,1)=3 |I(4,2)=5 |I(4,3)=6 |I(4,4)=5 |I(4,5)=3 |I(4,6)=1 |
|         |         |         |         |         |         |         |

Теперь, чтобы найти число перестановок с n = 5 и для всех возможных k мы можем получить рекуррент я (5, k) из я (4, k) путем вставки n-го (наибольшего) элемент (5) где-то в каждой перестановке в предыдущих подстановках, так что результирующее число инверсий равно k

например, я (5,4) - не что иное, как число перестановок последовательности {1,2,3,4,5} который имеет ровно 4 инверсии каждый. Пусть теперь наблюдение я (4, k) выше, пока столбец k = 4 не будет числа инверсий &lt = 4 Теперь разместим элемент 5, как показано ниже

|___k=0___|___k=1___|___k=2___|___k=3___|___k=4___|___k=5___|___k=6___|
| |5|1234 | 1|5|243 | 13|5|42 | 143|5|2 | 2431|5| | 3421    | 4321    |
|         | 1|5|324 | 14|5|23 | 234|5|1 | 3241|5| | 4231    |         |
|         | 2|5|134 | 21|5|43 | 241|5|3 | 3412|5| | 4312    |         |
|         |         | 23|5|14 | 314|5|4 | 4132|5| |         |         |
|         |         | 31|5|24 | 321|5|4 | 4213|5| |         |         |
|         |         |         | 412|5|3 |         |         |         |
|         |         |         |         |         |         |         |
|    1    |    3    |    5    |    6    |    5    |         |         |
|         |         |         |         |         |         |         |

Каждая из перечисленных выше перестановок, содержащая 5, имеет ровно 4 инверсии. Таким образом, полная перестановка с 4 инверсиями я (5,4) = я (4,4) + я (4,3) + я (4,2) + я (4,1) + я (4,0)                                                 = 1 + 3 + 5 + 6 + 5 = 20

Аналогично для я (5,5) из я (4, k)

|___k=0___|___k=1___|___k=2___|___k=3___|___k=4___|___k=5___|___k=6___|
|   1234  | |5|1243 | 1|5|342 | 14|5|32 | 243|5|1 | 3421|5| | 4321    |
|         | |5|1324 | 1|5|423 | 23|5|41 | 324|5|1 | 4231|5| |         |
|         | |5|2134 | 2|5|143 | 24|5|13 | 341|5|2 | 4312|5| |         |
|         |         | 2|5|314 | 31|5|44 | 413|5|2 |         |         |
|         |         | 3|5|124 | 32|5|14 | 421|5|3 |         |         |
|         |         |         | 41|5|23 |         |         |         |
|         |         |         |         |         |         |         |
|         |    3    |    5    |    6    |    5    |    3    |         |
|         |         |         |         |         |         |         |

Таким образом, полная перестановка с 5 инверсиями я (5,5) = я (4,5) + я (4,4) + я (4,3) + я (4,2) + я (4,1 )                                                 = 3 + 5 + 6 + 5 + 3 = 22

So I(n, k) = sum of I(n-1, k-i) such that i < n && k-i >= 0

Кроме того, k может перейти к n * (n-1)/2, это происходит, когда последовательность сортируется в порядке убывания https://secweb.cs.odu.edu/~zeil/cs361/web/website/Lectures/insertion/pages/ar01s04s01.html http://www.algorithmist.com/index.php/SPOJ_PERMUT1

#include <stdio.h>

int dp[100][100];

int inversions(int n, int k)
{
    if (dp[n][k] != -1) return dp[n][k];
    if (k == 0) return dp[n][k] = 1;
    if (n == 0) return dp[n][k] = 0;
    int j = 0, val = 0;
    for (j = 0; j < n && k-j >= 0; j++)
        val += inversions(n-1, k-j);
    return dp[n][k] = val;
}

int main()
{
    int t;
    scanf("%d", &t);
    while (t--) {
        int n, k, i, j;
        scanf("%d%d", &n, &k);
        for (i = 1; i <= n; i++)
            for (j = 0; j <= k; j++)
                dp[i][j] = -1;
        printf("%d\n", inversions(n, k));
    }
    return 0;
}

Ответ 2

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

После просмотра на странице страницы Википедии, в которой обсуждается инверсия в дискретной математике, я нашел интересную рекомендацию в нижней части страницы.

Число перестановок n элементов с k инверсиями; Mahonian числа: A008302

Я нажал на ссылку на OEIS и показал мне бесконечную последовательность целых чисел, называемую треугольником из числа махонов.

1, 1, 1, 1, 2, 2, 1, 1, 3, 5, 6, 5, 3, 1, 1, 4, 9, 15, 20, 22, 20, 15, 9, 4, 1, 1, 5, 14, 29, 49, 71, 90, 101, 101, 90, 71, 49, 29, 14, 5, 1, 1, 6, 20, 49, 98, 169, 259, 359, 455, 531, 573, 573, 531, 455, 359, 259, 169, 98, 49, 20, 6, 1.,.

Мне было любопытно, что это за цифры, которые мне показались знакомыми. Затем я понял, что видел подпоследовательность 1, 3, 5, 6, 5, 3, 1 раньше. Фактически это был ответ на проблему для нескольких пар (n, k), а именно (4, 0), (4, 1), (4, 2), (4, 3), (4, 4), (4, 5), (4, 6). Я посмотрел на то, что было по обе стороны от этой подпоследовательности, и был поражен, увидев, что все это действительное (то есть большее, чем 0 перестановок) ответы для n < 4 и n > 4.

Формула для последовательности была задана как:

в разложении Product_ {i = 0..n-1} (1 + x +... + x ^ i)

Мне было легко понять и проверить. Я мог бы в принципе взять все n и подключить к формуле. Тогда коэффициент для члена х ^k был бы ответом для (n, k).

Я покажу пример для n = 3.

(x0)(x0 + 1)(x0 + x1 + x2) = (1)(1 + x)(1 + x + x2) = (1 + x)(1 + x + x2) = 1 + x + x + x2 + x2 + x3 = 1 + 2x + 2x2 + x3

Окончательное разложение составляло 1 + 2x + 2x2 + x3, а коэффициенты членов x ^k составляли 1, 2, 2 и 1 для k = 0, 1, 2, 3 соответственно. Это просто все допустимые числа инверсий для 3-элементных перестановок.

1, 2, 2, 1 является третьей строкой числа махонов, когда они выложены в таблице следующим образом:

1
1 1
1 2 2 1
1 3 5 6 5 3 1
etc.

Таким образом, в основном вычисление моего ответа сводилось к простому вычислению n-й строки в Mahonian и взятию k-го элемента с k, начинающемуся с 0, и печати 0, если индекс был вне диапазона. Это был простой случай восходящего динамического программирования, так как каждая i-я строка могла использоваться для легкого вычисления я + 1-й строки.

Ниже приведено решение Python, которое я использовал, всего за 0,02 секунды. Максимальный срок для этой проблемы составлял 3 секунды для их данных тестов, и я получал ошибку таймаута, прежде чем я думаю, что эта оптимизация довольно хороша.

def mahonian_row(n):
    '''Generates coefficients in expansion of 
    Product_{i=0..n-1} (1+x+...+x^i)
    **Requires that n is a positive integer'''
    # Allocate space for resulting list of coefficients?
    # Initialize them all to zero?
    #max_zero_holder = [0] * int(1 + (n * 0.5) * (n - 1))

    # Current max power of x i.e. x^0, x^0 + x^1, x^0 + x^1 + x^2, etc.
    # i + 1 is current row number we are computing
    i = 1
    # Preallocate result
    # Initialize to answer for n = 1
    result = [1]
    while i < n:
        # Copy previous row of n into prev
        prev = result[:]
        # Get space to hold (i+1)st row
        result = [0] * int(1 + ((i + 1) * 0.5) * (i))
        # Initialize multiplier for this row
        m = [1] * (i + 1)
        # Multiply
        for j in range(len(m)):
            for k in range(len(prev)):
                result[k+j] += m[j] * prev[k]
        # Result now equals mahonian_row(i+1)
        # Possibly should be memoized?
        i = i + 1
    return result


def main():
    t = int(raw_input())
    for _ in xrange(t):
        n, k = (int(s) for s in raw_input().split())
        row = mahonian_row(n)
        if k < 0 or k > len(row) - 1:
            print 0
        else:
            print row[k]


if __name__ == '__main__':
    main()

Я понятия не имею о временной сложности, но я абсолютно уверен, что этот код можно улучшить с помощью memoization, так как есть 10 заданных тестов случаи и вычисления для предыдущих тестовых случаев могут быть использованы для "обмана" будущих тестов. Я буду делать эту оптимизацию в будущем, но, надеюсь, этот ответ в текущем состоянии поможет любому, кто пытается эту проблему в будущем, избегать наивного подхода с факториальной сложностью генерации и итерации через все перестановки.

Ответ 3

Если есть решение динамического программирования, возможно, есть способ сделать это шаг за шагом, используя результаты для перестановок длины n, чтобы помочь с результатами для перестановок длины n + 1.

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

Итак, если вы рассматриваете одно из n + 1 мест, где вы можете добавить (n + 1), если вы добавите его в место j, считая справа, так что последняя позиция как позиция 0 - количество перестановок с K-инверсиями, которое это создает число перестановок с инверсиями Kj на n местах.

Итак, если на каждом шаге вы подсчитываете количество перестановок с K-инверсиями для всех возможных K, вы можете обновить количество перестановок с помощью K инверсий для длины n + 1, используя число перестановок с K инверсиями для длины n.

Ответ 4

Основная проблема при вычислении этих коэффициентов - размер порядка полученного продукта. Полиномиальный продукт я = 1,2,..., n {(1 + x). (1 + x + x ^ 2).... (1 + x + x ^ 2 +.. + x ^ i) +... (1 + x + x ^ 2 +... + x ^ n) будет иметь порядок, эквивалентный n * (n + 1). Следовательно, это налагает ограничительный вычислительный предел на процесс. Если мы используем процесс, в котором предыдущие результаты для продукта для n-1 используются в процессе вычисления Продукта для n, мы рассматриваем хранение (n-1) * n целых чисел. Можно использовать рекурсивный процесс, который будет намного медленнее, и снова он будет ограничен целыми числами меньше квадратного корня из общего размера целого. Ниже приведен пример грубого и готового рекурсивного кода для этой проблемы. Функция mahonian (r, c) возвращает c-й коэффициент для r-го Продукта. Но снова это очень медленно для крупных продуктов, которые превышают 100 или около того. Запустив это, можно видеть, что рекурсия явно не является ответом.

unsigned int numbertheory::mahonian(unsigned int r, unsigned int c)
  {
      unsigned int result=0;
      unsigned int k;

     if(r==0 && c==0)
       return 1;
     if( r==0 && c!=0)
      return 0;

   for(k=0; k <= r; k++)
       if(r > 0 && c >=k)
           result = result + mahonian(r-1,c-k);

   return result;

}

В качестве интереса я включил следующее, которое является версией Sashank С++, которая намного быстрее, чем мой пример рекурсии. Примечание. Я использую библиотеку armadillo.

uvec numbertheory::mahonian_row(uword n){
 uword i = 2;
 uvec current;
 current.ones(i);
 uword current_size;
 uvec prev;
 uword prev_size;

 if(n==0){
   current.ones(1);
   return current;
 }

 while (i <= n){                  // increment through the rows
   prev_size=current.size();     // reset prev size to current size
   prev.set_size(prev_size);     // set size of prev vector
   prev= current;                //copy contents of current to prev vector
   current_size =1+ (i*(i+1)/2);      // reset current_size
   current.zeros(current_size);    // reset current vector with zeros

   for(uword j=0;j<i+1; j++)       //increment through current vector
      for(uword k=0; k < prev_size;k++)
         current(k+j) += prev(k);
   i++;                                        //increment to next row
}
return current;                                //return current vector
 }

 uword numbertheory::mahonian_fast(uword n, uword c) {
**This function returns the coefficient of c order of row n of
**the Mahonian numbers
    // check for input errors
    if(c >= 1+ (n*(n+1)/2)) {
        cout << "Error. Invalid input parameters" << endl;
   }
   uvec mahonian;
   mahonian.zeros(1+ (n*(n+1)/2));
   mahonian = mahonian_row(n);
   return mahonian(c);
 }