Я создаю приложение, в котором тасование массивов является одним из основных компонентов.Это не очень важно, что содержат массивы, но для простоты я использовал отдельные символы в моем примере кода ниже.В большинстве случаев массив будет содержать 1-3000 элементов, но, возможно, больше.
Массив a представляет исходное состояние массива, а массив b - это конечное состояние, в котором я хочу, чтобы массив находился вСостояние b может быть сделано с использованием любого количества преобразований, но после перемешивания я хочу найти минимальный набор преобразований, который необходимо выполнить, чтобы преобразовать массив a в то же состояние, что и массив b.
Существуют некоторые ограничения в отношении того, какие преобразования можно выполнить.Я буду использовать API для перетасовки массива, поэтому я хочу найти наименьшее (или близкое) число необходимых преобразований, чтобы минимизировать количество запросов.
Преобразования могут быть сделаны только путем выбора start индекса элемента (ов), который вы хотите переместить, range того, сколько последовательных элементов вы хотите переместить за один раз, и какой индекс выхочу разместить диапазон before.Список преобразований можно упорядочить таким образом, чтобы каждое преобразование использовало предыдущий результат, или все они могут использовать исходное состояние 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}
]
}
Поскольку я буду использовать разные алгоритмы тасования, я бы предпочел использовать исходное и конечное состояние массива для расчета преобразований, но если есть другие более эффективные решения, требующие немного другого ввода, который мог быработать также.
Что меня действительно интересует, так это узнать, может ли эта проблема быть решена в разумные сроки, и есть ли какие-либо алгоритмы, которые могут помочь мне сделать это.