KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > jgrapht > experimental > permutation > CompoundPermutationIter


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  * CompoundPermutationIter.java
27  * -----------------
28  * (C) Copyright 2005-2006, by Assaf Lehr and Contributors.
29  *
30  * Original Author: Assaf Lehr
31  * Contributor(s): -
32  *
33  * $Id: CompoundPermutationIter.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 import org.jgrapht.util.*;
43
44
45 /**
46  * For permutation like this:
47  * <li>1,2 are the same eq.group (numbers)
48  * <li>a,b are og the same eq.group (letters)
49  * <li>'$' is of its own eq. group (signs) Let the order of the group be
50  * (arbitrary): signs,numbers,letters (note that for performance reasons, this
51  * arbitrary order is the worst! see Performance section below)
52  *
53  * <p>These are the possible compound perm: [$,1,2,a,b,c]
54  *
55  * <p>[$,1,2,a,c,b]
56  *
57  * <p>[$,1,2,b,a,c]
58  *
59  * <p>[$,1,2,b,c,a]
60  *
61  * <p>[$,1,2,c,a,b]
62  *
63  * <p>[$,1,2,c,b,a]
64  *
65  * <p>[$,2,1,a,b,c]
66  *
67  * <p>[$,2,1,a,c,b]
68  *
69  * <p>[$,2,1,b,a,c]
70  *
71  * <p>[$,2,1,b,c,a]
72  *
73  * <p>[$,2,1,c,a,b]
74  *
75  * <p>[$,2,1,c,b,a]
76  *
77  * <p>The overall number is the product of the factorials of each eq. group
78  * size; in our example : (1!)x(2!)x(3!)=1x2x6=12. Using the constructor with
79  * eq.group sizes and initial order [1,2,3], the result permutations are
80  * retrieved as numbers in an array, where [0,1,2,3,4,5] means [$,1,2,a,b,c]:
81  *
82  * <p>[0,1,2,3,5,4]
83  *
84  * <p>[0,1,2,4,3,5]
85  *
86  * <p>etc. etc., till:
87  *
88  * <p>[0,2,1,5,4,3] means [$,2,1,c,b,a]
89  *
90  * <p>
91  * <p><i>Performance:</i> The implementation tries to advance each time the
92  * group zero, if it does not succeed, it tries the next group (1,2 and so on),
93  * so: try to put the largest group as the first groups, UNLIKE the example.
94  * Performance-wise it is better to do [a,b,c,1,2,$] .The effect is improvement
95  * by constant (for example, by 2)
96  *
97  * @author Assaf
98  * @since May 30, 2005
99  */
100 public class CompoundPermutationIter
101     implements ArrayPermutationsIter, Iterator
102 {
103
104     //~ Instance fields -------------------------------------------------------
105
106     IntegerPermutationIter [] permArray;
107
108     /**
109      * on the example 1+2+3=6
110      */
111     private int totalPermArraySize;
112
113     /**
114      * The overall number is the product of the factorial of each eq. group
115      * size.
116      */
117     private int max;
118
119     private int iterCounter = 0;
120
121     //~ Constructors ----------------------------------------------------------
122
123     /**
124      * For the class example, use [1,2,2]. order matters! (performance-wise too)
125      *
126      * @param equalityGroupsSizesArray
127      */
128     public CompoundPermutationIter(int [] equalityGroupsSizesArray)
129     {
130         init(equalityGroupsSizesArray);
131     }
132
133     //~ Methods ---------------------------------------------------------------
134
135     /**
136      * Creates an IntegerPermutationIter class per equalityGroup with different
137      * integers.
138      *
139      * @param equalityGroupsSizesArray
140      */
141     private void init(int [] equalityGroupsSizesArray)
142     {
143         this.permArray =
144             new IntegerPermutationIter [equalityGroupsSizesArray.length];
145
146         int counter = 0;
147         this.max = 1; // each time , multiply by factorail(eqGroupSize)
148 for (
149             int eqGroup = 0;
150             eqGroup < equalityGroupsSizesArray.length;
151             eqGroup++) {
152             // create an array of eq.group size filled with values
153 // of counter, counter+1, ... counter+size-1
154 int currGroupSize = equalityGroupsSizesArray[eqGroup];
155             int [] currArray = new int [currGroupSize];
156             for (int i = 0; i < currGroupSize; i++) {
157                 currArray[i] = counter;
158                 counter++;
159             }
160             this.permArray[eqGroup] = new IntegerPermutationIter(currArray);
161             this.permArray[eqGroup].getNext(); // first iteration return the
162 // source
163
164             // each time , multiply by factorail(eqGroupSize)
165 this.max *= MathUtil.factorial(currGroupSize);
166         }
167         this.totalPermArraySize = counter;
168
169         // calc max
170 }
171
172     public Object JavaDoc next()
173     {
174         return getNext();
175     }
176
177     /**
178      * Iteration may be one of these two: 1. the last group advances by one
179      * iter, all else stay. 2. the last group cannot advance , so it restarts
180      * but telling the group after it to advance (done recursively till some
181      * group can advance)
182      */
183     public int [] getNext()
184     {
185         if (this.iterCounter == 0) {
186             // just return it , without change
187 this.iterCounter++;
188             return getPermAsArray();
189         }
190
191         int firstGroupCapableOfAdvancing = -1;
192         int currGroupIndex = 0; //
193 while (firstGroupCapableOfAdvancing == -1) {
194             IntegerPermutationIter currGroup = this.permArray[currGroupIndex];
195
196             if (currGroup.hasNext()) {
197                 currGroup.getNext();
198
199                 // restart all that we passed on
200 for (int i = 0; i < currGroupIndex; i++) {
201                     restartPermutationGroup(i);
202                 }
203                 firstGroupCapableOfAdvancing = currGroupIndex;
204             }
205
206             currGroupIndex++;
207             if (currGroupIndex >= this.permArray.length) {
208                 break;
209             }
210         }
211
212         this.iterCounter++;
213
214         if (firstGroupCapableOfAdvancing == -1) {
215             // nothing found. we finished all iterations
216 return null;
217         } else {
218             int [] tempArray = getPermAsArray();
219             return tempArray;
220         }
221     }
222
223     /**
224      * Creates and returns a new array which consists of the eq. group current
225      * permutation arrays. For example, in the 10th iter ([$,2,1,b,c,a]) The
226      * permutations current statuses is [0] [2,1] [4,5,3] so retrieve
227      * [0,2,1,4,5,3]
228      */
229     public int [] getPermAsArray()
230     {
231         int [] resultArray = new int [this.totalPermArraySize];
232         int counter = 0;
233         for (
234             int groupIndex = 0;
235             groupIndex < this.permArray.length;
236             groupIndex++) {
237             int [] currPermArray = this.permArray[groupIndex].getCurrent();
238             System.arraycopy(
239                 currPermArray,
240                 0,
241                 resultArray,
242                 counter,
243                 currPermArray.length);
244             counter += currPermArray.length;
245         }
246         return resultArray;
247     }
248
249     /**
250      * Restarts by creating a new one instead.
251      *
252      * @param groupIndex
253      */
254     private void restartPermutationGroup(int groupIndex)
255     {
256         int [] oldPermArray = this.permArray[groupIndex].getCurrent();
257         Arrays.sort(oldPermArray);
258         this.permArray[groupIndex] = new IntegerPermutationIter(oldPermArray);
259         this.permArray[groupIndex].getNext();
260     }
261
262     public boolean hasNext()
263     {
264         boolean result;
265         if (this.iterCounter < this.max) {
266             result = true;
267         } else {
268             result = false;
269         }
270         return result;
271     }
272
273     public int getMax()
274     {
275         return max;
276     }
277
278     /* (non-Javadoc)
279      * @see ArrayPermutationsIter#nextPermutation()
280      */
281     public int [] nextPermutation()
282     {
283         return (int []) next();
284     }
285
286     /* (non-Javadoc)
287      * @see ArrayPermutationsIter#hasNextPermutaions()
288      */
289     public boolean hasNextPermutaions()
290     {
291         return hasNext();
292     }
293
294     /**
295      * UNIMPLEMENTED. always throws new UnsupportedOperationException
296      *
297      * @see java.util.Iterator#remove()
298      */
299     public void remove()
300     {
301         throw new UnsupportedOperationException JavaDoc();
302     }
303 }
304
Popular Tags