The effect of Arrays.sort, as well as shuffle, reverse, rotate, and many other operations, can be expressed as a permutation vector or "PV". Since arrays are indexed by Java `int` indexes, the natural format for a permutation vector is an `int[]` array which contains no repeats and no gaps, and starts with zero.
For example, with PVs, a shuffle operation could be thought of factoring into two steps: First create a random PV (by shuffling an iota vector of the desired length), and second, apply the PV to your array.
Although that is less efficient than shuffling all in one step, exposing the PV under the shuffle is strictly more powerful. For example, you can shuffle two or more arrays in parallel, using the same random PV. Or you can shuffle an array, apply some algorithm to it, and then restore it to its original order, by applying the same PV a second time but in the inverse ("backwards") sense.
What goes for shuffles also goes for sorts. A sorting operation takes an array (or list) of keys and decides how to reorder them. The result of this sorting operation could be reported as a PV, instead of as direct side effects to the sorted array. This might be useful if the array to be sorted were (for any of a number of reasons) not suitable for modification; the PV would report the result of the sorting. The PV might also be useful if the array needed to be sorted, but a *second* array *also* needed to be reordered *in parallel*. And of course it is common for algorithms to work on nearest neighbors in sorted inputs, but if the sorting phase produced a PV, then the PV could be used (backwards) to restore the array to its original order, after the nearest-neighbor computation.
Thus, PVs arise naturally when extending algorithms that do any kind of one-shot reordering of an array (or list).
The main PV operations might be referred to as forward application and backward application, as follows:
```
permuteForward(pv={0,3,1,2}, a={A,B,C,D})
changes a to a' == {a[0],a[3],a[1],a[2]} == {A,D,B,C}
therefore a'[i] <- a[pv[i]]
permuteBackward(pv={0,3,1,2}, a'={A,D,B,C})
reverses the previous change to a', so a is {A,B,C,D}
permuteBackward(pv={0,3,1,2}, a={A,B,C,D})
changes a to a'' == {A,C,D,B}
therefore a''[pv[i]] <- a[i]
```
In the forward application of a PV, the element at position i (`a[i]`) is moved to position `pv[i]`, so it ends up as `a[pv[i]]`. In the reverse application, the element `a[pv[i]]` moves back to `a[i]`.
These operations are clearly inverses. The naming is arbitrary, but the forward version is intended to correspond to the standard one-line notation[1] for mathematical permutations.
[1]: <http://en.wikipedia.org/wiki/Permutation#One-line_notation>
The simplest algorithm to apply a permutation would use a dynamically allocated clone of the original array, and simply assign the old elements (taken from the copy) over the top of the original array but in a new order. A tricky way to reduce footprint is not clone the array, but use a bit-array to keep track of which items have been moved yet, systematically visiting each element in the array to be moved, working each permutation cycle separately to avoid smashing more than one target array element at a time. Or, the PV itself could be cloned and the clone modified destructively while visiting cycles; the sign bits could easily carry "visited" state. Any of these techniques would work for either direction.
More subtle algorithms can also be considered that exploit the connection between permutation and sorting. For example, consider sorting the target array using a comparator which uses the corresponding PV entry as the sort key, while continually updating the target array *and* the PV *together*. That would result in the PV ending up as an iota vector (an identity PV of the form `{0,1,2…}`) and the array reordered by the original PV contents, as if by `permuteBackward`.
Constructing a PV is a little simpler than applying it, in many cases. Generally you start with a neutral permutation (an iota vector of the form `{0,1,2…}`)and operate on that permutation as if it were the only data you care about. So shuffling or sorting or rotating that PV, using the appropriate context, will produce a PV which, when applied in the forward direction, will reorder any other data set with exactly the same shuffle or sort-result or rotation.
The this RFE connects to this other RFE:
<https://bugs.openjdk.org/browse/JDK-8265378>
Arrays.sort should provide optional external comparator for int and long arrays
This other RFE would allow an iota PV (in the form of an `int[]` array) to be sorted by using keys from a second array. The resulting updated array would be a PV which specifies how the second array should be permuted, if its elements (the keys just referred to) are to be sorted. In this way, a reusable PV can be extracted from any sortable data structure, by sorting the indexes into that data structure.
Suggested API points:
```
void permute[Forward|Backward](int[] pv, [Object|int|long|…][] a)
void permute[Forward|Backward](int[] pv, [Object|int|long|…][] a, int frid, int toid)
permutation(int length, IntUnaryOperator fn) -> new int[] pv
emptyPermutation(int length) -> new int[] iota = permutation(length, i->i)
permutationInverse(int[] pv) -> new int[] pvInverse
```
Possible difficulties:
- Not all `int[]` arrays represent PVs, and it's O(N) hard to detect fakes.
- When an `int[]` array fails to represent a PV, the result is hard to define.
- Algorithms which require O(N) temporary storage are unpleasant.
As Stuart Marks points out, decomposing a permutation into cycles is an interesting operation. It is arguably a more basic primitive than some of the above operations, since inverting or applying a permutation is assisted by knowing its cycles, and so an algorithm that can find the cycles is useful for those other operations as well. A straightforward output format for a cycle detector would be a ragged 2D int array, one sub-array per cycle, and in a canonical order (such as highest element first in each cycle, and lower-starting cycles first). Tweaking such a representation for compression (e.g., by omitting 1-cycles or flattening into a single array using sign bit boundaries) would probably not be profitable in the end. An inverse function which converts a cycle set to a permutation should not require a canonical input, but should accept an additional parameter which determines how many steps to take along each cycle and in what direction, thus providing a way to efficiently compute inverses and powers of permutations.
```
permutationToCycles(int[] pv) -> new int[][] canonicalCycles
permutationFromCycles(int[][] cycles, int steps) -> new int[] pv
```
For example, with PVs, a shuffle operation could be thought of factoring into two steps: First create a random PV (by shuffling an iota vector of the desired length), and second, apply the PV to your array.
Although that is less efficient than shuffling all in one step, exposing the PV under the shuffle is strictly more powerful. For example, you can shuffle two or more arrays in parallel, using the same random PV. Or you can shuffle an array, apply some algorithm to it, and then restore it to its original order, by applying the same PV a second time but in the inverse ("backwards") sense.
What goes for shuffles also goes for sorts. A sorting operation takes an array (or list) of keys and decides how to reorder them. The result of this sorting operation could be reported as a PV, instead of as direct side effects to the sorted array. This might be useful if the array to be sorted were (for any of a number of reasons) not suitable for modification; the PV would report the result of the sorting. The PV might also be useful if the array needed to be sorted, but a *second* array *also* needed to be reordered *in parallel*. And of course it is common for algorithms to work on nearest neighbors in sorted inputs, but if the sorting phase produced a PV, then the PV could be used (backwards) to restore the array to its original order, after the nearest-neighbor computation.
Thus, PVs arise naturally when extending algorithms that do any kind of one-shot reordering of an array (or list).
The main PV operations might be referred to as forward application and backward application, as follows:
```
permuteForward(pv={0,3,1,2}, a={A,B,C,D})
changes a to a' == {a[0],a[3],a[1],a[2]} == {A,D,B,C}
therefore a'[i] <- a[pv[i]]
permuteBackward(pv={0,3,1,2}, a'={A,D,B,C})
reverses the previous change to a', so a is {A,B,C,D}
permuteBackward(pv={0,3,1,2}, a={A,B,C,D})
changes a to a'' == {A,C,D,B}
therefore a''[pv[i]] <- a[i]
```
In the forward application of a PV, the element at position i (`a[i]`) is moved to position `pv[i]`, so it ends up as `a[pv[i]]`. In the reverse application, the element `a[pv[i]]` moves back to `a[i]`.
These operations are clearly inverses. The naming is arbitrary, but the forward version is intended to correspond to the standard one-line notation[1] for mathematical permutations.
[1]: <http://en.wikipedia.org/wiki/Permutation#One-line_notation>
The simplest algorithm to apply a permutation would use a dynamically allocated clone of the original array, and simply assign the old elements (taken from the copy) over the top of the original array but in a new order. A tricky way to reduce footprint is not clone the array, but use a bit-array to keep track of which items have been moved yet, systematically visiting each element in the array to be moved, working each permutation cycle separately to avoid smashing more than one target array element at a time. Or, the PV itself could be cloned and the clone modified destructively while visiting cycles; the sign bits could easily carry "visited" state. Any of these techniques would work for either direction.
More subtle algorithms can also be considered that exploit the connection between permutation and sorting. For example, consider sorting the target array using a comparator which uses the corresponding PV entry as the sort key, while continually updating the target array *and* the PV *together*. That would result in the PV ending up as an iota vector (an identity PV of the form `{0,1,2…}`) and the array reordered by the original PV contents, as if by `permuteBackward`.
Constructing a PV is a little simpler than applying it, in many cases. Generally you start with a neutral permutation (an iota vector of the form `{0,1,2…}`)and operate on that permutation as if it were the only data you care about. So shuffling or sorting or rotating that PV, using the appropriate context, will produce a PV which, when applied in the forward direction, will reorder any other data set with exactly the same shuffle or sort-result or rotation.
The this RFE connects to this other RFE:
<https://bugs.openjdk.org/browse/JDK-8265378>
Arrays.sort should provide optional external comparator for int and long arrays
This other RFE would allow an iota PV (in the form of an `int[]` array) to be sorted by using keys from a second array. The resulting updated array would be a PV which specifies how the second array should be permuted, if its elements (the keys just referred to) are to be sorted. In this way, a reusable PV can be extracted from any sortable data structure, by sorting the indexes into that data structure.
Suggested API points:
```
void permute[Forward|Backward](int[] pv, [Object|int|long|…][] a)
void permute[Forward|Backward](int[] pv, [Object|int|long|…][] a, int frid, int toid)
permutation(int length, IntUnaryOperator fn) -> new int[] pv
emptyPermutation(int length) -> new int[] iota = permutation(length, i->i)
permutationInverse(int[] pv) -> new int[] pvInverse
```
Possible difficulties:
- Not all `int[]` arrays represent PVs, and it's O(N) hard to detect fakes.
- When an `int[]` array fails to represent a PV, the result is hard to define.
- Algorithms which require O(N) temporary storage are unpleasant.
As Stuart Marks points out, decomposing a permutation into cycles is an interesting operation. It is arguably a more basic primitive than some of the above operations, since inverting or applying a permutation is assisted by knowing its cycles, and so an algorithm that can find the cycles is useful for those other operations as well. A straightforward output format for a cycle detector would be a ragged 2D int array, one sub-array per cycle, and in a canonical order (such as highest element first in each cycle, and lower-starting cycles first). Tweaking such a representation for compression (e.g., by omitting 1-cycles or flattening into a single array using sign bit boundaries) would probably not be profitable in the end. An inverse function which converts a cycle set to a permutation should not require a canonical input, but should accept an additional parameter which determines how many steps to take along each cycle and in what direction, thus providing a way to efficiently compute inverses and powers of permutations.
```
permutationToCycles(int[] pv) -> new int[][] canonicalCycles
permutationFromCycles(int[][] cycles, int steps) -> new int[] pv
```
- relates to
-
JDK-8265378 Arrays.sort should provide optional external comparator for int and long arrays
-
- Open
-