Наибольшая перестановка в k шагов (R)

Question

У меня есть проблема, когда я хотел бы заменить 2 числа в наборе на "k", чтобы каждый раз, когда они переключались, я получал максимально возможную перестановку и печатал ее после k-перестановок. Например, с k=2, для набора (1,4,2,5,3,3) в 1 шаг я поменял бы (1,5) на создание (5,4,2,1,3,3). На шаге 2 я бы поменял (2,3) на создание (5,4,3,1,3,2). Если после точки n

Пока это то, что у меня есть:

x<-y<-c(1,4,2,5,3,3)
sx<-sort(x,decreasing=TRUE)
if(k>=n){cat(sx)} else{ ### If we have more operations than numbers?
i<-0; k<-2
m<-max(y)
while(i<k){
  if(all(sort(x,decreasing=TRUE)==y)){break}
  i<-i+1
  a<-max(which(y==m))
  while(length(which(y[c(1:a)]<m))==0){
    m<-m-1
    a<-which(y==m) ### Location of the largest number
    if(length(a)==0){
      a<-1
      next
    }
    a<-max(a)
  }
  y[c(min(which(y[c(1:a)]<m)),a)]<-y[c(a,min(which(y[c(1:a)]<m)))]
}
cat(y)
}
5 4 2 1 3 3

По сути, код находит максимум текущего набора. Затем находит самое правое вхождение этого максимального числа. Затем находит самое левое число ниже максимального числа. Затем переключает их. Это продолжается до тех пор, пока мы не выполним k шагов ИЛИ не получим наибольшую перестановку перед k. Затем печатает это.

Этот код работает, но занимает слишком много времени, если для больших k больше 10^4 цифр. Есть ли способ уменьшить сложность до O(n) в R?

Answer 1

Вот O(n log n) алгоритм (O(n) невозможно только при сравнении, хотя, может быть, вы знаете что-то о вводимых числах).

Для каждой подмассивы перестановки, имеющей (индексированные нулями) границы [i 2^j, (i+1) 2^j) для некоторых целых i, j, сохраните минимальное и максимальное значение в подмассиве (т. е. установите древовидную структуру сегмента).

Найти максимум за интервал времени O(log n) разложить интервал на O(log n) элементарные интервалы и вернуть максимум из максимумов.

Найти самый правый максимум за элементарный промежуток времени O(log n), несколько раз спуститься к правому потомку, если его максимум равен цели, иначе спуститься к левому потомку.

Чтобы найти крайнее левое число ниже целевого числа в интервале времени O(log n) разложить интервал на O(log n) элементарные интервалы и найдите крайний левый элементарный интервал, минимум которого ниже, чем цель. Начиная с этого интервала, несколько раз спускайтесь к левому потомку, если его минимум ниже целевого, иначе спуск к правому потомку.

Следуя вашему примеру:

        1,5
  4,5         1,2         3,3
5     4     2     1     3     3

Мы только что переехали 5, а также 4 находится в правильном месте, поэтому мы хотим максимум на остальной части массива. Элементарные интервалы 2 1 а также 3 3, Максимум 3, Мы изучаем 3 3 и обнаружьте, что максимум в правильном ребенке, полностью в конце.

Теперь мы ищем крайнее левое число меньше 3, Элементарные интервалы 2 1 а также 3 3, Мы видим, что 2 1 имеет минимум меньше чем 3 Итак, мы исследуем это. Так же и левый ребенок 2 1, так 2 это то, что мы меняем 3 с.

       *1,5*
  4,5        *1,2*       *3,3*
5     4     3     1     3     2

Агрегаты в *asterisks* может потребоваться обновление (предки поменявшихся значений). Есть O(log n) из этих. Мы работаем снизу вверх.

       *1,5*
  4,5         1,3        *3,3*
5     4     3     1     3     2

        1,5
  4,5         1,3        *3,3*
5     4     3     1     3     2

        1,5
  4,5         1,3         2,3
5     4     3     1     3     2