public class GenericPermuting extends Object
This class swaps elements around, in a way that avoids stumbling over its own feet: Let before be the generic data before calling the reordering method. Let after be the generic data after calling the reordering method. Then there holds after[i] == before[indexes[i]].
Similar to GenericSorting, this class has no idea what kind of data it is reordering.
It can decide to swap the data at index a with the data at index b.
It calls a user provided Swapper object that knows how to swap the data of these indexes.
For convenience, some non-generic variants are also provided. Further a method to generate the p-th lexicographical permutation indexes.
Example:
Reordering [A,B,C,D,E] with indexes [0,4,2,3,1] yields [A,E,C,D,B] In other words, in the reordered list, we first have the element at old index 0, then the one at old index 4, then the ones at old indexes 2,3,1. g[0]<--g[0], g[1]<--g[4], g[2]<--g[2], g[3]<--g[3], g[4]<--g[1]. Reordering [A,B,C,D,E] with indexes [0,4,1,2,3] yields [A,E,B,C,D] In other words g[0]<--g[0], g[1]<--g[4], g[2]<--g[1], g[3]<--g[2], g[4]<--g[3]. |
Here are some example swappers:
// a swapper knows how to swap two indexes (a,b)
// reordering an array
Swapper swapper = new Swapper() {
public void swap(int a, int b) {
String tmp; // reordering String[]
// int tmp; // reordering int[]
tmp = array[a]; array[a] = array[b]; array[b] = tmp;
}
};
// reordering a list
Swapper swapper = new Swapper() {
public void swap(int a, int b) {
Object tmp;
tmp = list.get(a);
list.set(a, list.get(b));
list.set(b, tmp);
}
};
// reordering the rows of a 2-d matrix (see
|
Swapper,
GenericSorting| Modifier and Type | Method and Description |
|---|---|
static int[] |
permutation(long p,
int N)
Returns the p-th permutation of the sequence [0,1,...,N-1].
|
static void |
permute(int[] list,
int[] indexes)
A non-generic variant of reordering, specialized for int[], same semantics.
|
static void |
permute(int[] indexes,
Swapper swapper,
int[] work)
Deprecated.
|
static void |
permute(int[] indexes,
Swapper swapper,
int[] work1,
int[] work2)
Generically reorders arbitrary shaped generic data g such that g[i] == g[indexes[i]].
|
static void |
permute(Object[] list,
int[] indexes)
A non-generic variant of reordering, specialized for Object[], same semantics.
|
public static int[] permutation(long p,
int N)
This is, for example, useful for Monte-Carlo-tests where one might want to compute k distinct and random permutations of a sequence, obtaining p from cern.jet.random.sampling without replacement or a random engine like MersenneTwister.
Note: When N! exceeds the 64-bit range (i.e. for N > 20), this method has different behaviour: it makes a sequence [0,1,...,N-1] and randomizes it, seeded with parameter p.
Examples:
http://www.hep.net/wwwmirrors/cernlib/CNASDOC/shortwrups_html3/node255.html // exactly lexicographically enumerated (ascending) permutation(1,3) --> [ 0,1,2 ] permutation(2,3) --> [ 0,2,1 ] permutation(3,3) --> [ 1,0,2 ] permutation(4,3) --> [ 1,2,0 ] permutation(5,3) --> [ 2,0,1 ] permutation(6,3) --> [ 2,1,0 ] permutation(1 ,20) --> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] permutation(2 ,20) --> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 19, 18] permutation(1000000,20) --> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 17, 18, 13, 19, 11, 15, 14, 16, 10] permutation(20! -2 ,20) --> [19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 1, 2, 0] permutation(20! -1 ,20) --> [19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 0, 1] permutation(20! ,20) --> [19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
// not exactly enumerated, rather randomly shuffled permutation(1,21) --> [18, 20, 11, 0, 15, 1, 19, 13, 3, 6, 16, 17, 9, 5, 12, 4, 7, 14, 8, 10, 2] permutation(2,21) --> [1, 9, 4, 16, 14, 13, 11, 20, 10, 8, 18, 0, 15, 3, 17, 5, 12, 2, 6, 7, 19] permutation(3,21) --> [12, 0, 19, 1, 20, 5, 8, 16, 6, 14, 2, 4, 3, 17, 11, 13, 9, 10, 15, 18, 7]
p - the lexicographical ordinal number of the permutation to be computed.N - the length of the sequence to be generated.IllegalArgumentException - if p < 1 || N < 0 || p > N!.public static void permute(int[] list,
int[] indexes)
public static void permute(int[] indexes,
Swapper swapper,
int[] work)
Example:
Reordering [A,B,C,D,E] with indexes [0,4,2,3,1] yields [A,E,C,D,B] In other words g[0]<--g[0], g[1]<--g[4], g[2]<--g[2], g[3]<--g[3], g[4]<--g[1]. Reordering [A,B,C,D,E] with indexes [0,4,1,2,3] yields [A,E,B,C,D] In other words g[0]<--g[0], g[1]<--g[4], g[2]<--g[1], g[3]<--g[2], g[4]<--g[3].
indexes - the permutation indexes.swapper - an object that knows how to swap two indexes a,b.work - the working storage, must satisfy work.length >= indexes.length; set work==null if you don't care about performance.public static void permute(int[] indexes,
Swapper swapper,
int[] work1,
int[] work2)
Example:
Reordering [A,B,C,D,E] with indexes [0,4,2,3,1] yields [A,E,C,D,B] In other words g[0]<--g[0], g[1]<--g[4], g[2]<--g[2], g[3]<--g[3], g[4]<--g[1]. Reordering [A,B,C,D,E] with indexes [0,4,1,2,3] yields [A,E,B,C,D] In other words g[0]<--g[0], g[1]<--g[4], g[2]<--g[1], g[3]<--g[2], g[4]<--g[3].
indexes - the permutation indexes.swapper - an object that knows how to swap two indexes a,b.work1 - some working storage, must satisfy work1.length >= indexes.length; set work1==null if you don't care about performance.work2 - some working storage, must satisfy work2.length >= indexes.length; set work2==null if you don't care about performance.public static void permute(Object[] list, int[] indexes)
Jas4pp 1.5 © Java Analysis Studio for Particle Physics