Class GenericPermuting
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]invalid input: '<'--g[0], g[1]invalid input: '<'--g[4], g[2]invalid input: '<'--g[2], g[3]invalid input: '<'--g[3], g[4]invalid input: '<'--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]invalid input: '<'--g[0], g[1]invalid input: '<'--g[4], g[2]invalid input: '<'--g[1], g[3]invalid input: '<'--g[2], g[4]invalid input: '<'--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
|
- Version:
- 1.0, 10-Oct-99
- See Also:
-
Constructor Summary
ConstructorsModifierConstructorDescriptionprotected
Makes this class non instantiable, but still let's others inherit from it. -
Method Summary
Modifier and TypeMethodDescriptionstatic 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
Deprecated.static void
Generically reorders arbitrary shaped generic data g such that g[i] == g[indexes[i]].static void
A non-generic variant of reordering, specialized for Object[], same semantics.
-
Constructor Details
-
GenericPermuting
protected GenericPermuting()Makes this class non instantiable, but still let's others inherit from it.
-
-
Method Details
-
permutation
public static int[] permutation(long p, int N) Returns the p-th permutation of the sequence [0,1,...,N-1]. A small but smart and efficient routine, ported from Cernlib. The Fortran source. A sequence of N distinct elements has N! permutations, which are enumerated in lexicographical order 1 .. 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 likeMersenneTwister
.
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]- Parameters:
p
- the lexicographical ordinal number of the permutation to be computed.N
- the length of the sequence to be generated.- Returns:
- the p-th permutation.
- Throws:
IllegalArgumentException
- if p invalid input: '<' 1 || N invalid input: '<' 0 || p > N!.
-
permute
public static void permute(int[] list, int[] indexes) A non-generic variant of reordering, specialized for int[], same semantics. Quicker than generic reordering. Also for convenience (forget about the Swapper object). -
permute
Deprecated.Deprecated. Generically reorders arbitrary shaped generic data g such that g[i] == g[indexes[i]]. (The generic data may be one array, a 2-d matrix, two linked lists or whatever). This class swaps elements around, in a way that avoids stumbling over its own feet.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]invalid input: '<'--g[0], g[1]invalid input: '<'--g[4], g[2]invalid input: '<'--g[2], g[3]invalid input: '<'--g[3], g[4]invalid input: '<'--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]invalid input: '<'--g[0], g[1]invalid input: '<'--g[4], g[2]invalid input: '<'--g[1], g[3]invalid input: '<'--g[2], g[4]invalid input: '<'--g[3].
- Parameters:
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.
-
permute
Generically reorders arbitrary shaped generic data g such that g[i] == g[indexes[i]]. (The generic data may be one array, a 2-d matrix, two linked lists or whatever). This class swaps elements around, in a way that avoids stumbling over its own feet.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]invalid input: '<'--g[0], g[1]invalid input: '<'--g[4], g[2]invalid input: '<'--g[2], g[3]invalid input: '<'--g[3], g[4]invalid input: '<'--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]invalid input: '<'--g[0], g[1]invalid input: '<'--g[4], g[2]invalid input: '<'--g[1], g[3]invalid input: '<'--g[2], g[4]invalid input: '<'--g[3].
- Parameters:
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.
-
permute
A non-generic variant of reordering, specialized for Object[], same semantics. Quicker than generic reordering. Also for convenience (forget about the Swapper object).
-