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

   1 /*
   2  * Copyright (C) 2015, 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 import java.util.Random;
  22
  23 /**
  24  * a permutation generator that uses the Fisher-Yates shuffle
  25  * (Durstenfeld, R. (July 1964). "Algorithm 235: Random permutation".
  26  * Communications of the ACM 7 (7): 420)
  27  *
  28  * use this if TotalPermutations would be too large and PairPermutations
  29  * not enough
  30  */
  31 public class RandomPermutationGenerator extends PermutationGenerator {
  32
  33   protected int seed;
  34   protected Random rand;
  35
  36   protected int[] orig;
  37
  38   public RandomPermutationGenerator (int nElements, int nPermutations, int seed){
  39     super(nElements);
  40     this.nPermutations = nPermutations;
  41     rand = new Random(seed);
  42     orig = permutation.clone();
  43   }
  44
  45   @Override
  46   protected long computeNumberOfPermutations() {
  47     return nPermutations; // it's input (set)
  48   }
  49
  50   @Override
  51   public void reset() {
  52     initPermutations();
  53     rand = new Random(seed);
  54     nGenerated = 0;
  55   }
  56
  57   @Override
  58   public int[] next() {
  59     if (nGenerated == 0){
  60       nGenerated = 1;
  61       return permutation;
  62
  63     } else if (nGenerated < nPermutations){
  64       permutation = orig.clone();
  65       for (int i=0; i<nElements; i++){
  66         int r = i + rand.nextInt( nElements-i);  // i <= r < nElements-1
  67         swap(permutation, r, i);
  68       }
  69       nGenerated++;
  70       return permutation;
  71
  72     } else {
  73       throw new NoSuchElementException();
  74     }
  75   }
  76 }