Как применить перестановку с повторяющимися значениями к другому

Question

Рассмотрим алгоритм:

apply(src, perm) {
    result = []

    for (i; i < perm.length; i++) {
        result.push(src[perm[i]);
    }

    return result;
}

Передав src = [0,1,2,3] и perm = [3,0,1,2], мы получим на каждой итерации:

result -> 3
result -> 3 0
result -> 3 0 1
result -> 3 0 1 2

, если мы вызовем apply с этим результат типа apply(result, perm), мы получаем:

result -> 2 
result -> 2 3
result -> 2 3 0
result -> 2 3 0 1

И так далее. Обратите внимание, что если мы выполним это время длины массивов, оно станет исходным.

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

- applying the perm (2 0 [1 1]) in src (0 [1 1] 2) should result in (2 0 [1 1]);
- applying the perm (2 0 [1 1]) in src (2 0 [1 1]) should result in (1] 0 2 [1);
- applying the perm (2 0 [1 1]) in src (1] 0 2 [1) should result in ([1 1] 0 2);
- ...

Я уменьшил количество элементов в массивах, чтобы улучшить примеры, но на самом деле длина входных данных будет 12 (0 1 1 2 3 3 4 5 5 6 7 7 ). Кроме того, это не просто циклическое вращение c; если перманент будет другим, я думаю, что результаты будут работать по-другому. Кроме того, всегда повторяющиеся значения будут только числа odd и even являются одинарными.

Я пытался написать функцию, которая пытается проверить что-то вроде, если текущее значение нечетное или четное, если нечетные толчки следующее:

function apply(src, perm){
    res = [];
    last = 0;
    for (i = 0; i < perm.length; i++){
        if (src[perm[i]] % 2 === 0 && src[perm[i]] !== last){
            res.push(src[perm[i]]);
            last = src[perm[i]];
        } else if (src[perm[i]] % 2 === 0 && src[perm[i]] === last) {
            res.push(src[perm[i] + 1]);
            last = src[perm[i] + 1];
        } else {
            if (src[perm[i] + 1] !== undefined){ //out of bounds
                res.push(src[perm[i] + 1]);
                last = src[perm[i] + 1];
            }
        }
    }
    return res;
}

Здесь go некоторые примеры входов и ожидаемых результатов:

base formula (no repetitions): result[i] = src[perm[i]]

Example 1:
src:    [4 1 1 2 5 5 0 3 3 6 7 7];
perm:   [4 1 1 6 3 3 0 5 5 2 7 7];
result: [0 1 1 6 5 5 4 3 3 2 7 7];

Example 2:
src:    [6 1 1 0 3 3 4 5 5 2 7 7];
perm:   [2 1 1 6 3 3 4 5 5 0 7 7];
result: [0 1 1 2 3 3 4 5 5 6 7 7];

Example 3:
src:    [0 1 1 2 3 3 6 5 5 4 7 7];
perm:   [2 3 3 4 5 5 6 7 7 0 1 1];
result: [2 3 3 6 5 5 4 7 7 0 1 1];

Example 4:
src:    [2 1 1 6 5 5 4 3 3 0 7 7];
perm:   [1 1 2 3 3 4 5 5 6 7 7 0];
result: [1 1 6 5 5 4 5 5 0 7 7 2];

Example 5:
src:    [6 7 7 0 1 1 4 5 5 2 3 3];
perm:   [3 3 4 5 5 6 7 7 0 1 1 2];
result: [1 1 4 5 5 2 3 3 6 7 7 0];

В любом случае, это не работает. Я надеюсь, что вопрос был ясен, если нет, не стесняйтесь спрашивать. Заранее спасибо.

Answer 1

Это имеет смысл:

perm (2 0 [1 1]) in src (0 [1 1] 2) result is (2 0 [1 1])

Но с этого момента больше не имеет смысла:

perm (2 0 [1 1]) in src (2 0 [1 1]) result is (1] 0 2 [1)

Давайте посмотрим: сначала вы берете элемент 2 = [1 1] или 1, затем элемент 0 = 2, затем элемент [1 1] = 0 или 0, 0. Результат никогда не будет [1 0 2 1]

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

perm (2 0 1) in src (0 [1 1] 2) result is (2 0 [1 1])
perm (2 0 1) in src (2 0 [1 1]) result is ([1 1] 2 0)
perm (2 0 1) in src ([1 1] 2 0) result is (0 [1 1] 2)

Что также дает вам циклический c свойство.

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

ОБНОВЛЕНИЕ: Если в вашей перми есть повторения, также удалите их перед Запуск алгоритма.

function removeDuplicates(arr) { // Assumes duplicates are in order
  var result = [], prev = null;
  for (var el of arr) {
    if (el != prev) result.push(el);
    prev = el;
  }
  return result;
}

function apply(src, perm) {
  var result = [], prev = null;
  var src2 = removeDuplicates(src);
  for (var i of perm) {
    if (i != prev) { // Ignore duplicates
      var el = src2[i];
      result.push(el);
      if (el % 2 != 0) result.push(el); // duplicate odds
    }
    prev = i;
  }
  console.log(`src = [${src}] perm = [${perm}] result = [${result}]`);
}

apply([0, 1, 1, 2], [2, 0, 1]);
apply([2, 0, 1, 1], [2, 0, 1]);
apply([1, 1, 2, 0], [2, 0, 1]);

apply([4, 1, 1, 2, 5, 5, 0, 3, 3, 6, 7, 7], [4, 1, 1, 6, 3, 3, 0, 5, 5, 2, 7, 7]);
apply([6, 1, 1, 0, 3, 3, 4, 5, 5, 2, 7, 7], [2, 1, 1, 6, 3, 3, 4, 5, 5, 0, 7, 7]);
apply([0, 1, 1, 2, 3, 3, 6, 5, 5, 4, 7, 7], [2, 3, 3, 4, 5, 5, 6, 7, 7, 0, 1, 1]);
apply([2, 1, 1, 6, 5, 5, 4, 3, 3, 0, 7, 7], [1, 1, 2, 3, 3, 4, 5, 5, 6, 7, 7, 0]);
apply([6, 7, 7, 0, 1, 1, 4, 5, 5, 2, 3, 3], [3, 3, 4, 5, 5, 6, 7, 7, 0, 1, 1, 2]);