Mercurial > hg > Members > kono > jpf-core

annotate src/main/gov/nasa/jpf/util/RandomPermutationGenerator.java @ 5:1ba6ea44e5f9

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
4
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
1 /*
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
2 * Copyright (C) 2015, United States Government, as represented by the
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
3 * Administrator of the National Aeronautics and Space Administration.
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
4 * All rights reserved.
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
5 *
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
6 * The Java Pathfinder core (jpf-core) platform is licensed under the
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
7 * Apache License, Version 2.0 (the "License"); you may not use this file except
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
8 * in compliance with the License. You may obtain a copy of the License at
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
9 *
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
10 * http://www.apache.org/licenses/LICENSE-2.0.
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
11 *
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
12 * Unless required by applicable law or agreed to in writing, software
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
13 * distributed under the License is distributed on an "AS IS" BASIS,
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
15 * See the License for the specific language governing permissions and
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
16 * limitations under the License.
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
17 */
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
18 package gov.nasa.jpf.util;
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
19
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
20 import java.util.NoSuchElementException;
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
21 import java.util.Random;
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
22
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
23 /**
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
24 * a permutation generator that uses the Fisher-Yates shuffle
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
25 * (Durstenfeld, R. (July 1964). "Algorithm 235: Random permutation".
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
26 * Communications of the ACM 7 (7): 420)
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
27 *
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
28 * use this if TotalPermutations would be too large and PairPermutations
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
29 * not enough
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
30 */
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
31 public class RandomPermutationGenerator extends PermutationGenerator {
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
32
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
33 protected int seed;
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
34 protected Random rand;
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
35
5
1ba6ea44e5f9 slight fix of RandomPermutationGenerator, which should re-shuffle the original
Peter Mehlitz <pcmehlitz@gmail.com>
parents: 4
diff changeset
36 protected int[] orig;
1ba6ea44e5f9 slight fix of RandomPermutationGenerator, which should re-shuffle the original
Peter Mehlitz <pcmehlitz@gmail.com>
parents: 4
diff changeset
37
4
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
38 public RandomPermutationGenerator (int nElements, int nPermutations, int seed){
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
39 super(nElements);
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
40 this.nPermutations = nPermutations;
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
41 rand = new Random(seed);
5
1ba6ea44e5f9 slight fix of RandomPermutationGenerator, which should re-shuffle the original
Peter Mehlitz <pcmehlitz@gmail.com>
parents: 4
diff changeset
42 orig = permutation.clone();
4
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
43 }
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
44
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
45 @Override
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
46 protected long computeNumberOfPermutations() {
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
47 return nPermutations; // it's input (set)
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
48 }
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
49
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
50 @Override
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
51 public void reset() {
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
52 initPermutations();
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
53 rand = new Random(seed);
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
54 nGenerated = 0;
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
55 }
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
56
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
57 @Override
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
58 public int[] next() {
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
59 if (nGenerated == 0){
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
60 nGenerated = 1;
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
61 return permutation;
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
62
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
63 } else if (nGenerated < nPermutations){
5
1ba6ea44e5f9 slight fix of RandomPermutationGenerator, which should re-shuffle the original
Peter Mehlitz <pcmehlitz@gmail.com>
parents: 4
diff changeset
64 permutation = orig.clone();
4
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
65 for (int i=0; i<nElements; i++){
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
66 int r = i + rand.nextInt( nElements-i); // i <= r < nElements-1
5
1ba6ea44e5f9 slight fix of RandomPermutationGenerator, which should re-shuffle the original
Peter Mehlitz <pcmehlitz@gmail.com>
parents: 4
diff changeset
67 swap(permutation, r, i);
4
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
68 }
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
69 nGenerated++;
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
70 return permutation;
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
71
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
72 } else {
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
73 throw new NoSuchElementException();
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
74 }
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
75 }
d0a0ff1c0e10 added some infrastructure to pull-generate permutations (total, random and
Peter Mehlitz <pcmehlitz@gmail.com>
parents:
diff changeset
76 }