|
Parallel Colt 0.9.4 | |||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectcern.colt.GenericPermuting
public class GenericPermuting
Generically reorders (permutes) arbitrary shaped data (for example, an array, three arrays, a 2-d matrix, two linked lists) using an in-place swapping algorithm. Imagine having a couple of apples. For some reason you decide to reorder them. The green one before the red one. The pale one after the shiny one, etc. This class helps to do the job.
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
Method Summary | |
---|---|
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. |
Methods inherited from class java.lang.Object |
---|
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Method Detail |
---|
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.tdouble.sampling
without replacement or a random engine like
DoubleMersenneTwister
.
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] <br> // 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)
@Deprecated 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)
|
Parallel Colt 0.9.4 | |||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |