cern.colt

## Class GenericPermuting

- java.lang.Object
- - cern.colt.GenericPermuting

-     public class GenericPermuting
      extends java.lang.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
  See Also:
    `Swapper`, `GenericSorting`

- - ### 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(java.lang.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

    - #### 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:
        `java.lang.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(java.lang.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).

Jump to the Colt Homepage