001// ============================================================================
002//   Copyright 2006-2012 Daniel W. Dyer
003//
004//   Licensed under the Apache License, Version 2.0 (the "License");
005//   you may not use this file except in compliance with the License.
006//   You may obtain a copy of the License at
007//
008//       http://www.apache.org/licenses/LICENSE-2.0
009//
010//   Unless required by applicable law or agreed to in writing, software
011//   distributed under the License is distributed on an "AS IS" BASIS,
012//   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013//   See the License for the specific language governing permissions and
014//   limitations under the License.
015// ============================================================================
016package squidpony.squidmath;
017
018import java.io.Serializable;
019import java.util.ArrayList;
020import java.util.Collection;
021import java.util.Collections;
022import java.util.Iterator;
023import java.util.List;
024
025/**
026 * Permutation generator for generating all permutations for all sets up to
027 * 20 elements in size.  While 20 may seem a low limit, bear in mind that
028 * the number of permutations of a set of size n is n!  For a set of 21
029 * items, the number of permutations is bigger than can be stored in Java's
030 * 64-bit long integer data type.  Therefore it seems unlikely that you
031 * could ever generate, let alone process, all of the permutations in a
032 * reasonable time frame.  For this reason the implementation is optimised for
033 * sets of size 20 or less (this affords better performance by allowing primitive
034 * numeric types to be used for calculations rather than
035 * {@link java.math.BigInteger}).
036 * <br>
037 * Originally part of the <a href="http://maths.uncommons.org/">Uncommon Maths software package</a>.
038 * @param <T> The type of element that the permutation will consist of.
039 * @author Daniel Dyer (modified from the original version written by Michael
040 * Gilleland of Merriam Park Software -
041 * <a href="http://www.merriampark.com/perm.htm">http://www.merriampark.com/perm.htm</a>).
042 * @see CombinationGenerator
043 */
044public class PermutationGenerator<T> implements Iterable<List<T>>, Serializable
045{
046    private static final long serialVersionUID = 514276118639629743L;
047
048    private final T[] elements;
049    private final int[] permutationIndices;
050    private long remainingPermutations;
051    private long totalPermutations;
052
053
054    /**
055     * Permutation generator that generates all possible orderings of
056     * the elements in the specified set.
057     * @param elements The elements to permute; will be modified, so this should be copied beforehand
058     */
059    public PermutationGenerator(T[] elements)
060    {
061        if (elements.length > 20)
062        {
063            throw new IllegalArgumentException("Size must be less than or equal to 20.");
064        }
065        this.elements = elements;
066        permutationIndices = new int[elements.length];
067        totalPermutations = MathExtras.factorial(elements.length);
068        reset();
069    }
070
071
072    /**
073     * Permutation generator that generates all possible orderings of
074     * the elements in the specified set.
075     * @param elements The elements to permute.
076     * @param filler An array of T with the same length as elements; needed because GWT can't create a generic array.
077     */
078    @SuppressWarnings("unchecked")
079    public PermutationGenerator(Collection<T> elements, T[] filler)
080    {
081        this(elements.toArray(filler));
082    }
083
084
085    /**
086     * Resets the generator state.
087     */
088    public final void reset()
089    {
090        for (int i = 0; i < permutationIndices.length; i++)
091        {
092            permutationIndices[i] = i;
093        }
094        remainingPermutations = totalPermutations;
095    }
096
097
098    /**
099     * Returns the number of permutations not yet generated.
100     * @return The number of unique permutations still to be generated.
101     */
102    public long getRemainingPermutations()
103    {
104        return remainingPermutations;
105    }
106
107
108    /**
109     * Returns the total number of unique permutations that can be
110     * generated for the given set of elements.
111     * @return The total number of permutations.
112     */
113    public long getTotalPermutations()
114    {
115        return totalPermutations;
116    }
117
118    /**
119     * Returns the total number of unique permutations that can be
120     * generated for the given count of permute-able elements.
121     * Typically used with the static methods of this class that
122     * find permutation indices.
123     * @param count the number of elements (typically indices) you want to find a permutation of
124     * @return The total number of permutations.
125     */
126    public static long getTotalPermutations(int count)
127    {
128        return MathExtras.factorial(count);
129    }
130
131
132    /**
133     * Are there more permutations that have not yet been returned?
134     * @return true if there are more permutations, false otherwise.
135     */
136    public boolean hasMore()
137    {
138        return remainingPermutations > 0;
139    }
140
141
142    /**
143     * Generate the next permutation and return an array containing
144     * the elements in the appropriate order.  This overloaded method
145     * allows the caller to provide an array that will be used and returned.
146     * The purpose of this is to improve performance when iterating over
147     * permutations. This method allows a single array instance to be reused.
148     * @param destination Provides an array to use to create the
149     * permutation.  The specified array must be the same length as a
150     * permutation.  This is the array that will be returned, once
151     * it has been filled with the elements in the appropriate order.
152     * @return The next permutation as an array.
153     */
154    public T[] nextPermutationAsArray(T[] destination)
155    {
156        if (destination.length != elements.length)
157        {
158            throw new IllegalArgumentException("Destination array must be the same length as permutations.");
159        }
160        generateNextPermutationIndices();
161        // Generate actual permutation.
162        for (int i = 0; i < permutationIndices.length; i++)
163        {
164            destination[i] = elements[permutationIndices[i]];
165        }
166        return destination;
167    }
168
169
170    /**
171     * Generate the next permutation and return a list containing
172     * the elements in the appropriate order.
173     * @see #nextPermutationAsList(List)
174     * @return The next permutation as a list.
175     */
176    public List<T> nextPermutationAsList()
177    {
178        List<T> permutation = new ArrayList<T>(elements.length);
179        return nextPermutationAsList(permutation);
180    }
181
182
183    /**
184     * Generate the next permutation and return a list containing
185     * the elements in the appropriate order.  This overloaded method
186     * allows the caller to provide a list that will be used and returned.
187     * The purpose of this is to improve performance when iterating over
188     * permutations.  If the {@link #nextPermutationAsList()} method is
189     * used it will create a new list every time.  When iterating over
190     * permutations this will result in lots of short-lived objects that
191     * have to be garbage collected.  This method allows a single list
192     * instance to be reused in such circumstances.
193     * @param destination Provides a list to use to create the
194     * permutation.  This is the list that will be returned, once
195     * it has been filled with the elements in the appropriate order.
196     * @return The next permutation as a list.
197     */
198    public List<T> nextPermutationAsList(List<T> destination)
199    {
200        generateNextPermutationIndices();
201        // Generate actual permutation.
202        destination.clear();
203        for (int i : permutationIndices)
204        {
205            destination.add(elements[i]);
206        }
207        return destination;
208    }
209
210    /**
211     * Generate the indices into the elements array for the next permutation.  The
212     * algorithm is from Kenneth H. Rosen, Discrete Mathematics and its Applications,
213     * 2nd edition (NY: McGraw-Hill, 1991), p. 284)
214     */
215    private void generateNextPermutationIndices()
216    {
217        if (remainingPermutations == 0)
218        {
219            throw new IllegalStateException("There are no permutations remaining.  " +
220                                            "Generator must be reset to continue using.");
221        }
222        else if (remainingPermutations < totalPermutations)
223        {
224            // Find largest index j with permutationIndices[j] < permutationIndices[j + 1]
225            int j = permutationIndices.length - 2;
226            while (permutationIndices[j] > permutationIndices[j + 1])
227            {
228                j--;
229            }
230
231            // Find index k such that permutationIndices[k] is smallest integer greater than
232            // permutationIndices[j] to the right of permutationIndices[j].
233            int k = permutationIndices.length - 1;
234            while (permutationIndices[j] > permutationIndices[k])
235            {
236                k--;
237            }
238
239            // Interchange permutation indices.
240            int temp = permutationIndices[k];
241            permutationIndices[k] = permutationIndices[j];
242            permutationIndices[j] = temp;
243
244            // Put tail end of permutation after jth position in increasing order.
245            int r = permutationIndices.length - 1;
246            int s = j + 1;
247
248            while (r > s)
249            {
250                temp = permutationIndices[s];
251                permutationIndices[s] = permutationIndices[r];
252                permutationIndices[r] = temp;
253                r--;
254                s++;
255            }
256        }
257        --remainingPermutations;
258    }
259
260    private int[] getPermutationShift(T[] perm) {
261        int[] sh = new int[perm.length];
262        boolean[] taken = new boolean[perm.length];
263
264        for (int i = 0; i < perm.length - 1; i++) {
265            int ctr = -1;
266            for (int j = 0; j < perm.length; j++) {
267                if (!taken[j])
268                    ctr++;
269                if (perm[j] == elements[i]) {
270                    taken[j] = true;
271                    sh[i] = ctr;
272                    break;
273                }
274            }
275        }
276        return sh;
277    }
278
279    private int[] getPermutationShift(List<T> perm) {
280        int length = perm.size();
281        int[] sh = new int[length];
282        boolean[] taken = new boolean[length];
283
284        for (int i = 0; i < length - 1; i++) {
285            int ctr = -1;
286            for (int j = 0; j < length; j++) {
287                if (!taken[j])
288                    ctr++;
289                if (perm.get(j) == elements[i]) {
290                    taken[j] = true;
291                    sh[i] = ctr;
292                    break;
293                }
294            }
295        }
296        return sh;
297    }
298
299    /**
300     * Given an array of T that constitutes a permutation of the elements this was constructed with, finds the specific
301     * index of the permutation given a factoradic numbering scheme (not used by the rest of this class, except the
302     * decodePermutation() method). The index can be passed to decodePermutation to reproduce the permutation passed to
303     * this, or modified and then passed to decodePermutation(). Determines equality by identity, not by .equals(), so
304     * that equivalent values that have different references/identities can appear in the permuted elements.
305     * <br>
306     * Credit goes to user Joren on StackOverflow, http://stackoverflow.com/a/1506337
307     * @param perm an array of T that must be a valid permutation of this object's elements
308     * @return an encoded number that can be used to reconstruct the permutation when passed to decodePermutation()
309     */
310    public long encodePermutation(T[] perm)
311    {
312        long e = 0;
313        if(perm == null || perm.length != elements.length)
314            return e;
315        int[] shift = getPermutationShift(perm);
316        for (int i = 1; i < shift.length; i++) {
317            e += shift[i] * MathExtras.factorialsStart[i];
318        }
319        return e;
320    }
321
322    /**
323     * Given a List of T that constitutes a permutation of the elements this was constructed with, finds the specific
324     * index of the permutation given a factoradic numbering scheme (not used by the rest of this class, except the
325     * decodePermutation() method). The index can be passed to decodePermutation to reproduce the permutation passed to
326     * this, or modified and then passed to decodePermutation(). Determines equality by identity, not by .equals(), so
327     * that equivalent values that have different references/identities can appear in the permuted elements.
328     * <br>
329     * Credit goes to user Joren on StackOverflow, http://stackoverflow.com/a/1506337
330     * @param perm a List of T that must be a valid permutation of this object's elements
331     * @return an encoded number that can be used to reconstruct the permutation when passed to decodePermutation()
332     */
333    public long encodePermutation(List<T> perm)
334    {
335        long e = 0;
336        if(perm == null || perm.size() != elements.length)
337            return e;
338        int[] shift = getPermutationShift(perm);
339        for (int i = 1; i < shift.length; i++) {
340            e += shift[i] * MathExtras.factorialsStart[i];
341        }
342        return e;
343    }
344
345    private static int[] getPermutationShift(int[] perm) {
346        int[] sh = new int[perm.length];
347        boolean[] taken = new boolean[perm.length];
348
349        for (int i = 0; i < perm.length - 1; i++) {
350            int ctr = -1;
351            for (int j = 0; j < perm.length; j++) {
352                if (!taken[j])
353                    ctr++;
354                if (perm[j] == i) {
355                    taken[j] = true;
356                    sh[i] = ctr;
357                    break;
358                }
359            }
360        }
361        return sh;
362    }
363    /**
364     * Given an array of int that constitutes a permutation of indices, where no element in perm is repeated and all
365     * ints are less than perm.length, finds the specific index of the permutation given a factoradic numbering scheme
366     * (not used by the rest of this class, except the decodePermutation() method). The index can be passed to
367     * decodePermutation to reproduce the index permutation passed to this, or modified and then passed to
368     * decodePermutation().
369     * <br>
370     * Credit goes to user Joren on StackOverflow, http://stackoverflow.com/a/1506337
371     * @param perm an array of int that is a permutation of the range from 0 (inclusive) to perm.length (exclusive)
372     * @return an encoded number that can be used to reconstruct the permutation when passed to decodePermutation()
373     */
374    public static long encodePermutation(int[] perm)
375    {
376        long e = 0;
377        if(perm == null || perm.length <= 0)
378            return e;
379        int[] shift = getPermutationShift(perm);
380        for (int i = 1; i < shift.length; i++) {
381            e += shift[i] * MathExtras.factorialsStart[i];
382        }
383        return e;
384    }
385
386
387    private int[] factoradicDecode(long e)
388    {
389        int[] sequence = new int[elements.length];
390        int base = 2;
391
392        for (int k = 1; k < elements.length; k++)
393        {
394            sequence[elements.length - 1 - k] = (int)(e % base);
395            e /= base;
396
397            base++;
398        }
399        return sequence;
400    }
401
402    private static int[] factoradicDecode(long e, int count)
403    {
404        int[] sequence = new int[count];
405        int base = 2;
406
407        for (int k = 1; k < count; k++)
408        {
409            sequence[count - 1 - k] = (int)(e % base);
410            e /= base;
411
412            base++;
413        }
414        return sequence;
415    }
416
417    /**
418     * Given a long between 0 and the total number of permutations possible (see getTotalPermutations() for how to access
419     * this) and an int count of how many indices to find a permutation of, returns an array with the permutation
420     * of the indices described by the long as a special (factoradic) index into the possible permutations. You can get
421     * an index for a specific permutation with encodePermutation() or by generating a random number between 0 and
422     * getTotalPermutations(), if you want it randomly.
423     * <br>
424     * Credit goes to user Joren on StackOverflow, http://stackoverflow.com/a/1506337
425     * @param encoded the index encoded as a long
426     * @param count an int between 1 and 20, inclusive, that will be the size of the returned array
427     * @return the looked-up permutation as an int array with length equal to count
428     */
429    public static int[] decodePermutation(long encoded, int count)
430    {
431        if(count <= 0)
432            return new int[0];
433        encoded %= MathExtras.factorial(count);
434        int[] sequence = factoradicDecode(encoded, count), destination = new int[count];
435        //char[] list = new char[] { 'a', 'b', 'c', 'd', 'e' }; //change for elements
436
437        //char[] permuted = new char[n]; //change for destination
438        boolean[] set = new boolean[count];
439
440        for (int i = 0; i < count; i++)
441        {
442            int s = sequence[i];
443            int remainingPosition = 0;
444            int index;
445
446            // Find the s'th position in the permuted list that has not been set yet.
447            for (index = 0; index < count; index++)
448            {
449                if (!set[index])
450                {
451                    if (remainingPosition == s)
452                        break;
453
454                    remainingPosition++;
455                }
456            }
457
458            destination[index] = i;
459            set[index] = true;
460        }
461        return destination;
462    }
463
464    /**
465     * Given a long between 0 and the total number of permutations possible (see getTotalPermutations() for how to access
466     * this) and an int count of how many indices to find a permutation of, returns an array with the permutation
467     * of the indices described by the long as a special (factoradic) index into the possible permutations. You can get
468     * an index for a specific permutation with encodePermutation() or by generating a random number between 0 and
469     * getTotalPermutations(), if you want it randomly. This variant adds an int to each item in the returned array,
470     * which may be useful if generating indices that don't start at 0.
471     * <br>
472     * Credit goes to user Joren on StackOverflow, http://stackoverflow.com/a/1506337
473     * @param encoded the index encoded as a long
474     * @param count an int between 1 and 20, inclusive, that will be the size of the returned array
475     * @param add an int to add to each item of the permutation
476     * @return the looked-up permutation as an int array with length equal to count
477     */
478    public static int[] decodePermutation(long encoded, int count, int add)
479    {
480        int[] p = decodePermutation(encoded, count);
481        for (int i = 0; i < p.length; i++) {
482            p[i] += add;
483        }
484        return p;
485    }
486
487    /**
488     * Given a long between 0 and the total number of permutations possible (see getTotalPermutations() for how to access
489     * this) and an array of T with the same length as the elements this was constructed with, fills the array with the
490     * permutation described by the long as a special (factoradic) index into the possible permutations. You can get an
491     * index for a specific permutation with encodePermutation() or by generating a random number between 0 and
492     * getTotalPermutations(), if you want it randomly.
493     * <br>
494     * Credit goes to user Joren on StackOverflow, http://stackoverflow.com/a/1506337
495     * @param encoded the index encoded as a long
496     * @param destination an array of T that must have equivalent length to the elements this was constructed with
497     * @return the looked-up permutation, which is the same value destination will be assigned
498     */
499    public T[] decodePermutation(long encoded, T[] destination)
500    {
501        if(destination == null)
502            return null;
503        encoded %= totalPermutations;
504        int[] sequence = factoradicDecode(encoded);
505        //char[] list = new char[] { 'a', 'b', 'c', 'd', 'e' }; //change for elements
506
507        //char[] permuted = new char[n]; //change for destination
508        boolean[] set = new boolean[elements.length];
509
510        for (int i = 0; i < elements.length; i++)
511        {
512            int s = sequence[i];
513            int remainingPosition = 0;
514            int index;
515
516            // Find the s'th position in the permuted list that has not been set yet.
517            for (index = 0; index < elements.length; index++)
518            {
519                if (!set[index])
520                {
521                    if (remainingPosition == s)
522                        break;
523
524                    remainingPosition++;
525                }
526            }
527
528            destination[index] = elements[i];
529            set[index] = true;
530        }
531        return destination;
532    }
533
534    /**
535     * Given a long between 0 and the total number of permutations possible (see getTotalPermutations() for how to access
536     * this), creates a List filled with the permutation described by the long as a special (factoradic) index into the
537     * possible permutations. You can get an index for a specific permutation with encodePermutation() or by generating a
538     * random number between 0 and getTotalPermutations(), if you want it randomly.
539     * <br>
540     * Credit goes to user Joren on StackOverflow, http://stackoverflow.com/a/1506337
541     * @param encoded the index encoded as a long
542     * @return a List of T that corresponds to the permutation at the encoded index
543     */
544    public List<T> decodePermutation(long encoded)
545    {
546        ArrayList<T> list = new ArrayList<T>(elements.length);
547        Collections.addAll(list, elements);
548        return decodePermutation(encoded, list);
549    }
550
551    /**
552     * Given a long between 0 and the total number of permutations possible (see getTotalPermutations() for how to access
553     * this) and a List of T with the same length as the elements this was constructed with, fills the List with the
554     * permutation described by the long as a special (factoradic) index into the possible permutations. You can get an
555     * index for a specific permutation with encodePermutation() or by generating a random number between 0 and
556     * getTotalPermutations(), if you want it randomly.
557     * <br>
558     * Credit goes to user Joren on StackOverflow, http://stackoverflow.com/a/1506337
559     * @param encoded the index encoded as a long
560     * @param destination a List of T that must have equivalent size to the elements this was constructed with
561     * @return the looked-up permutation, which is the same value destination will be assigned
562     */
563    public List<T> decodePermutation(long encoded, List<T> destination)
564    {
565        if(destination == null)
566            return null;
567        encoded %= totalPermutations;
568        int[] sequence = factoradicDecode(encoded);
569        //char[] list = new char[] { 'a', 'b', 'c', 'd', 'e' }; //change for elements
570
571        //char[] permuted = new char[n]; //change for destination
572        boolean[] set = new boolean[elements.length];
573
574        for (int i = 0; i < elements.length; i++)
575        {
576            int s = sequence[i];
577            int remainingPosition = 0;
578            int index;
579
580            // Find the s'th position in the permuted list that has not been set yet.
581            for (index = 0; index < elements.length; index++)
582            {
583                if (!set[index])
584                {
585                    if (remainingPosition == s)
586                        break;
587
588                    remainingPosition++;
589                }
590            }
591
592            destination.set(index, elements[i]);
593            set[index] = true;
594        }
595        return destination;
596    }
597    /**
598     * <p>Provides a read-only iterator for iterating over the permutations
599     * generated by this object.  This method is the implementation of the
600     * {@link Iterable} interface that permits instances of this class to be
601     * used with the new-style for loop.</p>
602     * <p>For example:</p>
603     * <pre>
604     * List&lt;Integer&gt; elements = Arrays.asList(1, 2, 3);
605     * PermutationGenerator&lt;Integer&gt; permutations = new PermutationGenerator(elements);
606     * for (List&lt;Integer&gt; p : permutations)
607     * {
608     *     // Do something with each permutation.
609     * }
610     * </pre>
611     * @return An iterator.
612     * @since 1.1
613     */
614    public Iterator<List<T>> iterator()
615    {
616        return new Iterator<List<T>>()
617        {
618            public boolean hasNext()
619            {
620                return hasMore();
621            }
622
623
624            public List<T> next()
625            {
626                return nextPermutationAsList();
627            }
628
629
630            public void remove()
631            {
632                throw new UnsupportedOperationException("Iterator does not support removal.");
633            }
634        };
635    }
636}