src/main/gov/nasa/jpf/util/TotalPermutationGenerator.java

   1 /*
   2  * Copyright (C) 2014, United States Government, as represented by the
   3  * Administrator of the National Aeronautics and Space Administration.
   4  * All rights reserved.
   5  *
   6  * The Java Pathfinder core (jpf-core) platform is licensed under the
   7  * Apache License, Version 2.0 (the "License"); you may not use this file except
   8  * in compliance with the License. You may obtain a copy of the License at
   9  *
  10  *        http://www.apache.org/licenses/LICENSE-2.0.
  11  *
  12  * Unless required by applicable law or agreed to in writing, software
  13  * distributed under the License is distributed on an "AS IS" BASIS,
  14  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  15  * See the License for the specific language governing permissions and
  16  * limitations under the License.
  17  */
  18 package gov.nasa.jpf.util;
  19
  20 import java.util.NoSuchElementException;
  21
  22 /**
  23  * a pull mode generator for permutations that executes in constant space,
  24  * using Ives' algorithm (F. M. Ives: Permutation enumeration: four new
  25  * permutation algorithms, Comm. ACM, 19, 2, Feb 1976, pg. 68-72)
  26  *
  27  * NOTE - this is mostly here for completeness, since use of full permutations
  28  * in most cases is prohibitive due to N!
  29  */
  30 public class TotalPermutationGenerator extends PermutationGenerator {
  31
  32   protected int[] inverse; // inverse permutations array
  33
  34   public TotalPermutationGenerator (int nElements){
  35     super( nElements);
  36
  37     initInverse();
  38   }
  39
  40   void initInverse (){
  41     inverse = new int[nElements];
  42     for (int i=0; i<nElements; i++){
  43       inverse[i] = i;
  44     }
  45   }
  46
  47   @Override
  48   public void reset(){
  49     initPermutations();
  50     initInverse();
  51   }
  52
  53
  54   public static long computeNumberOfPermutations(int nElements){
  55     long n = 1;
  56     for (int i=1; i<=nElements; i++){
  57       n *= i;
  58     }
  59     return n;
  60   }
  61
  62   @Override
  63   protected long computeNumberOfPermutations(){
  64     return computeNumberOfPermutations(nElements);
  65   }
  66
  67   @Override
  68   public int[] next (){
  69     if (nGenerated == 0){
  70       nGenerated =1;
  71       return permutation;
  72
  73     } else {
  74       for (int lower=0, upper=nElements-1; upper > lower; lower++, upper--){
  75         int i = inverse[lower];
  76         int j = (i == upper) ? lower : i+1;
  77         int pj = permutation[j];
  78
  79         permutation[i] = pj;
  80         permutation[j] = lower;
  81
  82         inverse[lower] = j;
  83         inverse[pj] = i;
  84
  85         if ((permutation[lower] != lower) || (permutation[upper] != upper)){
  86           nGenerated++;
  87           return permutation;
  88         }
  89       }
  90       throw new NoSuchElementException();
  91     }
  92   }
  93 }