src/main/gov/nasa/jpf/util/UniqueRandomPermGenerator.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
  22 /**
  23  * a RandomPermutationGenerator that keeps track of previously produced values
  24  * to avoid duplicates.
  25  * Note this only makes sense for relatively small sample sizes, but then again
  26  * that is what RandomPermutationGenerators are used for (to avoid N!)
  27  */
  28 public class UniqueRandomPermGenerator extends RandomPermutationGenerator {
  29
  30   protected SortedArrayIntSet visited;
  31
  32   public UniqueRandomPermGenerator (int nElements, int nPermutations, int seed){
  33     super(nElements, nPermutations, seed);
  34
  35     visited = new SortedArrayIntSet();
  36     this.nPermutations = Math.min( TotalPermutationGenerator.computeNumberOfPermutations(nElements), nPermutations);
  37   }
  38
  39   public void reset(){
  40     super.reset();
  41     visited = new SortedArrayIntSet();
  42   }
  43
  44   public int[] next(){
  45     while (nGenerated < nPermutations){
  46       int[] p = super.next();
  47       int h = OATHash.hash(p);
  48
  49       if (visited.add(h)){
  50         return p;
  51       } else {
  52         nGenerated--; // that one didn't count, we already have seen it
  53       }
  54     }
  55     throw new NoSuchElementException();
  56   }
  57 }