Подтвердить что ты не робот

Как переставить массив по массиву индексов?

Учитывая массив arr и массив индексов ind, я бы хотел перестроить arr на месте, чтобы удовлетворить заданным индексам. Например:

var arr = ["A", "B", "C", "D", "E", "F"];
var ind = [4, 0, 5, 2, 1, 3];

rearrange(arr, ind);

console.log(arr); // => ["B", "E", "D", "F", "A", "C"]

Вот возможное решение, которое использует O(n) время и O(1) пробел, , но мутирует ind:

function swap(arr, i, k) {
  var temp = arr[i];
  arr[i] = arr[k];
  arr[k] = temp;
}

function rearrange(arr, ind) {
  for (var i = 0, len = arr.length; i < len; i++) {
    if (ind[i] !== i) {
      swap(arr, i, ind[i]);
      swap(ind, i, ind[i]);
    }
  }
}

Каким будет оптимальное решение , если мы ограничены пробелом O(1), а мутация ind не разрешена?

Изменить: Неправильный алгоритм. См. этот вопрос.

4b9b3361

ОТВЕТЫ

Ответ 1

Это решение "знакового бита".

Учитывая, что это вопрос JavaScript, и числовые литералы, указанные в массиве ind, поэтому сохраняются как подписанные поплавки, в пробеле, используемом входом, есть знаковый бит.

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

Массив ind изменяется во время выполнения, но будет восстановлен до его оригинала по завершении алгоритма. В одном из комментариев вы упомянули, что это приемлемо.

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

Изменить: Я заменил использование оператора ~, так как он не дает желаемых результатов для чисел, равных или больше 2 31 а JavaScript должен номера поддержки, которые будут использоваться как индексы массивов, по крайней мере, до 2 32 - 1. Поэтому вместо этого теперь я использую k = -k-1, что то же самое, но работает для всего диапазона поплавков, который безопасен для использования в качестве целых чисел. Обратите внимание, что в качестве альтернативы можно использовать бит дробной части с плавающей запятой (+/- 0,5).

Вот код:

var arr = ["A", "B", "C", "D", "E", "F"];
var ind = [4, 0, 5, 2, 1, 3];

rearrange(arr, ind);

console.log('arr: ' + arr);
console.log('ind: ' + ind);

function rearrange(arr, ind) {
    var i, j, buf, temp;
    
    for (j = 0; j < ind.length; j++) {
        if (ind[j] >= 0) { // Found a cycle to resolve
            i = ind[j];
            buf = arr[j];
            while (i !== j) { // Not yet back at start of cycle
                // Swap buffer with element content
                temp = buf;
                buf = arr[i];
                arr[i] = temp;
                // Invert bits, making it negative, to mark as visited
                ind[i] = -ind[i]-1; 
                // Visit next element in cycle
                i = -ind[i]-1;
            }
            // dump buffer into final (=first) element of cycle
            arr[j] = buf;
        } else {
            ind[j] = -ind[j]-1; // restore
        }
    }
}

Ответ 2

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

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

function rearrange(values, indexes) {
    main_loop:
    for (var start = 0, len = indexes.length; start < len; start++) {
        var next = indexes[start];
        for (; next != start; next = indexes[next])
            if (next < start) continue main_loop;

        next = start;
        var tmp = values[start];
        do {
            next = indexes[next];
            tmp = [values[next], values[next] = tmp][0]; // swap
        } while (next != start);
    }
    return values;
}

Этот алгоритм перезаписывает каждый элемент заданного массива ровно один раз, не мутирует массив индексов (даже временно). Его наихудшая сложность - O (n 2). Но для случайных перестановок его ожидаемая сложность - O (n log n) (как указано в комментариях к связанному ответу).

Этот алгоритм может быть оптимизирован немного. Наиболее очевидной оптимизацией является использование короткого битового набора для хранения информации о нескольких индексах перед текущей позицией (независимо от того, были ли они уже обработаны или нет). Использование одного 32-разрядного или 64-битного слова для реализации этого битового набора не должно нарушать требования к пространству O (1). Такая оптимизация даст небольшое, но заметное улучшение скорости. Хотя это не меняет худшего случая и ожидаемых асимптотических сложностей.

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

Тем не менее массив индексов может дать нам некоторое пространство (намного большее, чем одно слово) для битрейта. Поскольку этот массив определяет перестановку, он содержит гораздо меньше информации, чем произвольный массив того же размера. Приближение Стирлинга для ln(n!) дает n ln n бит информации, в то время как массив может хранить бит n log n. Различие между естественным и двоичным логарифмами дает нам около 30% потенциального свободного пространства. Кроме того, мы могли бы извлечь до 1/64 = 1,5% или 1/32 = 3% свободного пространства, если размер массива не является степенью двух, или, другими словами, если бит высокого порядка используется только частично, (И эти 1,5% могут быть гораздо более ценными, чем гарантированные 30%).

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

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

Недостатком этого метода является то, что большая часть свободного пространства создается, когда алгоритм приходит к концу массива, в то время как это пространство в основном требуется, когда мы находимся в начале. В результате сложность наихудшего случая, вероятно, будет лишь немного меньше, чем O (n 2). Это может также увеличить ожидаемую сложность, если не этот простой трюк: используйте оригинальный алгоритм (без сжатия), в то время как он достаточно дешев, затем переключитесь на "сжатый" вариант.

Если длина массива не равна 2 (и у нас частично неиспользуемый бит высокого порядка), мы могли бы просто игнорировать тот факт, что индексный массив содержит перестановку и упаковывает все индексы, как если бы в base- n числовая система. Это позволяет значительно уменьшить асимптотическую сложность наихудшего случая, а также ускорить алгоритм в "среднем случае".

Ответ 3

В этом предложении используется ответ Евгения Клуева.

Я сделал расширение для более быстрой обработки, если все элементы уже обработаны, но индекс не достиг нуля. Это делается с дополнительной переменной count, которая учитывается для каждого замененного элемента. Это используется для выхода из основного цикла, если все элементы находятся в правильном положении (count = 0).

Это полезно для колец, как в первом примере с

["A", "B", "C", "D", "E", "F"]
[ 4,   0,   5,   2,   1,   3 ]

index 5: 3 -> 2 -> 5 -> 3
index 4: 1 -> 0 -> 4 -> 1

Оба кольца сначала переставляются двумя петлями, и в то время как каждое кольцо имеет 3 элемента, count теперь равно нулю. Это приводит к короткому замыканию для внешнего цикла while.

function rearrange(values, indices) {
    var count = indices.length, index = count, next;

    main: while (count && index--) {
        next = index;
        do {
            next = indices[next];
            if (next > index) continue main;
        } while (next !== index)
        do {
            next = indices[next];
            count--;
            values[index] = [values[next], values[next] = values[index]][0];
        } while (next !== index)
    }
}

function go(values, indices) {
    rearrange(values, indices);
    console.log(values);
}

go(["A", "B", "C", "D", "E", "F"], [4, 0, 5, 2, 1, 3]);
go(["A", "B", "C", "D", "E", "F"], [1, 2, 0, 4, 5, 3]);
go(["A", "B", "C", "D", "E", "F"], [5, 0, 1, 2, 3, 4]);
go(["A", "B", "C", "D", "E", "F"], [0, 1, 3, 2, 4, 5]);

Ответ 4

Этот ответ был обновлен для соответствия условиям OP

В этом ответе нет массивов temp, а массив ind не может быть перенаправлен или отсортирован любым способом. Все операции замены выполняются за один проход. Функция getItemIndex получает только малую часть массива ind для работы. Это просто сделано путем использования всей информации, скрытой в массиве ind.

Это ключ к пониманию того, что массив ind хранит всю историю для нас.

У нас есть следующая информация, исследуя массив ind.

  • При просмотре элементов мы находим карту-указатель соответствующего элемента в массиве arr.
  • Каждый индекс товаров указывает нам, сколько проверок было сделано раньше. Мы получаем историю.
  • Индекс каждой позиции также указывает, существовал ли предыдущий своп, связанный с текущей позицией индекса, в которой находился предыдущий элемент. Мы можем сделать как ind.indexOf(i); В любом случае вот код:

Я добавил несколько функций, таких как Array.prototype.swap(), чтобы облегчить интерпретацию кода. Вот код.

Array.prototype.swap = function(i,j){
  [this[i],this[j]] = [this[j],this[i]];
  return this;
};

function getItemIndex(a,i){
  var f = a.indexOf(i);
  return f !=-1 ? getItemIndex(a,f) : i;
}

function sort(arr,ind){
  ind.forEach((n,i,x) => x.indexOf(i) > i ? arr.swap(i,x[i]) // item has not changed before so we can swap 
                                          : arr.swap(getItemIndex(ind.slice(0,i),i),x[i])); // item has gone to somwhere in previous swaps get it index and swap
  return arr;
}

var arr = ["A", "B", "C", "D", "E", "F"],
    ind = [4, 0, 5, 2, 1, 3];


console.log(sort(arr,ind),ind);

Ответ 5

var arr = ["A", "B", "C", "D", "E", "F"];
var ind = [4, 0, 5, 2, 1, 3];

function rearrange(arr, ind){
  var map = [];
  for (var i = 0; i < arr.length; i++)   map[ind[i]] = arr[i];
  for (var i = 0; i < arr.length; i++)   arr[i] = map[i];
}

rearrange(arr, ind);

console.log(arr);

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

Ответ 6

Ниже можно найти решение PARTIAL для случая, когда у нас есть только ОДИН цикл, т.е.

var arr = ["A", "B", "C", "D", "E", "F"];
var ind = [4, 2, 5, 0, 1, 3];

function rearrange( i, arr, ind, temp ){
    if( temp ){
        if( arr[ind[i]] ){
            var temp2 = arr[ind[i]];
            arr[ind[i]] = temp;
            rearrange( ind[i], arr, ind, temp2 );
        }
        else{                                           // cycle
            arr[ind[i]] = temp;
            // var unvisited_index = ...;
            // if( unvisited_index ) rearrange( unvisited_index, arr, ind, "" );
        }
    }
    else{
        if( i == ind[i] ){
            if( i < arr.length ) rearrange( i + 1, arr, ind, temp );    
        }
        else{
            temp = arr[ind[i]];
            arr[ind[i]]=arr[i];
            arr[i] = "";
            i = ind[i];
            rearrange(i, arr, ind, temp );
        }
    }
}

rearrange( 0, arr, ind, "" );

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

Для примера OP:

var arr = ["A", "B", "C", "D", "E", "F"];
var ind = [4, 0, 5, 2, 1, 3];

Существует два уникальных цикла:

4 -> 1 -> 0 -> 4
5 -> 3 -> 2 -> 5

Если вы запустите

rearrange( 0, arr, ind, "" );
rearrange( 5, arr, ind, "" );

S (he) получит желаемый результат для проблемы OP.

Ответ 7

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

var arr = ["A", "B", "C", "D", "E", "F"];
var ind = [4, 0, 5, 2, 1, 3];

arr = ind.map(function(value)
{ return arr[value]; });

Другое решение, не использующее функцию карты, может выглядеть примерно так:

var arr = ["A", "B", "C", "D", "E", "F"];
var ind = [4, 0, 5, 2, 1, 3];

var temp = [];

for (var i = 0, ind_length = ind.length; i < ind_length; i++) 
{ 
    var set_index = ind[i];
    temp.push(arr[set_index]); 
    delete arr[set_index]; 
}

arr = temp;

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

Ответ 8

Попробуйте следующее:

var result = new Array(5);
for (int i = 0; i < result.length; i++) {
    result[i] = arr[ind[i]];
}
console.log(arr);

Ответ 9

Я использую ind как индексы в своем собственном порядке

var arr = ["A", "B", "C", "D", "E", "F"];
var ind = [4, 0, 5, 2, 1, 3];
var obj = {}
for(var i=0;i<arr.length;i++)
    obj[ind[i]]=arr[i];
console.log(obj);

Рабочая скрипта