Recursion Question


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 2 of 2

Thread: Recursion Question

  1. #1
    Join Date
    May 2005
    Posts
    22

    Recursion Question

    Hey, i have this small prog that lists all the possibilities of choosing 7 of 20 options.

    There are 20 cards..yet only 7 can be chosen at a time..basically the porgram lists all posibilities of how to take the cards.

    I can do the prog yet the problem is that my solutuion doesnt account for repition, which i want to eliminate.. i dont want it to list
    1,1,1,1,2,3,4
    and 1,1,1,1,2,4,5

    ..basically i want no repetion..ive tried some obvious ways yet i havnt been able to figure it out.. so Please..i coudl really use some help..

    here is the code so far



    public class StuffEnvelope{
    public static void main(String[]args){

    int c[]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
    int u[]=new int[7];
    crack(c,0,u);
    }

    public static void crack(int x[],int n,int v[]){

    String tryString="";

    for(int i=0;i<20;i++){
    v[n]=x[i];

    tryString=(v[0]+","+v[1]+","+v[2]+","+v[3]+","+v[4]+","+v[5]+","+v[6]);

    System.out.println(tryString);

    if(n<6){
    crack(x,(n+1),v);
    }
    }


    }
    }



    Basically i need to know what to add in so there is no repetion in the thing at all.. simply no card can be chosen more then once..and arrangements 1,2,3,4,5,6,7 is the same as 7,6,5,4,3,2,1..so i dont waant both listed..


    Thanks for any help. I need it lol =/.

  2. #2
    Join Date
    Nov 2004
    Location
    Norway
    Posts
    1,560

    Unhappy Is your algorithm correct ?

    I have a setup here that guarantees the condition:
    no card can be chosen more then once..and arrangements 1,2,3,4,5,6,7 is the same as 7,6,5,4,3,2,1
    is satisfied.

    I introduced a class for this:

    Code:
    import java.util.*;
    
    class Hand implements Comparator {
      private static StringBuffer sb=new StringBuffer();
      public ArrayList sortedHand=null;
      public Hand(int [] cards)  {
        sortedHand=new ArrayList(cards.length);
        for (int i=0; i<cards.length; i++) {
          sortedHand.add(new Integer(cards[i]));
        }
        Collections.sort(sortedHand,this);
      }
      public int compare(Object o1, Object o2) {
        int i1=((Integer)o1).intValue();
        int i2=((Integer)o2).intValue();
        return i1-i2;
      }
      public boolean equals(Object obj) {
        Hand h=(Hand)obj;
        return h.toString().equals(toString());
      }
      public boolean hasRepetitions() {
        Object lag=null;
        for (int i=0; i<sortedHand.size(); i++) {
          if (i > 0) {
            if (lag.equals(sortedHand.get(i))) {
              //System.out.println("hasRepetitions: "+toString());
              return true;
            }
          }
          lag=sortedHand.get(i);
        }
        return false;
      }
    
      public int hashCode() {
        int ret=0;
        for (int i=sortedHand.size()-1; i >= 0;  i--) {
          ret +=Math.pow( ((Integer)sortedHand.get(i)).intValue(),i+1);
        }
        return ret;
      }
      public String toString () {
        sb.setLength(0);
        for (int i=0; i<sortedHand.size(); i++) {
          sb.append(sortedHand.get(i)+" ");
        }
        return sb.toString();
      }
    
    }
    And implemented it in your code (slightly "unstaticfied"). For testing I trimmed
    down the possible number of combinations by using only a 3 cards hand, -
    the 7 cards version started to get strung out somewhere around 30000
    combinations...

    Code:
    public class StuffEnvelope  {
      private HashSet versions=new HashSet(10000);
      private int [] c=null;
      private int combinationCount=0;
      private int lastRep=-1;
    
      public StuffEnvelope (int c[]) {
        this.c=c;
    
      }
    
      public void getCombinations(int [] u) {
    
        crack(c,0,u);
        System.out.println("combinationCount(no check): "+combinationCount);
        System.out.println("Combinations (checked)    : "+versions.size());
        Iterator it=versions.iterator();
        while (it.hasNext()) {
          Hand h=(Hand)it.next();
          System.out.println(h);
        }
      }
      public void crack(int x[], int n, int v[]) {
    
        for (int i = 0; i < x.length; i++) {
          v[n] = x[i];
    
          combinationCount++;
    
          //Hand h=new Hand(new int []{v[0],v[1],v[2],v[3],v[4],v[5],v[6]});
          Hand h = new Hand(new int[] {v[0], v[1], v[2]});
    
          if (!h.hasRepetitions()) {
            versions.add(h);
            //System.out.println("hand: "+h);
          }
          if ( (versions.size() > 0) && (versions.size() % 100 == 0)) {
            if (lastRep!=versions.size()) {
              System.out.println("versions: " + versions.size());
              lastRep=versions.size();
            }
          }
          if (n < 2) {
          //if (n < 6) {
            crack(x, (n + 1), v);
          }
    
        }
    
      }
      /**********************************************
       *  MAIN
       */
      public static void main(String[] args) {
    
        int c[] = {
            1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
        //int u[] = new int[7];
        int u[] = new int[3];
        StuffEnvelope se=new StuffEnvelope(c);
        se.getCombinations(u);
      }
    
    }
    But I'm not quite sure about your algorithm though.....
    Last edited by sjalle; 06-14-2005 at 06:00 AM.
    eschew obfuscation

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center