Как происходит переупорядочение одного списка на основе подразумеваемого переупорядочения, полученного в результате сортировки другого списка?

Question

Меня не интересует какой-либо конкретный алгоритм; Я просто хочу знать, имеет ли это общее имя, о котором я просто не знаю.

Точнее сказать, у меня есть X = [42, 0, 99] и Y = ["a", "b", "c"]. Как это называется, когда я переупорядочиваю Y таким же образом, как я должен переупорядочить X, чтобы создать X отсортированный список, заканчивающийся на ["b", "a", "c"]?

А как насчет самого переупорядочения, который является своего рода списком - то есть [<2nd>, <1st>, <3rd>] - у которого тоже есть общее имя?

Похоже, это была бы операция, имя которой я должен знать, со своей собственной страницей в Википедии и всем остальным (или запись в Словаре алгоритмов и структур данных NIST: http://xw2k.nist.gov/dads/). Я, вероятно, почувствую себя глупым, когда кто-нибудь ответит на это.

Answer 1

Само переупорядочение называется перестановкой ^{(см. Sidenote)} .

Я не знаю специального термина для ситуации, но вы могли бы сказать, чтовы применяете перестановку, которая сортирует список X, к списку Y.

Sidenote : обратите внимание, что слово "перестановка" может относиться как к конкретному порядку группы элементов, например, с упорядоченным списком [3, 1, 2], представляющим собой перестановку чисел {1, 2, 3}, а также переупорядочение элементов (как всамо преобразование), например тот, который переставляет упорядоченный список [3, 1, 2] в упорядоченный список [1, 2, 3].

Answer 2

Вы можете назвать это сортировкой по параллельному ключу, так как X содержит ключи сортировки, а Y содержит значения.На функциональном языке, например, Scala, это может быть реализовано как X.zip (Y) .sortWith ((a, b) => a._1 a._2)

Answer 3

Насколько мне известно, для этой конкретной ситуации нет термина, но вы применяете то же преобразование к спискам X и Y, и вы создаете преобразование таким образом, чтобы оно преобразовывало список X в отсортированный список.

Answer 4

В основном я знаю, что это «индексированная сортировка».X - это индекс, который вы используете для сортировки Y.