Recursion Question

[p1kn1c]

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 =/.

[sjalle]

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:

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...

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.....