1 /*
2 * Combinator.java
3 *
4 * Created on 3-mrt-2006, based on CombinationGenerator from Michael Gilleland.
5 *
6 * Copyright (C) 2006 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 sequentially returns all combinations of a certain number out of
24 * an array of given elements. Thanks to Michael Gillegand for the base
25 * implementation: <a href="http://www.merriampark.com/comb.htm">
26 * http://www.merriampark.com/comb.htm</a>.
27 *
28 * @author <a href="mailto:hendrik.maryns@uni-tuebingen.de">Hendrik Maryns</a>
29 * @param <T> The type of the elements of which combinations are to be
30 * returned.
31 */
32 public final class Combinator<T> extends CombinatoricOperator<T> {
33
34 /**
35 * Initialise a new Combinator, with given elements and size of the arrays
36 * to be returned.
37 *
38 * @param elements
39 * The elements of which combinations have to be computed.
40 * @param r
41 * The size of the combinations to compute.
42 * @pre r should not be greater than the length of the elements, and
43 * not smaller than 0.
44 * | 0 <= r <= elements.length
45 * @post The total number of iterations is set to the factorial of the
46 * number of elements divided by the factorials of the size of the
47 * combinations and the number of elements minus the size of the
48 * combinations. That is, with the number of elements = n and the
49 * size of the combinations = r:
50 * n n!
51 * ( ) = ---------
52 * r (n-r)!r!
53 * | new.getTotal() == factorial(elements.length).divide(
54 * | factorial(r).multiply(factorial(elements.length-r))
55 * @post The number of combinations left is set to the total number.
56 * | new.getNumLeft() == new.getTotal()
57 */
58 public Combinator(final T[] elements, final int r) {
59 super(elements, r);
60 assert r <= elements.length;
61 }
62
63 /**
64 * Compute the total number of elements to return.
65 *
66 * @return The factorial of the number of elements divided by the
67 * factorials of the size of the combinations and the number of
68 * elements minus the size of the combinations.
69 * That is, with the number of elements = n and the size of the
70 * combinations = r:
71 * n n!
72 * ( ) = ---------
73 * r (n-r)!r!
74 * @see CombinatoricOperator#initialiseTotal(int, int)
75 */
76
77 @Override
78 protected double initialiseTotal(final int n, final int r) {
79 final double nFact = CombinatoricOperator.factorial(n);
80 final double rFact = CombinatoricOperator.factorial(r);
81 final double nminusrFact = CombinatoricOperator.factorial(n - r);
82 return (nFact/(rFact*nminusrFact));
83 }
84
85 /**
86 * Compute the next array of indices.
87 *
88 * @see CombinatoricOperator#computeNext()
89 */
90
91 protected void computeNext() {
92 final int r = this.indices.length;
93 int i = r - 1;
94 final int n = this.elements.length;
95 while((i>=0) && (this.indices[i] == n - r + i)) {
96 i--;
97 }
98 if(i>=0){
99 this.indices[i] = this.indices[i] + 1;
100 for (int j = i + 1; j < r; j++) {
101 this.indices[j] = this.indices[i] + j - i;
102 }
103 // TODO: understand this.
104 }
105 }
106
107 }