Изменение порядка элементов массива

Question

Для массива

[a1 a2 a3 ... an b1 b2 b3 ... bn c1 c2 c3 ...cn]

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

[a1 b1 c1 a2 b2 c2 a3 b3 c3 ... an bn cn]

Answer 1

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

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

Answer 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

Примечание: это произойдет только тогда, когда 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]

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

Теперь, чтобы преобразовать a1 a2 ... an b1 b2 ... bn c1 c2 ... cn

в

[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) пространство.

Answer 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)]

Answer 4

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

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

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

Затем вы берете карту А3 и путе Переместите с1 в положение а3 и сдвиньте все карты вверх.

Затем верните карту a3 в опустошенное положение.

повторять, пока не будет сделано.

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