mev-4.0.01/source/org/tigr/util/Combinations.java

Code
Comments
Other
Rev Date Author Line
2 26 Feb 07 jari 1 /*
2 26 Feb 07 jari 2 Copyright @ 1999-2003, The Institute for Genomic Research (TIGR).
2 26 Feb 07 jari 3 All rights reserved.
2 26 Feb 07 jari 4 */
2 26 Feb 07 jari 5 /*
2 26 Feb 07 jari 6  * $RCSfile: Combinations.java,v $
2 26 Feb 07 jari 7  * $Revision: 1.1.1.1 $
2 26 Feb 07 jari 8  * $Date: 2003/08/21 21:04:23 $
2 26 Feb 07 jari 9  * $Author: braisted $
2 26 Feb 07 jari 10  * $State: Exp $
2 26 Feb 07 jari 11  */
2 26 Feb 07 jari 12 package org.tigr.util;
2 26 Feb 07 jari 13
2 26 Feb 07 jari 14 public class Combinations {
2 26 Feb 07 jari 15     
2 26 Feb 07 jari 16 /*-------------------------------------------------------------------
2 26 Feb 07 jari 17 Adapted from: http://www.brent.worden.org/algorithm/combinatorics/enumerateCombinations.html
2 26 Feb 07 jari 18  
2 26 Feb 07 jari 19  Description:
2 26 Feb 07 jari 20    Enumerates all possible combinations of choosing k objects from n
2 26 Feb 07 jari 21    distint objects.  Initialize the enumeration by setting j[0] to a
2 26 Feb 07 jari 22    negative value.  Then, each call to enumerateCombinations will
2 26 Feb 07 jari 23    generate the next combinations and place it in j[0..k-1].  A
2 26 Feb 07 jari 24    return value of false indicates there are no more combinations to
2 26 Feb 07 jari 25    generate.  j needs to be allocated with a size for at least k
2 26 Feb 07 jari 26    elements.
2 26 Feb 07 jari 27  
2 26 Feb 07 jari 28  Author:
2 26 Feb 07 jari 29    Brent Worden
2 26 Feb 07 jari 30  
2 26 Feb 07 jari 31  Language:
2 26 Feb 07 jari 32    C++
2 26 Feb 07 jari 33  
2 26 Feb 07 jari 34  Usage:
2 26 Feb 07 jari 35    int comb[10] = {-1};
2 26 Feb 07 jari 36    while(enumerateCombinations(10, 5, comb)){
2 26 Feb 07 jari 37        // do something with comb[0..4]
2 26 Feb 07 jari 38    }
2 26 Feb 07 jari 39  
2 26 Feb 07 jari 40  Reference:
2 26 Feb 07 jari 41    Tucker, Allen.  Applied Combinatorics.  3rd Ed.  1994.
2 26 Feb 07 jari 42 -------------------------------------------------------------------*/
2 26 Feb 07 jari 43     
2 26 Feb 07 jari 44     public static boolean enumerateCombinations(int n, int k, int j[]) {
2 26 Feb 07 jari 45   int i;
2 26 Feb 07 jari 46   if(j[0] < 0){
2 26 Feb 07 jari 47       for(i = 0; i < k; ++i){
2 26 Feb 07 jari 48     j[i] = i;
2 26 Feb 07 jari 49       }
2 26 Feb 07 jari 50       return true;
2 26 Feb 07 jari 51   } else {
2 26 Feb 07 jari 52       for(i = k - 1; i >= 0 && j[i] >= n - k + i; --i){}
2 26 Feb 07 jari 53       if(i >= 0){
2 26 Feb 07 jari 54     j[i]++;
2 26 Feb 07 jari 55     int m;
2 26 Feb 07 jari 56     for(m = i + 1; m < k; ++m){
2 26 Feb 07 jari 57         j[m] = j[m-1] + 1;
2 26 Feb 07 jari 58     }
2 26 Feb 07 jari 59     return true;
2 26 Feb 07 jari 60       } else {
2 26 Feb 07 jari 61     return false;
2 26 Feb 07 jari 62       }
2 26 Feb 07 jari 63   }
2 26 Feb 07 jari 64     }
2 26 Feb 07 jari 65     
2 26 Feb 07 jari 66     public static void main(String[] args) {
2 26 Feb 07 jari 67   int[] comb = new int[5];
2 26 Feb 07 jari 68   for (int i = 0; i < comb.length; i++) {
2 26 Feb 07 jari 69       comb[i] = -1;
2 26 Feb 07 jari 70   }
2 26 Feb 07 jari 71   
2 26 Feb 07 jari 72   while (enumerateCombinations(10, 5, comb)) {
2 26 Feb 07 jari 73       for (int i = 0; i < comb.length; i++) {
2 26 Feb 07 jari 74     System.out.print("" + comb[i] + " ");
2 26 Feb 07 jari 75       }
2 26 Feb 07 jari 76       System.out.println();
2 26 Feb 07 jari 77   }
2 26 Feb 07 jari 78     }
2 26 Feb 07 jari 79     
2 26 Feb 07 jari 80 }

Generated on Thu Jul 20 09:31:58 2023 (UTC) by svndigest 0.11.2pre (dev build 1672)