Алгоритм перестановки целочисленных массивов
Существует набор, например (1, 4, 2, 5, 7, 6, 9, 8, 3). Мы рассчитываем егоfirst difference
(FD) следующим образом:firstDifference[i] = inputArray[i+1] - inputArray[i]
, inputArray - оригинальный набор. В примере это (1, 4, 2, 5, 7, 6, 9, 8, 3). firstDifference создается из inputArray следующим образом: (2-й элемент inputArray) - (1-й элемент inputArray) и так далее.
Таким образом, FD данного набора (3, -2, 3, 2, -1, 3, -1, -5). Задача состоит в том, чтобы найти ряд перестановок заданного набора, первое отличие которых состоит в перестановке FD. В примере мы должны найти такие перестановки (1, 4, 2, 5, 7, 6, 9, 8, 3), что первыми отличиями является перестановка (3, -2, 3, 2, -1, 3, - 1, -5).
Вот мой алгоритм:
Найти все перестановки данного набора.Найти FD данного набора.Найдите все первые отличия перестановок в нашем наборе.выбирайте только такие наборы, в которых первые различия содержат номера FD данного набора. Посчитай их.Но этот алгоритм слишком медленный. Можете ли вы помочь создать более быстрый алгоритм? Возможно, я делаю какие-то шаги, которые можно устранить?