php - 使用存储对数组进行排序

Question

我有一个这样的数组:

$a = [2, 1, 1, 2, 3, 1, 3, 2];

我需要使用外部变量对其进行排序。但我需要以下输出:

$output = [
    [0, s],  // Move $a[0] to storage
    [5, 0],  // Move $a[5] to $[0]
    [s, 5],  // Move storage to $a[5]
    [4, s],  // Move $a[4] to storage
    [7, 4],  // Move $a[7] to $a[4]
    [s, 7]   // Move storage to $[7]
];

我需要一种算法来生成数组、分隔字符串或任何类型的输出，其中包含对数组进行排序的步骤。

主要在 PHP 中，但我可以从任何语言实现它。

Answer 1

一个有趣但可能不是那么有效的想法:

确定每个元素的计数和排序偏移量:

$a = [2, 1, 1, 2, 3, 1, 3, 2];
$count_and_offset = [1 => [3,0], 2 => [3,3], 3 => [2,6]]

确定排列，

$a_permutation = [5, 2, 3, 4, 8, 1, 7, 6];

枚举循环(http://en.wikipedia.org/wiki/Cyclic_permutation)，

(1586)(2)(3)(4)(7)

做一个列表(例子不是从零开始的)，

[[6, s]
,[8, 6]
,[5, 8]
,[1, 5]
,[s, 1]]