Как освоить алгоритмы модификации массивов на месте?

Question

Я готовлюсь к собеседованию по программному обеспечению, и у меня возникают проблемы с модификациями массивов на месте. Например, в задаче out-shuffle вы чередуете две половины массива, так что 1 2 3 4 5 6 7 8 станет 1 5 2 6 3 7 4 8. Этот вопрос требует постоянной решение (и линейное время, хотя я не уверен, что это даже возможно).

Сначала я думал, что линейный алгоритм тривиален, но потом я не смог его решить. Затем я нашел простой O(n^2) алгоритм, но это заняло у меня много времени. И я до сих пор не могу найти более быстрое решение.

Я также помню, как испытывал затруднения при решении аналогичной проблемы из Bentley's Programming Pearls, колонка 2: вращать массив, оставленный позициями i (например, abcde, повернутый на 2, становится cdeab), за время O(n) и только с парой байтов пространство.

У кого-нибудь есть советы, которые помогут мне решить такие проблемы? Существуют ли специальные учебники по таким вопросам? Спасибо!

Answer 1

О времени O (n), O (1) пробел для O-Shuffle

---

Выполнение O-Shuffle в O (n) время и O (1) пространство возможно, но оно жесткое .Не уверен, почему люди думают, что это легко, и предлагают вам попробовать что-то еще.

В следующей статье есть решение O (n) времени и пространства O (1) (хотя это и для случайных комбинаций, но выполнение таких операций делаетперестановка тривиальная):

http://arxiv.org/PS_cache/arxiv/pdf/0805/0805.1598v1.pdf

О методе работы с алгоритмами модификации массивов на месте

---

Алгоритмы модификации на месте могут стать очень сложными для обработки.

Рассмотрим пару:

• Внесение-тасование в линейное время.Использует теорию чисел.
• Сортировка на месте слияния была открыта в течение нескольких лет.Пришел алгоритм, но он был слишком сложным, чтобы быть практичным.Использует очень сложную бухгалтерию.

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

Тем не менее, для модификаций массивов, которые приводят к перестановке Из исходного массива вы можете попробовать метод following the cycles of the permutation.По существу, любая перестановка может быть записана как непересекающийся набор циклов (см. Также ответ Джона).Например, перестановку:

1 4 2 5 3 6

из 1 2 3 4 5 6 можно записать как

1 -> 1
2 -> 3 -> 5 -> 4 -> 2
6 -> 6.

, стрелку можно прочитать как «идет».

перестановка массива 1 2 3 4 5 6 выполняется три цикла:

1 переходит на 1.

6 переходит на 6.

2 переходит на 3, 3 переходит на 5,5 переходит к 4, а 4 переходит к 2.

Чтобы следовать этому длинному циклу, вы можете использовать только одну временную переменную.Храните 3 в нем.Поставь 2 где 3 было.Теперь поместите 3 в 5 и сохраните 5 в темп и так далее.Поскольку вы используете только постоянное дополнительное временное пространство для следования определенному циклу, вы делаете модификацию массива для этого цикла на месте.

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

Разумный выбор начальных точек циклов может упростить алгоритм.Если вы пришли к начальным точкам в пространстве O (1), теперь у вас есть полный алгоритм на месте.Здесь вам, возможно, придется познакомиться с проблемой и использовать ее свойства.

Даже если вы не знали, как вычислить начальные точки циклов, но имели формулу для вычисления следующего элементаВы можете использовать этот метод, чтобы получить O (n) время на месте алгоритм в некоторых особых случаях.

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

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

Вы получаете O (n) время и O (1) пространство алгоритм!Конечно, мы вроде «обманули», используя знаковые биты целых чисел массива в качестве нашего личного «посещенного» растрового изображения.

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

• The inshuffle (or out-shuffle) problem: Когда 2n + 1 - это степень 3, можно показать (используя теорию чисел), что 1,3,3 ^ 2 и т. Д. Находятся в разных циклах, и все циклы охватываются с использованием этих , Объедините это с тем фактом, что перетасовка восприимчива к разделению и завоеванию, вы получаете O (n) время, O (1) пространственный алгоритм (формула i -> 2 * i по модулю 2n + 1). Для получения более подробной информации см. Вышеупомянутый документ.

• The cyclic shift an array problem: циклическое смещение массива размера n на k также дает перестановку результирующего массива (задается формулой i, переходящей в i + k по модулю n), и также может быть решена за линейное время и на месте, используя следующий метод цикла. Фактически, с точки зрения количества обменов элементов этот следующий метод цикла лучше , чем алгоритм 3 обращений. Конечно, следование циклическому методу может привести к уничтожению кэша из-за шаблонов доступа, и на практике алгоритм 3 обращений может на самом деле лучше.

---

Что касается интервью, если интервьюер - разумный человек, они будут смотреть на то, как вы думаете и подходите к проблеме, а не к тому, решаете ли вы ее на самом деле. Поэтому, даже если вы не решите проблему, я думаю, вам не следует разочаровываться.

Answer 2

Основная стратегия с использованием алгоритмов на месте состоит в том, чтобы выяснить правило перемещения записи из слота N в слот M.

Итак, ваш случай, например. если A и B - карты, а N - количество карт. правила для первой половины колоды отличаются от правил для второй половины колоды

 // A is the current location, B is the new location.
 // this math assumes that the first card is card 0
 if (A < N/2)
    B = A * 2;
 else
    B = (A - N/2) * 2 + 1;

Теперь мы знаем правило, нам просто нужно переместить каждую карту, каждый раз, когда мы перемещаем карту, мы вычисляем новое местоположение, затем удаляем карту, которая в настоящее время находится в B. место A в слоте B, затем пусть B будет A, и вернитесь к началу алгоритма. Каждая перемещенная карта заменяет новую карту, которая становится следующей перемещаемой картой.

Я думаю, что анализ легче, если мы основаны на 0, а не на 1, поэтому

 0 1 2 3 4 5 6 7  // before
 0 4 1 5 2 6 3 7  // after

Итак, мы хотим переместить 1-> 2 2-> 4 4-> 1, и это завершает цикл затем переместите 3-> 6 6-> 5 5-> 3, и это завершает цикл и мы сделали.

Теперь мы знаем, что карта 0 и карта N-1 не двигаются, поэтому мы можем игнорировать их, так что мы знаем, что нам нужно всего лишь поменять карты N-2. Единственный липкий бит является то, что есть 2 цикла, 1,2,4,1 и 3,6,5,3. когда мы дойдем до карты 1 во второй раз нам нужно перейти к карточке 3.

 int A = 1;
 int N = 8;
 card ary[N]; // Our array of cards
 card a = ary[A];

 for (int i = 0; i < N/2; ++i)
 {
     if (A < N/2)
        B = A * 2;
     else
        B = (A - N/2) * 2 + 1;

     card b = ary[B];
     ary[B] = a;
     a = b;
     A = B;

     if (A == 1)
     {
        A = 3;
        a = ary[A];
     }
 }   

Теперь этот код работает только для 8-карточного примера, из-за этого теста if, который перемещает нас от 1 до 3, когда мы заканчиваем первый цикл. Что нам действительно нужно, так это общее правило для распознавания конца цикла и того, куда идти, чтобы начать следующий.

Это правило может быть математическим, если вы можете придумать способ, или вы могли бы отслеживать, какие места вы посетили в отдельном массиве, и когда A возвращается в посещенное место, вы можете затем сканировать вперед в вашем массиве ищу первое не посещаемое место.

Чтобы ваш алгоритм на месте был 0 (n), решение должно быть математическим.

Я надеюсь, что это нарушение процесса мышления будет полезным для вас. Если бы я брал у тебя интервью, я бы ожидал увидеть что-то подобное на доске.

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

Answer 3

Дополняет Ответ Арябхатты :

Существует общий способ «следить за циклами», даже не зная начальных позиций для каждого цикла или используя память, чтобы знать посещенные циклы. Это особенно полезно, если вам нужно O (1) памяти.

Для каждой позиции i в массиве следуйте циклу, пока не перемещая никаких данных, пока не достигнете ...

• начальная позиция i: конец cyle. это новый цикл: следуйте за ним снова, перемещая данные на этот раз.
• позиция ниже, чем я: этот цикл уже посещен, ничего общего с ним.

Конечно, это накладные расходы времени (я полагаю, O (n ^ 2)) и проблемы с кешем общего метода "следующих циклов".

Answer 4

Франк,

Для программирования с помощью циклов и массивов ничто не сравнится с учебником Дэвида Гриса Наука программирования . Я изучал его более 20 лет назад, и есть идеи, которые я использую каждый день. Это очень математично и потребует реальных усилий для освоения, но это усилие многократно окупит вас за всю вашу карьеру.

Answer 5

Для первого предположим, что n четно. У вас есть:

первая половина: 1 2 3 4
второй: 5 6 7 8

Пусть x1 = первый [1], x2 = второй [1].

Теперь вы должны напечатать одну из первой половины, одну из второй, одну из первой, одну из второй ...

Значение first [1], second [1], first [2], second [2], ...
Очевидно, вы не храните две половины в памяти, так как это будет O (n) памяти. Вы держите указатели на две половины. Вы видите, как вы это сделаете?

Второй немного сложнее. Рассмотрим:
12345
abcde
..cde
.....ab
..cdeab
cdeab

Вы заметили что-нибудь? Вы должны заметить, что в основном вопрос просит вас переместить первые символы i в конец вашей строки, не предоставляя роскоши копировать последние n - i в буфер, затем добавлять первый i и затем возвращать буфер. Вам нужно сделать с O (1) память.

Чтобы понять, как это сделать, вам, в основном, нужно много практиковаться с такими проблемами, как и со всем остальным. Практика делает идеальным в основном. Если вы никогда раньше не сталкивались с подобными проблемами, вряд ли вы это поймете. Если да, то вам нужно подумать о том, как вы можете манипулировать подстроками и / или индексами так, чтобы вы решали свою проблему при данных ограничениях. Общее правило заключается в том, чтобы работать как можно больше и учиться как можно больше, чтобы вы могли быстро находить решения этих проблем, когда видите их, но решение довольно сильно отличается от проблемы к проблеме. Боюсь, нет четкого рецепта успеха. Просто прочитайте много и поймите материал, который вы прочитали, прежде чем двигаться дальше.

Логика для второй проблемы заключается в следующем: что произойдет, если мы перевернем подстроку [1, 2], подстроку [3, 5], а затем объединим их и перевернем это? У нас в общем:

1, 2, 3, 4, ..., i, i + 1, i + 2, ..., N
реверс [1, i] =>
i, i - 1, ..., 4, 3, 2, 1, i + 1, i + 2, ..., N
реверс [i + 1, N] =>
i, i - 1, ..., 4, 3, 2, 1, N, ..., i + 1
реверс [1, N] =>
i + 1, ..., N, 1, 2, 3, 4, ..., i - 1, i
, что вы и хотели. Запись обратной функции с использованием памяти O (1) должна быть тривиальной.

Answer 6

Общий подход может быть следующим:

1. Создает массив позиций int [] pos , так что pos [i] относится к позиции (индексу) a [i ] в перетасованном массиве.

2. Перегруппировать исходный массив int [] a , в соответствии с этим массивом позиций pos .

   /** Shuffle the array a. */    
   void shuffle(int[] a) {
       // Step 1
       int [] pos = contructRearrangementArray(a)
       // Step 2
       rearrange(a, pos);
   }
   
   /**
    * Rearrange the given array a according to the positions array pos.
    */
   private static void rearrange(int[] a, int[] pos)
   {
       //  By definition 'pos' should not contain any duplicates, otherwise rearrange() can run forever.
      // Do the above sanity check.
       for (int i = 0; i < pos.length; i++) {
           while (i != pos[i]) {
               // This while loop completes one cycle in the array
               swap(a, i, pos[i]);
               swap(pos, i, pos[i]);
           }
       }
   }
   
   /** Swap ith element in a with jth element. */
   public static void swap(int[] a, int i, int j) 
   {
       int temp = a[i];
       a[i] = a[j];
       a[j] = temp;
   }
   

В качестве примера, для случая outShuffle следующим будет реализация contructRearrangementArray ().

/**
 * array     : 1 2 3 4 5 6 7 8
 * pos       : 0 2 4 6 1 3 5 7
 * outshuffle: 1 5 2 6 3 7 4 8 (outer boundaries remain same)
 */
public int[] contructRearrangementArray(int[] a)
{
    if (a.length % 2 != 0) {
        throw new IllegalArgumentException("Cannot outshuffle odd sized array");
    }
    int[] pos = new int[a.length];
    for (int i = 0; i < pos.length; i++) {
        pos[i] = i * 2 % (pos.length - 1);
    }
    pos[a.length - 1] = a.length - 1;
    return pos;
}

Answer 7

Вообще говоря, идея состоит в том, чтобы пройти через массив один раз, в то время как

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