1 /*
2 * Permuter.java
3 *
4 * Created on 3-mar-2006, based on Permutations from Tim Tyler.
5 *
6 * Copyright (C) 2005 Hendrik Maryns <hendrik@sfs.uni-tuebingen.de>.
7 *
8 * This program is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU General Public License
10 * as published by the Free Software Foundation; either version 2
11 * of the License, or (at your option) any later version.
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
19 */
20 package combinatorics;
21
22 /**
23 * A class that permutes a given array of elements. It is an iterator that
24 * returns all permutations, successively. Thanks to Tim Tyler for the
25 * original implementation <a href="http://mandala.co.uk/permutations/">
26 * http://mandala.co.uk/permutations/</a>.
27 *
28 * @author <a href="mailto:hendrik.maryns@uni-tuebingen.de">Hendrik Maryns</a>
29 * @param <T> The type of the array to be permuted.
30 */
31 public final class Permuter<T> extends CombinatoricOperator<T> {
32
33 /**
34 * Initialise a new permuter, with given array of elements to permute.
35 *
36 * @param elements
37 * The elements to permute.
38 * @post The total number is set to the factorial of the number of
39 * elements.
40 * | new.getTotal() == factorial(elements.length)
41 * @post The number of permutations left is set to the total number.
42 * | new.getNumLeft() == new.getTotal()
43 */
44 public Permuter(final T[] elements) {
45 super(elements, elements.length);
46 }
47
48 /**
49 * Compute the total number of elements to return.
50 *
51 * @return The factorial of the number of elements.
52 * | result == factorial(n)
53 * @see CombinatoricOperator#initialiseTotal(int, int)
54 */
55 @Override
56 protected double initialiseTotal(final int n, final int r) {
57 return CombinatoricOperator.factorial(n);
58 }
59
60 /**
61 * Compute the next array of indices.
62 *
63 * @see CombinatoricOperator#computeNext()
64 */
65 @Override
66 protected void computeNext() {
67 // find the rightmost element that is smaller than the element at its right
68 int i = this.indices.length - 1;
69 while (this.indices[i - 1] >= this.indices[i]) {
70 i = i - 1;
71 }
72 // find the rightmost element that is bigger then the other one
73 int j = this.indices.length;
74 while (this.indices[j - 1] <= this.indices[i - 1]) {
75 j = j - 1;
76 }
77 // swap them (always is i < j)
78 this.swap(i - 1, j - 1);
79 // now the elements at the right of i are in descending order, so reverse them all
80 i++;
81 j = this.indices.length;
82 while (i < j) {
83 this.swap(i - 1, j - 1);
84 i++;
85 j--;
86 }
87 // TODO: try other algorithms, see http://www.cut-the-knot.org/Curriculum/Combinatorics/JohnsonTrotter.shtml
88 }
89
90 /**
91 * Swap the elements at positions a and b, both from the index array and
92 * from the element array.
93 *
94 * @param a, b
95 * The indices of the elements to be swapped.
96 * @post The elements at indices a and b of the array of indices are
97 * swapped.
98 * | new.indexes[a] = indexes[b]
99 * | new.indexes[b] = indexes[a]
100 */
101 private void swap(final int a, final int b) {
102 final int temp = this.indices[a];
103 this.indices[a] = this.indices[b];
104 this.indices[b] = temp;
105 }
106
107
108 // protected int initialiseTotal(int n, int r) {
109 // throw new UnsupportedOperationException("Not supported yet.");
110 //}
111
112 }