2 * Copyright (C) 2015, United States Government, as represented by the
3 * Administrator of the National Aeronautics and Space Administration.
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
10 * http://www.apache.org/licenses/LICENSE-2.0.
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.
18 package gov.nasa.jpf.util;
20 import java.io.PrintStream;
23 * base type for permutation generators
25 public abstract class PermutationGenerator {
27 protected final int nElements;
29 protected int[] permutation; // array containing permutation
31 protected long nPermutations;
32 protected long nGenerated;
34 protected PermutationGenerator (int nElements){
35 this.nElements = nElements;
36 nPermutations = computeNumberOfPermutations();
41 protected void initPermutations (){
42 permutation = new int[nElements];
44 // initialize element array in order, starting with firstIdx
45 for (int i=0; i<nElements; i++){
52 protected abstract long computeNumberOfPermutations();
53 public abstract void reset();
55 public long getNumberOfPermutations(){
59 public long getNumberOfGeneratedPermutations(){
63 static void swap(int[] a, int i, int j){
70 * for debugging purposes
72 public void printOn (PrintStream ps){
73 printOn( ps, nGenerated, permutation);
76 public static void printOn (PrintStream ps, long nGenerated, int[] perm){
77 ps.printf("%2d: [", nGenerated);
78 for (int k=0; k<perm.length; k++){
79 if (k > 0) ps.print(',');
86 //--- the public iteration interface, following Iterator
87 public boolean hasNext(){
88 return (nGenerated < nPermutations);
92 * return the next permutation or throw a NoSuchElementException if there is none.
94 * NOTE - this does not guarantee to return a different object on each call,
95 * i.e. the caller has to clone if the result is stored directly
97 public abstract int[] next(); // the work horse, throws NoSuchElementException