arrays - 是否有一种算法可以找到将数组转换为新状态所需的最小转换集

Question

我正在制作一个应用程序，其中改组数组是主要组件之一。数组包含的内容并不重要，但为简单起见，我在下面的示例代码中使用了单个字符。在大多数情况下，该数组将包含 1-3000 个元素，但可能更多。

数组a表示数组的原始状态，数组b是我希望数组处于的最终状态。b<的状态 可以使用任意数量的转换进行，但在改组之后我想找到需要完成的最小转换集，以便将数组 a 转换为与数组 相同的状态>b.

但是，可以进行的转换有一些限制。我将使用一个 API 来洗牌数组，这就是为什么我想找到所需的最小(或接近)转换数量，以最大限度地减少请求数量。

转换只能通过选择要移动的元素的 start 索引、要移动的连续元素数的 range 来完成一个时间，以及您要将范围放在哪个索引之前。可以对转换列表进行排序，以便每个转换都使用之前的结果，或者它们都可以使用 a 的原始状态作为基础。

一些示例伪 javascript 代码:

const a = ['a', 'b', 'c', 'd', 'e']
const b = ['d', 'c', 'a', 'b', 'e']

const getTransformations = (a, b) => {
  // ...

  return [
    {start: 0, range: 2, before: 4},
    {start: 0, range: 1, before: 2}
  ]
}

因为我将使用不同的改组算法，所以我更愿意使用数组的原始状态和最终状态来计算转换，但是如果有其他更有效的解决方案需要稍微不同的输入就可以工作

我真正感兴趣的是知道这是否是一个可以在合理时间内解决的问题，以及是否有任何算法可以帮助我做到这一点。

Answer 1

请检查您是否需要这样的东西minimum-swaps-to-make-two-array-identical