001 /**
002 * Copyright (c) 2010, SIB. All rights reserved.
003 *
004 * SIB (Swiss Institute of Bioinformatics) - http://www.isb-sib.ch Host -
005 * https://sourceforge.net/projects/javaprotlib/
006 *
007 * Redistribution and use in source and binary forms, with or without
008 * modification, are permitted provided that the following conditions are met:
009 * Redistributions of source code must retain the above copyright notice, this
010 * list of conditions and the following disclaimer. Redistributions in binary
011 * form must reproduce the above copyright notice, this list of conditions and
012 * the following disclaimer in the documentation and/or other materials provided
013 * with the distribution. Neither the name of the SIB/GENEBIO nor the names of
014 * its contributors may be used to endorse or promote products derived from this
015 * software without specific prior written permission.
016 *
017 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
018 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
019 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
020 * ARE DISCLAIMED. IN NO EVENT SHALL SIB/GENEBIO BE LIABLE FOR ANY DIRECT,
021 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
022 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
023 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
024 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
025 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
026 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
027 */
028 package org.expasy.jpl.commons.base.math;
029
030
031 import java.util.ArrayList;
032 import java.util.Arrays;
033 import java.util.List;
034 import org.apache.commons.collections15.Transformer;
035
036
037 /**
038 * Generate all combinations of p things among n.
039 *
040 * @author nikitin
041 *
042 * @version 1.0
043 *
044 */
045 public final class CombinationFactory implements
046 Transformer<int[], List<int[]>> {
047
048 public static CombinationFactory newInstance() {
049 return new CombinationFactory();
050 }
051
052 /**
053 * @throws IllegalArgumentException if invalid parameters.
054 */
055 public List<int[]> transform(int[] param) {
056 if (param.length != 2) {
057 throw new IllegalArgumentException("can only process two integers.");
058 }
059 return process(param[0], param[1]);
060 }
061
062 /**
063 * Generate all combinations of p elements among n.
064 *
065 * @param p p.
066 * @param n n.
067 * @return a list of combinations.
068 *
069 * @throws IllegalArgumentException if invalid parameters.
070 */
071 public List<int[]> process(final int p, final int n) {
072 if (!checkPN(p, n)) {
073 throw new IllegalArgumentException("No combinations for C(" + p
074 + "," + n + ")");
075 }
076
077 // TODO : bug to fix
078 // comb.generateAllFaster();
079
080 return generateAll(p, n);
081 }
082
083 /**
084 * Compute the number of all the combinations of p elements among n.
085 *
086 * @param p p.
087 * @param n n.
088 *
089 * @return the total number of C(n, p).
090 */
091 public static long computeCombNumber(final int p, final int n) {
092 if (!checkPN(p, n)) {
093 return 0;
094 }
095 double numerator = 0;
096
097 for (int i = n; i > n - p; i--) {
098 numerator += Math.log(i);
099 }
100
101 final double result =
102 numerator - Math.log(FactorialCalculator.getValue(p));
103
104 return Math.round(Math.exp(result));
105 }
106
107 /**
108 * Set valid combination parameters with 1 ≤ {@code p} ≤ {@code n}.
109 *
110 * @param p number of taken things.
111 * @param n size of the set of things.
112 *
113 *
114 */
115 private static boolean checkPN(final int p, final int n) {
116 if ((p < 0) || (n < 0) || (p > n)) {
117 return false;
118 }
119 return true;
120 }
121
122 /**
123 * This algorithm generate all {@code p}-combinations cp...c2c1 of the
124 * {@code n} numbers {0,1,...,{@code n}-1}, given {@code n} ≥ {@code p}
125 * ≥ 1.
126 *
127 * [from knuth the AOCP, section 7.2.3 : Algorithm L]
128 */
129 private List<int[]> generateAll(int p, int n) {
130 List<int[]> combinations = new ArrayList<int[]>();
131 int j = 0;
132 final int[] currentCombination = new int[p + 2];
133
134 // Initialisation
135 while (j < p) {
136 currentCombination[j] = j;
137 j++;
138 }
139 currentCombination[p] = n;
140 currentCombination[p + 1] = 0;
141
142 while (true) {
143
144 // Add current combination
145 final int[] comb = new int[p];
146
147 for (int i = 0; i < comb.length; i++) {
148 comb[i] = currentCombination[i];
149 }
150
151 combinations.add(comb);
152
153 // Find j
154 j = 1;
155 while (currentCombination[j - 1] + 1 == currentCombination[j]) {
156 currentCombination[j - 1] = j - 1;
157 j++;
158 }
159
160 // Done ?
161 if (j > p) {
162 break;
163 }
164
165 currentCombination[j - 1]++;
166 }
167
168 return combinations;
169 }
170
171 /**
172 * TODO : Bug to fix when n=p Faster algorithm than the previous on [from
173 * knuth the AOCP, section 7.2.3 : Algorithm T]
174 */
175 @SuppressWarnings("unused")
176 private List<int[]> generateAllFaster(int p, int n) {
177 List<int[]> combinations = new ArrayList<int[]>();
178
179 int j = 0;
180 int x = 0;
181 final int[] currentCombination = new int[p + 2];
182
183 // Initialisation
184 while (j < p) {
185 currentCombination[j] = j;
186 j++;
187 }
188
189 currentCombination[p] = n;
190 currentCombination[p + 1] = 0;
191
192 // tuning 1
193 j = p - 1;
194
195 System.out.println("j=" + j);
196
197 while (true) {
198 System.out.println("in the while j=" + j);
199
200 // Add current combination
201 final int[] comb = new int[p];
202
203 for (int i = 0; i < comb.length; i++) {
204 comb[i] = currentCombination[i];
205 }
206
207 combinations.add(comb);
208
209 if (j >= 0) {
210 x = j + 1;
211 currentCombination[j] = x;
212 j--;
213 // goto T2
214 continue;
215 } else {
216 if (currentCombination[0] + 1 < currentCombination[1]) {
217 currentCombination[0]++;
218 // goto T2
219 continue;
220 } else {
221 j = 1;
222 }
223 }
224
225 // Find j
226 while (true) {
227
228 // Done ?
229 if (j >= p) {
230 return combinations;
231 }
232 currentCombination[j - 1] = j - 1;
233 x = currentCombination[j] + 1;
234
235 if (x == currentCombination[j + 1]) {
236 j++;
237 } else if (x < currentCombination[j + 1]) {
238 break;
239 }
240 }
241
242 // Increase combination[j]
243 currentCombination[j] = x;
244 j--;
245 }
246 }
247
248 public static String toString(List<int[]> combinations) {
249
250 final StringBuffer sb = new StringBuffer();
251
252 sb.append("[");
253
254 for (final int[] combination : combinations) {
255 sb.append(Arrays.toString(combination));
256 sb.append(", ");
257 }
258 if (sb.length() > 1) {
259 sb.replace(sb.length() - 2, sb.length(), "]");
260 } else {
261 sb.append("]");
262 }
263
264 return sb.toString();
265 }
266
267 }