Массив. Перемещение элементов

Пара очевидных вариантов: 1. Скопировать исходный массив, вытаскивать значения в результирующий из него. 2. Привести список пар к виду [(a, b), (b, c), (c, d) ...], заменяемое значение держать во временной переменной.

пусть n размер массива M c индексами 0..n-1

и у тебя есть операция которую z(x) которая сдвигает ( а по факту меняет местами m[x] и m[x+1]) . операция такая так?

ты совсем не можеш в рекурсию/индукцию?

смотри у тебя есть конечная последовательность которая показывает начальную перестановку S(0..n-1)==S(0..n-2)t

решение для S(n-1) при n>1:

где t(индекс Mконечное[n-1]) элемента который в новой позиции оказывается в конце

значит делаем z(t),z(t+1).... z(n-2)

и решаем задачу для S(n-2)

Пример 1 2 3 4 5 6 7 8 - их старое положение

8 1 7 5 2 4 3 6

z6:

1 2 3 4 5 7*6 8

z7:

1 2 3 4 5 7*8*6

----------------------

1 2 3 4 5 6 7 8

(1 2 3 4 5 7* 8*)6

z3z4z5z6:

(1 2 4*5*7**8**3)6

-------------------

1 2 3 4 5 6 7 8

(1 2 4*5*7**8**)3 6

и так далее

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

Грубо говоря у меня есть только: struct ICollection { long GetCount() = 0; void MoveTo(long OldIndex, long NewIndex) = 0; }

Непонятно.

a b c d e f g h - элементы коллекции
1 2 3 4 5 6 7 8 - их старое положение
8 1 7 5 2 4 3 6 - новое

а итоговая коллекция в этом случае как должна выглядить по твоему?

Так?

b e g f d h c a

которая при перемещении сдвигает старый элемент на новой позиции вправо

т.е. берем новое положение 'а' и перемещаем на 8-ю позицию, тогда 'h' сдвигается на 9-ю? И 'h' ты уже переместить не можешь, используя входящий массив?

(1 2 4*5*7**8**)3 6

</thread>

Если новый индекс элемента больше его первоначального, то все элементы коллекции, чьи индексы находятся между старым индексом элемента и новым (включая элемент, чье место займет текущий элемент), сдвинутся влево, то есть нужно будет сделать:

ПЕРЕМЕСТИТЬ(старая_позиция, старая_позиция - 1)

для каждого из этих элементов после перемещения текущего.

Наоборот, если элемент сдвигается влево, то сабсет перемещаемых элементов сдвигается вправо.

UPD: Перечитал ОП. Вообще не понял, что надо сделать.

#!/usr/bin/python

a=[x for x in "abcdefgh"]
old=[1,2,3,4,5,6,7,8]
new=[8,1,7,5,2,4,3,6]
b=[a[old.index(x)] for x in new]
def shift(a,i,j):
  assert(i<=j)
  return \
    a[:i]+ \
    a[i+1:j+1]+ \
    [a[i]]+ \
    a[j+1:]

for i in range(0,8)[::-1]:
  j = old.index(new[i])
  a=shift(a,j,i)
  del old[j]

print a
print b
assert(a==b)

по мотивам qulinxao

#!/usr/bin/python

:-)

по мотивам qulinxao

⊙_⊙

А, понял. Поправочка. Те элементы, которые уже передвинуты на новые позиции, нужно исключать из поправочного смещения.

Смотрел по диагонали, но похоже на прикрытую лабу). Например: jconsole -js 'echo (>:&.>) C. <: 8 1 7 5 2 4 3 6' 'exit 0' выведет группы. Просто перемещать начиная с первого - найдется какой-то цикл. Из необработанных берем следующий и т.д.

swap элементов делать нельзя?

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

Гм, я не уверен, что ты тот же анонимус, но, мне кажется, твой(?) код тоже далек от ТУ. Судить о рассуждениях qulinxao не берусь, я не понимаю его манеры изложения.

разъясняю

задача итеративна.

у нас есть конечная последовательность Р[1..n] == P[1..n-1]M[n]

значит мы можем ставить на конечную позицию элементы которые при дальнейших операциях не меняют своего положения

т.е сначала задвигаем тот который в оконцове окажется ультраправым. после этого решаем туже задачу для оставшейся возможно неупорядоченной последовательности на один элемент короче.

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

имхо тока соседей.

иначе(если в последовательности нельзя даже соседей менять - т.е некоторый аналог потока) задача решается разбиением последовательности на вплоть до N очередей(худщий случай - когда нам нужно реверсировать всю последовательность) и манипуляцией порядка помещения элементов в разные очереди и выхода из них.

т.е разбиение состава вагонов на разные пути и дольнейшие их слияние.

Неплохо. Можешь ведь, когда хочешь. Но, мне показалось, ТС хочет, чтобы все изменения происходили в исходной коллекции, а код анонимуса порождает новую. А если новую делать, можно проще сделать.

отлично, давай рассуждать

t = {...:  collection[oldindex - 1] for ...}

заменяемые значения держать во временной переменной не получится, копировать коллекции тоже

идем в начальную формулировку задачи:

Коллекция для перемещения имеет только операцию ПЕРЕМЕСТИТЬ... элемент... вправо.

можно было подумать, что слово «вправо» написано только для примера, можно принять это как ограничение. но все операции с коллекцией очевидно должны происходить через операцию «ПЕРЕМЕСТИТЬ», о чем автор темы второй раз указывает в этом сообщении

код:

a=shift(a,j,i)

def shift(a,i,j):
  assert(i<=j)

попробую пояснить на словах что qulinxao имел ввиду:

• операция z6 - это операция сдвига вправо 6-того элемента коллекции. та самая базовая операция описанная sotlef.
• z3z4z5z6 - это последовательное выполнение ряда сдвигов, то есть сдвиг элемента из позиции 3 на 4 позиции вправо (или shift(3-1,3-1+4)). в примере 3-ка из позиции 3 переместилась на 4 позиции вправо, за цифру 8. символ «*» при этом показывает путь цифры.
• скобки нужны для отделения изменяемой части от неизменной. наблюдая за их перемещением видно, что алгоритм «выталкивает» нужные элементы в право.

прошу прощения за количество слов в сообщении.

отлично, давай рассуждать

t = {...:  collection[oldindex - 1] for ...}

это перемещение элементов коллекции во внешнюю переменную.

это перемещение

Извини, ты хорошо знаешь семантику Python? В нем переменные - ссылки на объекты, и в моем коде и словарь t, и результирующая коллекция, список newcollection, будут содержать только ссылки на элементы коллекции collection. Копирование/перемещение не производится, появляются дополнительные ссылки. В этом можно убедиться, сравнив id элементов исходной и результирующей коллекций:

for oldindex, newindex in permuts_pairs:
    print id(collection[oldindex - 1]) == id(newcollection[newindex - 1]),

Конечно, это специфика Python, а не достоинство использованного «алгоритма».

Конечно же, алгоритм qulinxao является единственным решением, учитывая условия, ведь нигде не сказано, что коллекция подобна питоньим спискам и поддерживает все их возможности (поэтому и ваше решение не совсем точная реализация идеи из-за использования срезов хотя бы).

Всем спасибо.

Извини, ты хорошо знаешь семантику Python?

конечно нет. но для меня хранение ссылок на элементы исходного листа (коллекции) являлось критерием нарушающим пункт:

заменяемые значения держать во временной переменной не получится

а по поводу решения, оно мне показалось аналогом этой строчки:

b=[a[old.index(x)] for x in new]

не совсем точная реализация идеи из-за использования срезов хотя бы

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

#!/usr/bin/python

a=[x for x in "abcdefgh"]
old=[1,2,3,4,5,6,7,8]
new=[8,1,7,5,2,4,3,6]
b=[a[old.index(x)] for x in new]

class ICollection:
  def __init__(self, lst):
    self.a = lst
  def GetCount(self):
    return len(self.a)
  def MoveTo(self,i,j):
    assert(i<=j)
    self.a = \
      self.a[:i]+ \
      self.a[i+1:j+1]+ \
      [self.a[i]]+ \
      self.a[j+1:]

c = ICollection(a)
for i in range(0,8)[::-1]:
  j = old.index(new[i])
  c.MoveTo(j,i)
  del old[j]

print c.a
print b
assert(c.a==b)

а по поводу решения, оно мне показалось аналогом этой строчки:

Угу, так и есть, но у меня похуже аналог :/

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

Да, я понял, что это не часть алгоритма.

Вместо

range(0,8)[::-1]

я бы использовал

range(7, -1, -1)

т.е.

range(8 - 1, 0 - 1, -1)

Вместо ... я бы использовал

согласен полностью, исходная конструкция сбивает неподготовленного человека

сори , у мя z(pos) это swap в текущем массиве элементов на позициях pos и pos+1 - т.е элементарная

в терминах длинного сдвига

shift(from,to)==z(from),z(from+1)....z(to-1) // from <to

а так . ага.

перечитал, ну да z это элементарный сдвиг , ты get the point