Переупорядочение элементов массива

Ответ 1

Ваш вопрос также можно перефразировать как "Как сделать транспонирование на месте?". Чтобы понять, почему, представьте себе добавление новой строки после каждой подпоследовательности в обоих ваших массивах. Это превратит первый массив в матрицу NxM, а второй - в матрицу MxN.

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

Ответ 2

Предполагая, что вы имеете в виду память O (1) (или в зависимости от модели O (log n)), а не дополнительную память, существует алгоритм линейного времени на месте.

Эта статья: http://arxiv.org/abs/0805.1598 имеет алгоритм для случая, когда у вас

a1 ... an b1 ... bn и хотите преобразовать в

b1 a1 b2 a2 ... bn an.

В документе также упоминается, что вы можете обобщить это на другие k-way shuffles. В вашем случае k = 3.

Алгоритм в статье даст следующее:

Начните с a1 a2 ... an b1 b2 ... bn c1 c2 ... cn и конвертируйте в

c1 b1 a1 c2 b2 a2 ... cn bn an

Пропустите это, и вы можете легко получить a1 b1 c2 a2 b2 c2 ... an bn cn.

Теперь, чтобы обобщить алгоритм в работе, нам нужно выбрать простое p, такое, что k является примитивным корнем из p ^ 2.

При k = 3 будет выполняться p = 5.

Теперь, чтобы применить алгоритм, сначала вам нужно найти наибольшее значение m < n такое 3m + 1 является степенью 5.

Примечание: это произойдет только тогда, когда 3m + 1 - четная мощность 5. Таким образом, вы можете работать с полномочиями 25 при попытке найти m. (5 ^ нечетное - 1 не делится на 3).

Как только вы найдете m,

Вы перетасовываете массив, чтобы быть

[a1 a2 ... am b1 b2 ... bm c1 c2 ... cm] [a(m+1) ... an b(m+1) ... bn c(m+1) ... cn]

а затем используйте следующий метод цикла (обратитесь к статье) для первых 3m элементов, используя степени 5 (включая 1 = 5 ^ 0) в качестве отправных точек для разных циклов) и выполните хвостовую рекурсию для остальные.

Теперь конвертировать a1 a2 ... an b1 b2 ... bn c1 c2 ... cn

to

[a1 a2 ... am b1 b2 ... bm c1 c2 ... cm] [a(m+1) ... an b(m+1) ... bn c(m+1) ... cn]

сначала сделайте циклический сдвиг, чтобы получить

a1 a2 ... am [b1 b2 bm a(m+1) .. an] b(m+1) .. bn c1 c2 ... cn

(элементы в квадратных скобках - это те, которые были сдвинуты)

Затем сделайте циклический сдвиг, чтобы получить

a1 a2 ... am b1 b2 bm a(m+1) .. an [c1 c2 ..cm b(m+1) .. bn ] c(m+1) ... cn

И затем окончательный переход на

a1 a2 ... am b1 b2 bm [c1 c2 ..cm a(m+1) .. an ] b(m+1) .. bn c(m+1) ... cn

Обратите внимание, что циклический сдвиг может выполняться в O (n) времени и O (1) пространстве.

Таким целым алгоритмом является O (n) время и O (1) пространство.

Ответ 3

Вы можете рассчитать каждую позицию цели в зависимости от ее индекса.

groupSize = N/3
group = i/groupSize
rank = i - group * groupSize
dest = rank * 3 + group

Вы можете использовать этот расчет с сортировкой цикла, чтобы каждый элемент находился в правильном месте в линейном времени. Единственная проблема - отслеживать, какие элементы уже существуют. Все, что вам нужно, это N бит. С определенными типами данных вы можете "украсть" бит из самого элемента данных. Например, вы можете использовать высокий бит данных ASCII или младший байт выровненных по словам указателей.

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

source = i % groupSize + groupSize * (i/groupSize) ;  //integer division

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

getSource(i):
   s = i % groupSize + groupSize * (i/groupSize)
   while (s<i)
      s = s % groupSize + groupSize * (s/groupSize)
   return s

shuffle:
for i in (0..N-1) 
   swap(a[i],a[getSource(i)]

Ответ 4

Вы можете сделать это наверняка - просто возьмите карты туза, 2,... 5 в 3 костюмах и поместите их в порядок.

Сначала вы вынимаете карту a2 и откладываете ее. Затем вы перемещаете b1 в положение a2 и сдвигаете все карты вверх

Затем вы вернете карту a2 и поместите ее в сдвинутое положение.

Затем вы вынимаете карту a3 и puti taside Переместите c1 в позицию a3 и сдвиньте все карты вверх.

Затем верните карту a3 в опустошенную позицию.

повторить до завершения.

Фактический расчет индексов сложный, но я считаю, что предыдущий плакат сделал это.