Mercurial > hg > Members > kono > jpf-core
view src/main/gov/nasa/jpf/util/RandomPermutationGenerator.java @ 5:1ba6ea44e5f9
slight fix of RandomPermutationGenerator, which should re-shuffle the original
array, not the previous permutation
author | Peter Mehlitz <pcmehlitz@gmail.com> |
---|---|
date | Thu, 05 Feb 2015 19:13:42 -0800 |
parents | d0a0ff1c0e10 |
children | 3a19eedcc13d |
line wrap: on
line source
/* * Copyright (C) 2015, United States Government, as represented by the * Administrator of the National Aeronautics and Space Administration. * All rights reserved. * * The Java Pathfinder core (jpf-core) platform is licensed under the * Apache License, Version 2.0 (the "License"); you may not use this file except * in compliance with the License. You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0. * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */ package gov.nasa.jpf.util; import java.util.NoSuchElementException; import java.util.Random; /** * a permutation generator that uses the Fisher-Yates shuffle * (Durstenfeld, R. (July 1964). "Algorithm 235: Random permutation". * Communications of the ACM 7 (7): 420) * * use this if TotalPermutations would be too large and PairPermutations * not enough */ public class RandomPermutationGenerator extends PermutationGenerator { protected int seed; protected Random rand; protected int[] orig; public RandomPermutationGenerator (int nElements, int nPermutations, int seed){ super(nElements); this.nPermutations = nPermutations; rand = new Random(seed); orig = permutation.clone(); } @Override protected long computeNumberOfPermutations() { return nPermutations; // it's input (set) } @Override public void reset() { initPermutations(); rand = new Random(seed); nGenerated = 0; } @Override public int[] next() { if (nGenerated == 0){ nGenerated = 1; return permutation; } else if (nGenerated < nPermutations){ permutation = orig.clone(); for (int i=0; i<nElements; i++){ int r = i + rand.nextInt( nElements-i); // i <= r < nElements-1 swap(permutation, r, i); } nGenerated++; return permutation; } else { throw new NoSuchElementException(); } } }