на месте перестановка массива следует этому правилу

Question

Предположим, есть массив, мы хотим найти все в нечетном индексе (индекс начинается с 0) и переместить его в конец. Все в четном указателе перемещает его в начало. Относительный порядок всех нечетных элементов индекса и всех четных элементов индекса сохраняется.

т.е. если массив

a1 b1 a2 b2 ...  an bn    

после операции становится

a1 a2 a3 ... an b1 b2 ... bn

Можно ли это сделать на месте и в O (n) время?

Answer 1

Это возможно, но это очень сложно! Простое решение O (nlogn) и O (1) может быть лучше для кода и с точки зрения кэша.

Мы решим проблему, отличную от вашей, но ваша проблема будет тривиальна, когда мы решим эту проблему.

Рассмотрим массив как

b1, a1, b2, a2, ..., bn, an

, и вы должны преобразовать это в

a1, a2, ..., an, b1, b2, ..., bn

Работа с индексами от 1 до 2n,

мы видим, что это дается

i -> (n+1)*i (mod 2n+1).

---

O (nlogn) время O (1) пространственное решение

Мы можем использовать разделяй и властвуй следующим образом.

Сначала для некоторого m, близкого к n / 2, преобразовать

b1, a1, ..., bn , an

до

a1,a2,...am, b1,b2, ..bm, a(m+1), ..., an, b(m+1), ... , bn

путем рекурсивного применения к первым 2м элементам, а затем к остальным.

Теперь все, что нам нужно сделать, это циклическое смещение среднего массива на m точек (это можно сделать за O (n) времени и O (1) пространства)

дать

a1, a2, .., am , a(m+1), ..., an, b1, b2, ..., bm, b(m+1), ..., bn.

Конечно, как указал IVlad, для этого требуется O (logn) стекового пространства. Мы можем обойти это, выполнив следующее:

У нас есть:

b1 a1, b2 a2, .. bm am, b(m+1) a(m+1), ..., bn an

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

b1 a1, b2 a2, .. bm am, a(m+1) b(m+1), ..., an bn

Теперь циклически сдвигаем элементы в нечетное положение: b1, b2, .., bm, a(m+1), a(m+2) ..., a(n).

Это дает что-то вроде

a(m+1) a1, a(m+2) a2, ..., a(2m) am, a(2m+1) b(m+1),...,an b(n-m), b1 b(n-m+1),...,bm bn

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

a(m+1) a1, a(m+2) a2, ..., a(2m) am, b(m+1) a(2m+1),...,b(n-m) an,b(n-m+1) b1,..., bn bm

Теперь рекурсивно решите первую часть и вторую часть, чтобы получить

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

Это работает независимо от того, 2m> = n или нет.

Итак, это алгоритм O (nlogn) времени и O (1).

---

O (n) время O (1) пространственное решение.

Используемые идеи аналогичны идеям, использованным в следующей статье: Простой алгоритм на месте для Inshuffle .

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

Это в основном обратная перестановка того, что решено в статье выше.

Достаточно решить эту проблему, когда 2n + 1 является степенью 3 = (скажем, 3 ^ m), так как после этого мы можем использовать разделяй и властвуй (как решение O (nlogn)).

Теперь 2n + 1 и n + 1 относительно простые, поэтому, работая по модулю 3 ^ m, мы видим, что n + 1 должно быть некоторой степенью 2. (Снова посмотрите эту статью, чтобы понять, почему: в основном любое число по модулю 3 ^ m, которое является относительным простым числом к ​​3 ^ m, является степенью 2, опять же по модулю 3 ^ m).

Скажите n + 1 = 2 ^ k (мы еще не знаем k и отметим, что это по модулю 3 ^ m).

Способ узнать k, вычислить степени n + 1 по модулю 3 ^ m, пока он не станет равным 1. Это дает нам k (и время O (n) самое большее).

Теперь мы можем видеть, что циклы перестановки (см. Выше ссылку paper / stackoverflow, что это такое) начинаются с

2 ^ а * 3 ^ Ь

, где 0 <= a <k и 0 <= b <m. </p>

Итак, вы начинаете с каждой возможной пары (a, b) и следуете циклам перестановки, и это дает алгоритм времени на месте O (n), когда вы касаетесь каждого элемента не более чем постоянным числом раз!

Это было немного кратко (!), И если вам нужна дополнительная информация, пожалуйста, дайте мне знать.

Answer 2

Имеется матрица N X 2, представленная в одномерном массиве, который вы хотите преобразовать в массив 2 X N.

Например, ваш список:

a ₁ , b ₁ , a ₂ , b ₂ , ... a _n, б _н

можно также представить в виде матрицы:

x _1,1 , x _1,2 , x _2,1 , x _2,2 , ... x _{n, 1} , x _{n, 2}

которым вы хотите транспонировать, чтобы стать:

x _1,1 , x _2,1 , ... x _{n, 1} , x _1,2 , x _2,2 , ... x _{n, 2}

Алгоритм транспонирования матрицы на месте выполнит эту работу.

EDIT

Хорошо, позвольте мне объяснить это. Попробуйте следующий фрагмент кода:

i = 0                /* linear array index */
do j = 1 to c        /* j = 1 to virtural columns */
  do k = 1 to r      /* k = 1 to virtural rows */
    i = i + 1
    sp = (k - 1) * c + j
    do while sp < i
      ct = (sp - 1) % r + 1
      rt = sp - (ct - 1) * r
      sp = (rt - 1) * c + ct
    end
    if i \= sp then say 'swap('i',' sp')'   /* swap elements */
  end
end

Это распечатает элементы массива, которые нужно поменять местами. Это будет работать для матрицы любого размера, представленной в линейном массиве, где элементы располагаются по столбцу, а затем по строке. Используя N X 2 martix, элементы будут расположены следующим образом:

x _1,1 , x _1,2 , x _2,1 , x _2,2 , ... х _{н, 1} , х _{н, 2}

Алгоритм распечатывает элементы, которые нужно поменять местами, чтобы получить массив в следующем порядке:

x _1,1 , x _2,1 , ... x _{n, 1} , x _1,2 , x _2,2 , ... x _{n, 2}

Например, начать с r = 4, c = 2 и массива:

 A1, B1, A2, B2, A3, B3, A4, B4

Требуются следующие свопы:

swap(2, 3)
swap(3, 5)
swap(4, 7)
swap(6, 7)

стать:

 A1, A2, A3, A4, B1, B2, B3, B4

Этот алгоритм эффективен как в пространстве, так и во времени.

Big-O

Мой О-фу не велик, но я попробую ...

Матрица содержит 2 столбца («A» и «B») и «M» строк. Чтобы представить это как линейный массив нам нужно 2М элементов. Позволяет назвать это число N (размер линейного массива).

Алгоритм имеет два цикла итерации, один для 'r' (строки) и один для 'c' (столбцы). Тогда общее число итераций равно r * c, которое в нашем случае сводится к 2M = N. Пока все хорошо.

Подстановочный знак - внутренний цикл DO WHILE. Сколько итераций требуется для данного числа строк? Ответ может быть: довольно много. На основании некоторых эмпирических результатов (показанных ниже) это выглядит как число DO WHILE итераций это сложная функция, включающая 'r', когда 'c' = 2 (или, возможно, любое значение 'c'). Мне не хватает O-foo, чтобы точно понять, что это за функция. Тем не менее, он не должен быть хуже, чем N ³ (одна полная «погоня» через матрицу, N ² , раз каждый элемент, N). Не очень хорошая картина - в теории. Итак, я думаю, что это делает O (N ³ )? Это может быть алгоритм не O (N), но с практической точки зрения, кажется, работает близко к O (N), учитывая биты Эмпирические данные приведены ниже. Я немного растерялся - комментарии приветствуются!

Одно замечание о цикле DO WHILE: используется целочисленная математика для простых переменных (без массива ссылки обязательны). Если вы идете нелинейно, это имеет быть «самым дешевым» местом для этого!

Сколько свопов требуется? Количество свопов ограничено одним на итерацию через внешний две петли, что не более N раз. Количество свопов соответствует производительности O (N).

Я предполагаю, что это не O (N) алгоритм, но, похоже, он ведет себя разумно для 2-х колоночных матриц среднего размера.

Вот некоторые эмпирические результаты для различных размеров матрицы из двух столбцов:

      Rows Loops per row
========== =============
       500             9
     1,000            19
     1,500            21
     2,000            12
     2,500            18
     3,000            23
     3,500            26
 1,000,000            30
 2,000,000            40
 3,000,000            45
10,000,000            59
20,000,000            39
30,000,000            60

Число циклов в ряду растет с количеством строк, но не с пугающей скоростью. Опасность заключается в том, чтобы попасть в какое-то «сладкое» место, где оно становится экспоненциальным, но я не знаю, действительно ли у него такой потенциал.

Я бы посоветовал Mgccl сравнить этот алгоритм с диапазоном количества строк, которыеКак правило, в своем приложении он решает, будет ли он приемлемым по сравнению с другими тестами алгоритма.Анализ Big-O интересен, но вот результаты по рабочему диапазону данных.

Последний удар по банке: Почему этот алгоритм работает?

Транспонированиематрица, представленная в линейной форме:

Данная матрица X имеет M строк и N столбцов.

Разложите X в линейный массив в главном порядке строк.Массив будет организован следующим образом:

11, 12, 13, ... 1N, 21, 22, 23, ... 2N, ... M1, M2, M3 ... MN

Обозначение, описывающее каждый элемент в линейном массиве:

    X[i,r,c] 

where: i is the linear array index for element X 
       r is the row number for element X
       c is the column number for element X. 

Используя эту нотацию, можно создать массив в главном порядке строккак:

i = 0
for j = 1 to M    /* Row counter */
  for k = 1 to N  /* Column counter */
    i = i + 1     /* array index of element j, k */
    say 'X['i','j',k']'
  end
end

Обратите внимание, что при заданных значениях j (строка) и k (столбец) i можно рассчитать как:

i = (j - 1) * N + k

Транспонирование матрицы X строится путем обменаэлементы X [i, r, c] с X [t, c, r] в диапазоне r и c.По сути, мы обмениваем все переменные строки на переменные столбца.Используя обозначения, описанные выше, это равносильно замене элементов линейного массива:

    exchange(X[i,r,c], X[t,c,r])

where: i = (r - 1) * N + c
       t = (c - 1) * M + i

Количество обменов, необходимых для транспонирования матрицы, будет меньше, чем M * N, потому что для размещенияэлемент в правильном положении.В некоторых случаях обмен не потребуется, поскольку элемент уже «на месте».Например, первый и последний элементы X никогда не нуждаются в обмене.

Проходя через линейный массив с увеличением i, мы знаем, что пока ни один из обменов не включает элементы, где i> t, матрица будетв главном порядке столбцов для всех элементов, имеющих индексы, меньшие или равные i.

Всякий раз, когда i> t, это означает, что предшествующий обмен имел место в индексе t.Элемент в точке t был заменен, как указано выше, поместив его в новую позицию t '.Учитывая индекс t, мы можем вычислить главный индекс строки t ', а также номера строк и столбцов, связанные с ним, следующим образом:

 c' = (t - 1) % M + 1
 r' = t - (c' - 1) * M
 t' = (r' - 1) * N + c'

Опять же, если t' меньше i, это означает, чтоэтот элемент также был обменен, и мы должны продолжить еще один раунд расчетов.Установите t в вычисленное значение t 'и повторите.В конце концов, я стану <= t, и обмен может быть сделан.По сути, мы «преследуем» элемент через все его предыдущие обмены, пока не найдем его в i или справа от i в линейном массиве. </p>

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

Answer 3

O (1) Время, O (1) Дополнительное пространство

#include <vector>
#include <iostream>
#include <ctime>
#include <boost/random.hpp>

template <typename T>
class pvec
{
private:
    // Stores values to permute
    std::vector<T> v;

    // Flag; true when permuted; false when not
    bool permuted;

public:
    pvec(size_t size) : v(size), permuted(false) {}

    // Set the permutation flag
    void set_p(bool p) { permuted = p; }

    // When the permuted flag is set, return the permuted element, otherwise
    // return the non-permuted element
    T& operator[](size_t i) { return (permuted ? v[p_ind(i)] : v[i]); }

    // Pass through the size of the vector used
    size_t size() const { return v.size(); }

private:
    // Used to determine the permuted index of a given index
    size_t p_ind(size_t i) const
    {
        return ( i < v.size()/2 ? i * 2 : 2 * (i - v.size()/2) + 1);
    }
};

// Used to display a pvec instance
template <typename T>
std::ostream& operator<<(std::ostream& os, pvec<T>& v)
{
    for (size_t i = 0; i < v.size(); ++i)
        os << (i == 0 ? "<" : ", ") << i << ":" << v[i];
    os << ">";
    return os;
}

int main(int argc, char** argv)
{
    const size_t size = 8;
    pvec<uint32_t> v(size);  // Array containing test values

    // Boost Random Number Library used to generate random values in the test
    // array
    boost::mt19937 rng(std::time(0));
    boost::uniform_int<> dist(0,65536);
    boost::variate_generator<boost::mt19937&, boost::uniform_int<> >
        var(rng, dist);

    // Generate random test values
    for (size_t i = 0; i < size; ++i)
        v[i] = var();

    // Observer original vector
    std::cout << v << std::endl;

    // Set the permutation flag O(1) time
    v.set_p(true);

    // Observe the permuted vector
    std::cout << v << std::endl;

    return 0;
}

Выход:

<0:44961, 1:246, 2:54618, 3:41468, 4:12646, 5:21691, 6:26697, 7:36409>
<0:44961, 1:54618, 2:12646, 3:26697, 4:246, 5:41468, 6:21691, 7:36409>

Answer 4

Хорошо, давайте посмотрим на этот пример:

0 1 2 3 4 5 6 7 8 9 10

0 2 4 6 8 10 1 3 5 7 9

Первая половина результата содержит элементы, индексы которых равны i / 2 исходного индекса i, а вторая половина - i - n / 2 + 1, где n - количество элементов в массиве.

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

Так что здесь есть идея использовать алгоритм сортировки пузырьков для сортировки массива целых чисел.Нам нужно вывести четные значения в начало, оставив нечетные значения позади:

0 1 2 3 4 5 6 7 8 9 10
  * *
0 2 1 3 4 5 6 7 8 9 10
      * *
0 2 1 4 3 5 6 7 8 9 10
    * *
0 2 4 1 3 5 6 7 8 9 10
          * *
0 2 4 1 3 6 5 7 8 9 10
        * *
...
0 2 4 6 1 3 5 7 8 9 10
              * *
...
0 2 4 6 8 1 3 5 7 9 10
                  * *

Это будет работать только в том случае, если вы можете сохранить индексы (т.е. в этом случае индексы коррелируют со значениями массива).Производительность пузырьковой сортировки - O (n ^ 2), а использование памяти - 1.

Этого нельзя достичь за время O (n) и 1 память [РЕДАКТИРОВАТЬ: используя только общие алгоритмы сортировки!], Лучшие универсальные алгоритмы сортировкивыполнить в O (nlog n):

http://en.wikipedia.org/wiki/Sorting_algorithm

Чтобы решить вашу проблему, лучшим способом было бы создать массив индексов, соответствующих вашему критерию:

size_t* indices = new size_t[n]; 

// n is the number of items in the original array
for (int i = 0; i < n; i++)
{
    if (i < n / 2)
    {
       indices[i] = i * 2;
    }
    else
    {
       indices[i] = i - n / 2 + 1;
    }
}

, а затем просто используйте его для сопоставления элементов в исходном массиве с новыми позициями:

// i is the new index here, which makes it appear as if ValuesArray has been sorted
Type* getOddEvenValue(size_t newIndex)
{
     // ValuesArray and indices should be available in this scope, of course
     return ValuesArray[indices[newIndex]];
}

Эта вещь будет работать в O (n), но также потребует O (n) памяти.Но если sizeof Type намного больше, чем sizeof, он все равно выигрывает в использовании памяти (в отличие от копирования объектов Type).

[EDIT2:]

Вместо красивого ООПКод andand сделал, что также требует от вас скопировать исходный вектор в экземпляр вашего класса, вы можете просто написать функцию:

 size_t permuted_index(size_t i, size_t vecSize)
 {
    return ( i < vecSize/2 ? i * 2 : 2 * (i - vecSize/2) + 1);
 }

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