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

Code
Comments
Other
Rev Date Author Line
2 26 Feb 07 jari 1 /*
2 26 Feb 07 jari 2  * Permutations.java
2 26 Feb 07 jari 3  *
2 26 Feb 07 jari 4  * Created on November 14, 2003, 3:42 PM
2 26 Feb 07 jari 5  */
2 26 Feb 07 jari 6
2 26 Feb 07 jari 7 package org.tigr.util;
2 26 Feb 07 jari 8
2 26 Feb 07 jari 9 /**
2 26 Feb 07 jari 10  *
2 26 Feb 07 jari 11  * @author  nbhagaba
2 26 Feb 07 jari 12  */
2 26 Feb 07 jari 13 public class Permutations {
2 26 Feb 07 jari 14     
2 26 Feb 07 jari 15     
2 26 Feb 07 jari 16 /*-------------------------------------------------------------------
2 26 Feb 07 jari 17  Description:
2 26 Feb 07 jari 18    Enumerates all possible permutations of choosing k objects from n
2 26 Feb 07 jari 19    distint objects.  Initialize the enumeration by setting j[0] to a
2 26 Feb 07 jari 20    negative value.  Then, each call to enumeratePermutations will
2 26 Feb 07 jari 21    generate the next permutation and place it in j[0..k-1].  A return
2 26 Feb 07 jari 22    value of false indicates there are no more permutations to
2 26 Feb 07 jari 23    generate.  j needs to be allocated with a size for at least n
2 26 Feb 07 jari 24    elements.
2 26 Feb 07 jari 25  
2 26 Feb 07 jari 26  Author:
2 26 Feb 07 jari 27    Brent Worden
2 26 Feb 07 jari 28  
2 26 Feb 07 jari 29  Language:
2 26 Feb 07 jari 30    C++
2 26 Feb 07 jari 31  
2 26 Feb 07 jari 32  Usage:
2 26 Feb 07 jari 33    int perm[10] = {-1};
2 26 Feb 07 jari 34    while(enumeratePermutations(10, 5, perm)){
2 26 Feb 07 jari 35        // do something with perm[0..4]
2 26 Feb 07 jari 36    }
2 26 Feb 07 jari 37  
2 26 Feb 07 jari 38  Reference:
2 26 Feb 07 jari 39    Tucker, Allen.  Applied Combinatorics.  3rd Ed.  1994.
2 26 Feb 07 jari 40 -------------------------------------------------------------------*/
2 26 Feb 07 jari 41     public static boolean enumeratePermutations(int n, int k, int j[]){
2 26 Feb 07 jari 42         int i;
2 26 Feb 07 jari 43         if(j[0] < 0){
2 26 Feb 07 jari 44             for(i = 0; i < n; ++i){
2 26 Feb 07 jari 45                 j[i] = i;
2 26 Feb 07 jari 46             }
2 26 Feb 07 jari 47             int start = k;
2 26 Feb 07 jari 48             int end = n - 1;
2 26 Feb 07 jari 49             int t;
2 26 Feb 07 jari 50             while(start < end){
2 26 Feb 07 jari 51                 t = j[start];
2 26 Feb 07 jari 52                 j[start++] = j[end];
2 26 Feb 07 jari 53                 j[end--] = t;
2 26 Feb 07 jari 54             }
2 26 Feb 07 jari 55             return true;
2 26 Feb 07 jari 56         } else {
2 26 Feb 07 jari 57             for(i = n - 2; i >= 0 && j[i] >= j[i+1]; --i){}
2 26 Feb 07 jari 58             if(i < 0){
2 26 Feb 07 jari 59                 return false;
2 26 Feb 07 jari 60             } else {
2 26 Feb 07 jari 61                 int least = i + 1;
2 26 Feb 07 jari 62                 for(int m = i + 2; m < n; ++m){
2 26 Feb 07 jari 63                     if(j[m] < j[least] && j[m] > j[i]){
2 26 Feb 07 jari 64                         least = m;
2 26 Feb 07 jari 65                     }
2 26 Feb 07 jari 66                 }
2 26 Feb 07 jari 67                 int t = j[i];
2 26 Feb 07 jari 68                 j[i] = j[least];
2 26 Feb 07 jari 69                 j[least] = t;
2 26 Feb 07 jari 70                 if(k - 1 > i){
2 26 Feb 07 jari 71                     int start = i + 1;
2 26 Feb 07 jari 72                     int end = n - 1;
2 26 Feb 07 jari 73                     while(start < end){
2 26 Feb 07 jari 74                         t = j[start];
2 26 Feb 07 jari 75                         j[start++] = j[end];
2 26 Feb 07 jari 76                         j[end--] = t;
2 26 Feb 07 jari 77                     }
2 26 Feb 07 jari 78                     start = k;
2 26 Feb 07 jari 79                     end = n - 1;
2 26 Feb 07 jari 80                     while(start < end){
2 26 Feb 07 jari 81                         t = j[start];
2 26 Feb 07 jari 82                         j[start++] = j[end];
2 26 Feb 07 jari 83                         j[end--] = t;
2 26 Feb 07 jari 84                     }
2 26 Feb 07 jari 85                 }
2 26 Feb 07 jari 86                 return true;
2 26 Feb 07 jari 87             }
2 26 Feb 07 jari 88         }
2 26 Feb 07 jari 89     }
2 26 Feb 07 jari 90     
2 26 Feb 07 jari 91     public static void main(String[] args) {
2 26 Feb 07 jari 92   int[] comb = new int[5];
2 26 Feb 07 jari 93   for (int i = 0; i < comb.length; i++) {
2 26 Feb 07 jari 94       comb[i] = -1;
2 26 Feb 07 jari 95   }
2 26 Feb 07 jari 96   int counter = 0;
2 26 Feb 07 jari 97         /*
2 26 Feb 07 jari 98   while (enumeratePermutations(5, 5, comb)) {
2 26 Feb 07 jari 99       for (int i = 0; i < comb.length; i++) {
2 26 Feb 07 jari 100     System.out.print("" + comb[i] + " ");
2 26 Feb 07 jari 101       }
2 26 Feb 07 jari 102             counter++;
2 26 Feb 07 jari 103       System.out.println();
2 26 Feb 07 jari 104   }
2 26 Feb 07 jari 105         System.out.println("Number of permutations = " + counter);
2 26 Feb 07 jari 106          **/
2 26 Feb 07 jari 107          
2 26 Feb 07 jari 108         
2 26 Feb 07 jari 109         for (int i = 1000; i <= 1500; i++) {
2 26 Feb 07 jari 110             String s = String.valueOf(i);
2 26 Feb 07 jari 111             
2 26 Feb 07 jari 112             float exp = Float.parseFloat(s);
2 26 Feb 07 jari 113             //System.out.println("s = " +s + ", exp = " + exp + ", 2^" + exp + " = " + (float)(Math.pow(2, exp)));
2 26 Feb 07 jari 114             System.out.println("2^" + i + " = "+ Math.pow(2, i));
2 26 Feb 07 jari 115         }
2 26 Feb 07 jari 116          
2 26 Feb 07 jari 117     }    
2 26 Feb 07 jari 118 }

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