Блог

Учитывая определение инверсии, как показано ниже

Инверсии: Учитывая доску, инверсией является любая пара плиток i и j, где i

У меня есть массив, подобный

arr = [1, 20, 6, 4, 22 , 5 , 12 , 3];

и функция для подсчета количества инверсий:

 function getInvCount(arr){
let inv_count = 0;
for(let i=0; i<arr.length-1; i  ){
    for(let j=i 1; j<arr.length; j  ){
        if(arr[i] > arr[j]) inv_count  ;
    }
}
return inv_count;
 

}

что я хочу сделать, так это, если число инверсий нечетное, внести изменения в массив, чтобы он дал мне четное число инверсий.

Как мне это сделать?

На самом деле (спасибо @MattTimmermans за то, что заметил это), здесь должна работать замена любой пары элементов, а не только последовательных.

Давайте возьмем вашу функцию…

 function getInvCount(arr){
  let inv_count = 0;
  for(let i=0; i<arr.length-1; i  ){
    for(let j=i 1; j<arr.length; j  ){
        if(arr[i] > arr[j]) inv_count  ;
    }
  }
}

arr[0] => compared with arr[1], ..., arr[k], arr[k   1], ..., arr[k   x], ..., arr[-1]
arr[1] => compared with arr[2], ..., arr[k], arr[k   1], ..., arr[k   x], ..., arr[-1]
...
arr[k]     => compared with arr[k   1], arr[k   2], ..., arr[k   x], ..., arr[-1]
arr[k   1] => compared with arr[k   2], arr[k   3], ..., arr[k   x], ..., arr[-1]
... 
arr[k   x] => compared with arr[k   x   1], arr[k   x   2], ..., arr[-2], arr[-1]
...
 

… и проанализируйте его, предположив, что мы поменяли местами элементы k и k x индексы. Как это изменило результат?

 arr[0] => compared with arr[1], ..., arr[k   x], arr[k   1], ..., arr[k], ..., arr[-1]
arr[1] => compared with arr[2], ..., arr[k   x], arr[k   1], ..., arr[k], ..., arr[-1]
...
arr[k   x] => compared with arr[k   1], arr[k   2], ..., arr[k], ..., arr[-1]
arr[k   1] => compared with arr[k   2], arr[k   3], ..., arr[k], ..., arr[-1]
...
arr[k] => compared with arr[k   x   1], arr[k   x   2], ..., arr[-2], arr[-1]
...
 

Ну, на самом деле не намного. Любой предшествующий элемент arr[k] по — прежнему сравнивается с обоими arr[k] и arr[k x] -просто в другом порядке (сравнение с arr[k x] идет первым сейчас). И любой элемент, следующий за ними, все равно не сравнивается с этими элементами вообще. Таким образом, все if(arr[i] > arr[j]) проверки из предыдущего «состояния» все еще там, и, по-видимому, их результат тот же.

Единственные измененные сравнения находятся в [k, k x] диапазоне. Для первой строки вот как изменяются проверки:

 a[k] > a[k   1] is replaced by a[k   x] > a[k   1]
a[k] > a[k   2] is replaced by a[k   x] > a[k   2]
...
a[k] > a[k   x] is replaced by a[k   x] > a[k]
 

Кажется, трудно предсказать, как это повлияет на количество, так как нет никакой гарантии, насколько велики эти цифры. Но давайте посмотрим, как влияют проверки для следующей строки:

 a[k   1] > a[k   2] => the same
a[k   1] > a[k   3] => the same
...
a[k   1] > a[k   x] => a[k   1] > a[k]
...
 

Теперь мы видим, что существует всего пара замененных проверок, включающих элемент[k 1] :

 a[k] > a[k   1] => a[k   x] > a[k   1]
a[k   1] > a[k   x] => a[k   1] > a[k]
 

И это ключ: независимо от того, какова a[k 1] ценность, здесь ровно две проверки поменялись местами. То же самое, на самом деле, верно для любого числа от k до k x. Только для a[k x] элемента есть ровно один своп:

 a[k] > a[k   x] => a[k   x] > a[k]
 

Вот почему, независимо от того, какие числа вы поменяете местами, разница будет нечетным числом. Точное число «инверсионного различия» будет эквивалентно (x — 1) * 2 1, поэтому оно строго равно 1 для последовательных чисел, 3 для чисел, разделенных одним элементом и т. Д.