Как рассчитать сдвиг?

Булевое значение функция возвращает правильно, но как отобразить сдвиги (перемещения) правил? При этом нужно не учитывать промежуточные перемещения — в этом и заключается сложность. Пример и ожидаемые результаты: <br/> <a href="https://jsbin.com/hocefifiva/2/edit?html,js,console,output" rel="nofollow">https://jsbin.com/hocefifiva/2/edit?html,js,consol...</a> <br/> <pre><code>console.log(shouldShowRevert(draftList[0], draftList, appliedList)); // EXPECTED false
  • 30 марта 2026 г. 9:01
Ответы на вопрос 1
Ниже — две рабочие идеи и готовый код на JS. Какая из них нужна — зависит от того, что вы понимаете под «не учитывать промежуточные перемещения».

1) Простая и логичная интерпретация: показывать только итоговый (net) сдвиг по сравнению с применённым состоянием. То есть для каждого правила берём его индекс в appliedList и индекс в draftList, разница — это сдвиг. «Промежуточные перемещения» автоматически игнорируются, потому что учитывается только начальная и конечная позиция.

2) Более «интеллигентный» вариант: сначала ищем набор якорей — элементы, которые сохранили относительный порядок (LCS — longest common subsequence). Этия «якоря» считаем неизменными. Элементы между якорями считаем как блоки, и считаем сдвиг внутри блока относительно якоря (то позволяет игнорировать перестановки внутри других блоков, которые в итоге вернулись на место).

Примеры реализаций.

A) Net shift (простой, обычно достаточен)
```js
// draftList и appliedList — массивы объектов с уникальным id
function computeNetShifts(draftList, appliedList, idKey = 'id') {
  const origIndex = new Map();
  appliedList.forEach((it, i) => origIndex.set(it[idKey], i));
  return draftList.map((it, currentIndex) => {
    const orig = origIndex.get(it[idKey]);
    const shift = (typeof orig === 'number') ? currentIndex - orig : null; // null — новый элемент
    return Object.assign({}, it, { shift });
  });
}
```
Пример: если правило было на позиции 3 в appliedList, а в draftList стало на 1 => shift = 1 - 3 = -2 (сдвинулось вверх на 2).

B) Shift относительно якорей (игнорируем «временные» перестановки за пределами блока)
```js
// Возвращает массив id-ов, составляющих LCS между appliedIds и draftIds
function lcs(appliedIds, draftIds) {
  const n = appliedIds.length, m = draftIds.length;
  const dp = Array.from({length: n+1}, () => Array(m+1).fill(0));
  for (let i = n-1; i >= 0; i--) {
    for (let j = m-1; j >= 0; j--) {
      if (appliedIds[i] === draftIds[j]) dp[i][j] = 1 + dp[i+1][j+1];
      else dp[i][j] = Math.max(dp[i+1][j], dp[i][j+1]);
    }
  }
  // восстановим саму последовательность
  const res = [];
  let i = 0, j = 0;
  while (i < n && j < m) {
    if (appliedIds[i] === draftIds[j]) { res.push(appliedIds[i]); i++; j++; }
    else if (dp[i+1][j] >= dp[i][j+1]) i++;
    else j++;
  }
  return res;
}

function computeAnchoredShifts(draftList, appliedList, idKey = 'id') {
  const appliedIds = appliedList.map(x => x[idKey]);
  const draftIds = draftList.map(x => x[idKey]);
  const anchors = new Set(lcs(appliedIds, draftIds)); // id-ы якорей (сохранили относительный порядок)

  // карты позиций
  const appliedPos = new Map(appliedList.map((it,i)=>[it[idKey], i]));
  const draftPos   = new Map(draftList.map((it,i)=>[it[idKey], i]));

  // сделаем массив якорей в порядке appliedList для удобства
  const anchorList = appliedList.filter(it => anchors.has(it[idKey])).map(it => it[idKey]);

  // добавим фиктивные "границы" — начало и конец
  const anchorBoundaries = [{id: null, appliedIndex: -1, draftIndex: -1}]
    .concat(anchorList.map(id => ({id, appliedIndex: appliedPos.get(id), draftIndex: draftPos.get(id)})))
    .concat([{id: null, appliedIndex: appliedList.length, draftIndex: draftList.length}]);

  const result = draftList.map(it => ({ ...it, shift: null }));

  // Для каждого сегмента между соседними якорями: берем элементы из applied в этом сегменте
  for (let s = 0; s < anchorBoundaries.length - 1; s++) {
    const left = anchorBoundaries[s];
    const right = anchorBoundaries[s+1];

    // applied-элементы в сегменте (исключая правый якорь)
    const segApplied = appliedList.slice(left.appliedIndex + 1, right.appliedIndex);
    // соответствующий блок в draft — все элементы между draftIndex левого и правого якоря
    const segDraftStart = left.draftIndex + 1;
    // Для каждого элемента в сегменте compute relative shift:
    // относительный индекс в applied: idxAppliedRel = origIndex - left.appliedIndex - 1
    // относительный индекс в draft:  idxDraftRel = draftIndex - segDraftStart
    // shift = idxDraftRel - idxAppliedRel
    segApplied.forEach((it, k) => {
      const id = it[idKey];
      const origIdx = appliedPos.get(id);
      const curIdx = draftPos.get(id);
      if (typeof origIdx === 'number' && typeof curIdx === 'number') {
        const idxAppliedRel = origIdx - left.appliedIndex - 1;
        const idxDraftRel = curIdx - segDraftStart;
        const shift = idxDraftRel - idxAppliedRel;
        // положим shift в result по позиции в draftList
        const outIndex = draftPos.get(id);
        result[outIndex] = Object.assign({}, it, { shift });
      }
    });
  }
  return result;
}
```

Кратко о различии:
- computeNetShifts — показывает простой итоговый сдвиг (наиболее интуитивно).
- computeAnchoredShifts — сперва ищет неизменные элементы (LCS), затем вычисляет сдвиг в пределах каждого сегмента между якорями. Полезно, если вы хотите «привязать» части списка к немещавшимся элементам и игнорировать перестановки, которые в итоге вернулись.

Если пришлёте example из вашего jsbin (содержимое draftList и appliedList или код функции shouldShowRevert), я подстрою функцию под ваши данные и покажу конкретный вывод, ожидаемый вами (включая случай, где shouldShowRevert(draftList[0], ...) должен вернуть false).
Похожие вопросы