cern.colt

Class GenericPermuting

java.lang.Object

cern.colt.GenericPermuting

public class GenericPermuting
extends Object

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 cern.colt.matrix) Swapper swapper = new Swapper() { public void swap(int a, int b) { matrix.viewRow(a).swap(matrix.viewRow(b)); } }; // reordering the columns of a 2-d matrix Swapper swapper = new Swapper() { public void swap(int a, int b) { matrix.viewColumn(a).swap(matrix.viewColumn(b)); } };

Version:

1.0, 10-Oct-99

Author:

wolfgang.hoschek@cern.ch

See Also:

Swapper, GenericSorting

Constructor Summary

Constructors

Modifier	Constructor and Description
protected	GenericPermuting() Makes this class non instantiable, but still let's others inherit from it.

Method Summary

Methods

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.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

GenericPermuting

protected GenericPermuting()

Makes this class non instantiable, but still let's others inherit from it.

Method Detail

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 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]

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 < 1 || N < 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

public static void permute(int[] indexes,
           Swapper swapper,
           int[] work)

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]<--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].

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

public 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]]. (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]<--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].

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

public static void permute(Object[] list,
           int[] indexes)

A non-generic variant of reordering, specialized for Object[], same semantics. Quicker than generic reordering. Also for convenience (forget about the Swapper object).