猜测哪个数组元素的索引（位置）在同一数组内发生变化的算法

Question

我在 this thread 上找了一段时间，但我在那里能找到的所有结果都是两个数组之间的比较结果是添加或删除了哪些元素。

我需要的只是猜测哪个元素已从索引移动到另一个。

示例：让我们采用以下数组：

let array1 = ['A', 'B', 'C', 'D', 'E', 'F'];

'E' 元素将从第 4 个索引移动到第 2 个索引，我们将得到：

 let array2 = ['A', 'B', 'E', 'C', 'D', 'F'];

我需要一个函数，returns 哪个元素已更改，它在新 array2 中的新索引和它在 array1 中的旧索引；

我过去做过这样的算法，大致（根据我现在的记忆）包括寻找两个数组之间的第一个不同元素然后检查它后面的序列以猜测找到的 diff 元素是否是本身被移动的那个或取代它的那个。

所以在重写它之前，我希望我能找到一个随时可用的 ;)

Answer 1

我不确定完整的要求是什么，但这将检测前后移动以及字符交换。它适用于任何订单，但随着连续发生的变化越多，它对变化的预测就越不准确。这是一个使用字典的示例：

const array1 = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K'];
const array2 = ['A', 'B', 'E', 'C', 'D', 'F', 'H', 'I', 'G', 'K' , 'J'];
let globalOffset = 0;
let currentSuspect = "";
var dict = new Object();
array1.forEach((char, index) => {
  dict[char] = index;
});
array2.forEach((char, index) => {
  dict[char] = dict[char] - index;
});

let offset = 0;
let prevValue = 0;
Object.entries(dict).forEach((entry, index) => {
  const [key, value] = entry;
  
  switch(true){
    case offset === 0 && value < -1:
      console.log(`The character ${key} had its index moved forward by ${Math.abs(value)}! \n New index: ${index + Math.abs(value)} - Old index: ${index}`);
      break;
    case offset < 0 && value > 1:
      console.log(`The character ${key} had its index moved backwards by ${value}! \n New index: ${index + offset} - Old index: ${index}`);
      break;
    case prevValue === -1 && offset === -1 && value === 1:
      console.log(`The characters ${key} and ${array2[index]} were swapped!`);
      break;
  }
  prevValue = value;
  offset += value;
});

Answer 2

let array1 = ['A', 'B', 'C', 'D', 'E', 'F'];

// test 1 : moving 'B' from index 1 to index 3
let array2 = ['A', 'C', 'D', 'B', 'E', 'F'];

// test 2: moving 'E' from 4 to 1
// let array2 = ['A', 'E', 'B', 'C', 'D', 'F'];

// test 3 : moving 'A' from 0 to 5
// let array2 = ['B', 'C', 'D', 'E', 'F', 'A'];

function getMovedElementInfos(array1, array2) {
    let firstDiffElIndexInNewArray = array2.findIndex((el, elindx) => el !== array1[elindx]);
    let firstDiffElInNewArray = array2[firstDiffElIndexInNewArray];
    let nextElInNewArray = array2[firstDiffElIndexInNewArray + 1];
    let firstDiffElIndexInOldArray = array1.findIndex(el => el === firstDiffElInNewArray);
    let nextElInOldArray = array1[firstDiffElIndexInOldArray + 1];
    let movedEl, movedElFrom, movedElTo;
    if (nextElInNewArray === nextElInOldArray) {
        movedEl = array1[firstDiffElIndexInNewArray];
        movedElFrom = firstDiffElIndexInNewArray;
        movedElTo = array2.findIndex(el => el === movedEl);
    } else {
        movedEl = firstDiffElInNewArray;
        movedElFrom = firstDiffElIndexInOldArray;
        movedElTo = firstDiffElIndexInNewArray;
    }
    return {
        movedEl,
        movedElFrom,
        movedElTo
    }
}
const {
    movedEl,
    movedElFrom,
    movedElTo
} = getMovedElementInfos(array1, array2)

console.log('movedEl is: ', movedEl);
console.log('movedEl index in old array is: ', movedElFrom);
console.log('movedEl index in new array is: ', movedElTo);

console.log('array1[movedElFrom]: ', array1[movedElFrom]);
console.log('array2[movedElTo]: ', array2[movedElTo]);

Answer 3

做法如下...

迭代数组之一，最好是当前数组。
对于每个当前 item/value 从最近的数组中获取其索引 ...
...并将此项s/value的当前索引与其最近的索引进行比较。
如果两个索引不相等（包括由于删除 value/item 而导致的 -1 的最近索引）创建一个类似对象的状态，其中包含值和索引的数据并将其推入结果数组。

实现基于Array.prototype.reduce where on would process the current item array and would pass the recent item array as part of a accumulator/collector as the reducer function's initial value。

function collectPositionChange({ recent, result }, value, currentIdx) {
  const recentIdx = recent.indexOf(value);
  if (recentIdx !== currentIdx) {

    result.push({ value, currentIdx, recentIdx });
  }
  return { recent, result };
}
const recentItems = ['A', 'B', 'E', 'C', 'D', 'F'];
const currentItems = ['A', 'B', 'C', 'D', 'E', 'F'];

console.log(
  currentItems
    .reduce(collectPositionChange, { recent: recentItems, result: [] })
    .result
);
console.log(
  ['A', 'C', 'D', 'B', 'E', 'F']
    .reduce(collectPositionChange, { recent: ['A', 'B', 'C', 'D', 'E', 'F'], result: [] })
    .result
);
console.log(
  ['A', 'B', 'C', 'D', 'E', 'F']
    .reduce(collectPositionChange, { recent: ['A', 'C', 'D', 'B', 'E', 'F'], result: [] })
    .result
);

.as-console-wrapper { min-height: 100%!important; top: 0; }

猜测哪个数组元素的索引（位置）在同一数组内发生变化的算法

Algorithm to guess which array element has its index (position) changed inside the same array

javascript

arrays

algorithm

compare

indexof