如何通过索引数组重新排列数组（证明）？

本文介绍了如何通过索引数组重新排列数组（证明）？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

给出一个数组 arr 和一个索引数组 ind ，以下算法重新排列 arr 就地满足给定索引：

Given an array arr and an array of indices ind, the following algorithm rearranges arr in-place to satisfy the given indices:

function swap(arr, i, k) { var temp = arr[i]; arr[i] = arr[k]; arr[k] = temp; } function rearrange(arr, ind) { for (var i = 0, len = arr.length; i < len; i++) { if (ind[i] !== i) { swap(arr, i, ind[i]); swap(ind, i, ind[i]); } } }

例如：

var arr = ["A", "B", "C", "D", "E", "F"]; var ind = [ 4, 0, 5, 2, 1, 3 ]; rearrange(arr, ind); console.log(arr); // => ["B", "E", "D", "F", "A", "C"]

证明该算法有效的最有说服力的方法是什么？

What's the most convincing way to prove that the algorithm works?

推荐答案

此算法不起作用，足以显示一个反例：

This algorithm does not work, it's enough to show a counter-example:

var arr = ["A", "B", "C", "D"]; var ind = [ 2, 3, 1, 0]; rearrange(arr, ind); console.log(arr); // => ["C", "D", "A", "B"]

可行的替代方法是

function swap(arr, i, k) { var temp = arr[i]; arr[i] = arr[k]; arr[k] = temp; } function rearrange(arr, ind) { for (var i = 0, len = arr.length; i < len; i++) { if (ind[i] !== i) { swap(arr, i, ind[i]); swap(ind, i, ind[i]); if (ind[i] < i) { i = ind[i]-1; } } } }