IntegerPermutationIter


1   /* ==========================================
2    * JGraphT : a free Java graph-theory library
3    * ==========================================
4    *
5    * Project Info:  http://jgrapht.sourceforge.net/
6    * Project Creator:  Barak Naveh (http://sourceforge.net/users/barak_naveh)
7    *
8    * (C) Copyright 2003-2006, by Barak Naveh and Contributors.
9    *
10   * This library is free software; you can redistribute it and/or modify it
11   * under the terms of the GNU Lesser General Public License as published by
12   * the Free Software Foundation; either version 2.1 of the License, or
13   * (at your option) any later version.
14   *
15   * This library is distributed in the hope that it will be useful, but
16   * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
17   * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
18   * License for more details.
19   *
20   * You should have received a copy of the GNU Lesser General Public License
21   * along with this library; if not, write to the Free Software Foundation,
22   * Inc.,
23   * 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
24   */
25  /* -----------------
26   * IntegerPermutationIter.java
27   * -----------------
28   * (C) Copyright 2005-2006, by Assaf Lehr and Contributors.
29   *
30   * Original Author:  Assaf Lehr
31   * Contributor(s):   -
32   *
33   * $Id: IntegerPermutationIter.java 504 2006-07-03 02:37:26Z perfecthash $
34   *
35   * Changes
36   * -------
37   */
38  package org.jgrapht.experimental.permutation;
39  
40  import java.util.*;
41  
42  
43  /**
44   * Iterates through permutations of N elements.
45   * <li>use getNext() to get the next permutation order,  for example(N=4):
46   * perm0=[1,2,3,4] perm1=[1,2,4,3] perm2=[1,3,2,4] .
47   * <li>use hasNext() or verify by counter<getTotalNumberOfPermutations () that
48   * you do not overflow the max number. RunTimeException will be thrown if you
49   * do. Getting the next permutation is done in O(N) Note: This class is not
50   * thread safe.
51   *
52   * @author Assaf
53   * @since May 20, 2005
54   */
55  public class IntegerPermutationIter
56      implements Iterator, ArrayPermutationsIter
57  {
58  
59      //~ Instance fields -------------------------------------------------------
60  
61      private int [] Value;
62      private int N;
63      private long permutationCounter;
64      private boolean endWasReached = false;
65      private boolean wasNextValueCalculatedAlready = false;
66  
67      /**
68       * Will hold the current value. Will be changed only by getNext()
69       */
70      private int [] currentValueBackup;
71  
72      //~ Constructors ----------------------------------------------------------
73  
74      /**
75       * Creates an array of size N with elements 1,2,...,n-1 Useful for
76       * describing regular permutations. See IntegerPermutationIter(int[] array)
77       * for the other kind of permutations; efficency of initiation is O(N)
78       *
79       * @param N
80       */
81      public IntegerPermutationIter(int N)
82      {
83          int [] newArray = new int [N];
84  
85          // fill the array with 1,2,3...
86          for (int i = 0; i < newArray.length; i++) {
87              newArray[i] = i;
88          }
89          init(newArray);
90      }
91  
92      /**
93       * Uses a predefined array (sorted), for example: [3,1,1,2,1]-->[1,1,1,2,3];
94       * note that there are much less than 5! premutations here, because of the
95       * repetitive 1s.
96       *
97       * @param array creates a copy of it (so sort / later changes will not
98       *              matter)
99       */
100     public IntegerPermutationIter(int [] array)
101     {
102         int [] newArray = new int [array.length];
103         System.arraycopy(array, 0, newArray, 0, array.length);
104         Arrays.sort(newArray);
105         init(newArray);
106     }
107 
108     //~ Methods ---------------------------------------------------------------
109 
110     private void init(int [] array)
111     {
112         this.N = array.length;
113         this.Value = array;
114         this.currentValueBackup = this.Value;
115         permutationCounter = 0;
116     }
117 
118     /**
119      * Swaps by array indexes
120      *
121      * @param i
122      * @param j
123      */
124     private void swap(int i, int j)
125     {
126         int temp = this.Value[i];
127         this.Value[i] = this.Value[j];
128         this.Value[j] = temp;
129     }
130 
131     private int [] arrayClone(int [] sourceArray)
132     {
133         int [] destArray = new int [sourceArray.length];
134         System.arraycopy(sourceArray, 0, destArray, 0, sourceArray.length);
135         return destArray;
136     }
137 
138     private int [] getNextStartingWith2()
139     {
140         permutationCounter++;
141         int i = N - 1;
142 
143         if (i <= 0) // may happen only on N<=1
144         {
145             this.endWasReached = true;
146             return null;
147         }
148 
149         /** while (Value[i-1] >= Value[i])
150           {
151           i = i-1;
152           }*/
153         while (Value[i - 1] >= Value[i]) {
154             i = i - 1;
155             if (i == 0) {
156                 this.endWasReached = true;
157                 return null;
158             }
159         }
160 
161         int j = N;
162 
163         while (Value[j - 1] <= Value[i - 1]) {
164             j = j - 1;
165         }
166 
167         swap(i - 1, j - 1); // swap values at positions (i-1) and (j-1)
168 
169         i++;
170         j = N;
171 
172         while (i < j) {
173             swap(i - 1, j - 1);
174             i++;
175             j--;
176         }
177         return this.Value;
178     }
179 
180     /**
181      * Efficiency: O(N) implementation, try to take the next!
182      */
183     public boolean hasNext()
184     {
185         if (
186             (this.permutationCounter == 0)
187             || (this.wasNextValueCalculatedAlready)) {
188             return true;
189         } else if (this.endWasReached) {
190             return false;
191         }
192 
193         boolean result = true;
194         // calculate the next value into this.value  save the current result.
195         // in the end swap the arrays
196         // there is no way to know when to stop , but the out-of-bound
197         /*  try
198          *  {
199          *      this.wasNextValueCalculatedAlready=true;
200          *      getNextStartingWith2();
201          *  }
202          *  catch (ArrayIndexOutOfBoundsException outOfBoundException)
203          *  {
204          *      endWasReached=true;
205          *      result=false;
206          *  }*/
207 
208         getNextStartingWith2();
209         this.wasNextValueCalculatedAlready = true;
210         if (endWasReached) {
211             return false;
212         }
213 
214         //////////////////////////////
215         return result;
216     }
217 
218     public Object   next()
219     {
220         return getNext();
221     }
222 
223     /**
224      * Facade. use it with getNext. efficency: O(N)
225      *
226      * @return a new Array with the permutatation order. for example:
227      *         perm0=[1,2,3,4] perm1=[1,2,4,3] perm2=[1,3,2,4]
228      */
229     public int [] getNext()
230     {
231         if (!hasNext()) {
232             throw new RuntimeException  (
233                 "IntegerPermutationIter exceeds the total number of permutaions."
234                 + " Suggestion: do a check with hasNext() , or count till getTotalNumberOfPermutations"
235                 + " before using getNext()");
236         }
237 
238         // if it is the first one , return original
239         int [] internalArray;
240         if (this.permutationCounter == 0) {
241             this.permutationCounter++;
242             internalArray = this.Value;
243         } else {
244             // if hasNext() has precaclulated it , take this value.
245             if (this.wasNextValueCalculatedAlready) {
246                 internalArray = this.Value;
247                 this.wasNextValueCalculatedAlready = false;
248             } else {
249                 internalArray = getNextStartingWith2();
250                 if (this.endWasReached) {
251                     return null;
252                 }
253             }
254         }
255         this.currentValueBackup = arrayClone(internalArray);
256         return arrayClone(internalArray);
257     }
258 
259     public int [] getCurrent()
260     {
261         return arrayClone(this.currentValueBackup);
262     }
263 
264     /**
265      * Utility method to convert the array into a string examples: [] [0]
266      * [0,1][1,0]
267      *
268      * @param array
269      */
270     public String   toString(int [] array)
271     {
272         if (array.length <= 0) {
273             return "[]";
274         }
275         StringBuffer   stBuffer = new StringBuffer  ("[");
276         for (int i = 0; i < (array.length - 1); i++) {
277             stBuffer.append(array[i]).append(",");
278         }
279         stBuffer.append(array[array.length - 1]).append("]");
280         return stBuffer.toString();
281     }
282 
283     /**
284      * UNIMPLEMENTED. always throws new UnsupportedOperationException
285      *
286      * @see java.util.Iterator#remove()
287      */
288     public void remove()
289     {
290         throw new UnsupportedOperationException  ();
291     }
292 
293     /* (non-Javadoc)
294      * @see ArrayPermutationsIter#nextPermutation()
295      */
296     public int [] nextPermutation()
297     {
298         return (int []) next();
299     }
300 
301     /* (non-Javadoc)
302      * @see ArrayPermutationsIter#hasNextPermutaions()
303      */
304     public boolean hasNextPermutaions()
305     {
306         return hasNext();
307     }
308 }
309
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags