1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

generate combination with less than 2 same numbers each other

Discussion in 'Java' started by nanachris, Oct 15, 2010.

  1. nanachris

    nanachris New Member

    Joined:
    Oct 15, 2010
    Messages:
    4
    Likes Received:
    0
    Trophy Points:
    0
    hi!
    I would like to generate all combination k choose n such that evry combination have less than 2 sane numbers each other. " I already use the Kenneth Rosen's algorithm to generate all combinations but I can't integrate that condition".


    For example: if we consider 3 choose 5 we generate
    123
    124
    125
    134
    135
    145
    234
    235
    245
    345

    with that condition we would just have 123 and 145.
    thank you
     
  2. virxen

    virxen New Member

    Joined:
    Nov 24, 2009
    Messages:
    387
    Likes Received:
    90
    Trophy Points:
    0
    send your code so far.
     
  3. nanachris

    nanachris New Member

    Joined:
    Oct 15, 2010
    Messages:
    4
    Likes Received:
    0
    Trophy Points:
    0
    This is the code:

    Code:
    //--------------------------------------
    // Systematically generate combinations.
    //--------------------------------------
    
    import java.math.BigInteger;
    
    public class CombinationGenerator {
    
      private int[] a;
      private int n;
      private int r;
      private BigInteger numLeft;
      private BigInteger total;
    
      //------------
      // Constructor
      //------------
    
      public CombinationGenerator (int n, int r) {
        if (r > n) {
          throw new IllegalArgumentException ();
        }
        if (n < 1) {
          throw new IllegalArgumentException ();
        }
        this.n = n;
        this.r = r;
        a = new int[r];
        BigInteger nFact = getFactorial (n);
        BigInteger rFact = getFactorial (r);
        BigInteger nminusrFact = getFactorial (n - r);
        total = nFact.divide (rFact.multiply (nminusrFact));
        reset ();
      }
    
      //------
      // Reset
      //------
    
      public void reset () {
        for (int i = 0; i < a.length; i++) {
          a[i] = i;
        }
        numLeft = new BigInteger (total.toString ());
      }
    
      //------------------------------------------------
      // Return number of combinations not yet generated
      //------------------------------------------------
    
      public BigInteger getNumLeft () {
        return numLeft;
      }
    
      //-----------------------------
      // Are there more combinations?
      //-----------------------------
    
      public boolean hasMore () {
        return numLeft.compareTo (BigInteger.ZERO) == 1;
      }
    
      //------------------------------------
      // Return total number of combinations
      //------------------------------------
    
      public BigInteger getTotal () {
        return total;
      }
    
      //------------------
      // Compute factorial
      //------------------
    
      private static BigInteger getFactorial (int n) {
        BigInteger fact = BigInteger.ONE;
        for (int i = n; i > 1; i--) {
          fact = fact.multiply (new BigInteger (Integer.toString (i)));
        }
        return fact;
      }
    
      //--------------------------------------------------------
      // Generate next combination (algorithm from Rosen p. 286)
      //--------------------------------------------------------
    
      public int[] getNext () {
    
        if (numLeft.equals (total)) {
          numLeft = numLeft.subtract (BigInteger.ONE);
          return a;
        }
    
        int i = r - 1;
        while (a[i] == n - r + i) {
          i--;
        }
        a[i] = a[i] + 1;
        for (int j = i + 1; j < r; j++) {
          a[j] = a[i] + j - i;
        }
    
        numLeft = numLeft.subtract (BigInteger.ONE);
        return a;
    
      }
    }
     
    Last edited by a moderator: Oct 18, 2010
  4. virxen

    virxen New Member

    Joined:
    Nov 24, 2009
    Messages:
    387
    Likes Received:
    90
    Trophy Points:
    0
    this is what i understood from what you said according to the example you gave.
    if it is not what you want try to explain better next time.

    Code:
    public class Test{
        public Test(){
            int numbers[][]={{123,1},{124,1},{125,1},{134,1},{135,1},{145,1},{234,1},{235,1},{245,1},{345,1}};
    //let's suppose that you have an integer array with the combinations and a value 0 or 1 to indicate if this combination is invalid(0) or valid(1)
    
            for (int i=0;i<numbers.length;i++){
                for (int j=i-1;j>=0;j--){//check all the previous numbers in the array
                    if (numbers[j][1]==1){//if you found one that is valid then...        
                        if (countDigits(numbers[i][0],numbers[j][0])>=2) numbers[i][1]=0;//if the same digits is >=2 then this number is not valid
                    }
                }
            }
            for (int i=0;i<numbers.length;i++){//print results
                System.out.println("number="+numbers[i][0]+" valid="+numbers[i][1]);
            }
            
        }
        private int countDigits(int a,int b){//count same digits between a,b
            int count=0;
            String A=""+a;//convert to string
            String B=""+b;//convert to string
            for (int i=0;i<A.length();i++){//check A digit by digit
                for (int j=0;j<B.length();j++){to B digit by digit
                    if (A.charAt(i)==B.charAt(j)) count++;//if 2 digits are the same increase count
                }
            }
            return count;
        }
        public static void main(String []args){
            new Test();
        }
    }
    
     
    nanachris and shabbir like this.
  5. nanachris

    nanachris New Member

    Joined:
    Oct 15, 2010
    Messages:
    4
    Likes Received:
    0
    Trophy Points:
    0
    Thanks Virxen for your help. But your program is static. I want to apply it on all 3-combinations from 1 to n
     
  6. nanachris

    nanachris New Member

    Joined:
    Oct 15, 2010
    Messages:
    4
    Likes Received:
    0
    Trophy Points:
    0
    The solution ought to be valid for all p-combinations from n
     
  7. virxen

    virxen New Member

    Joined:
    Nov 24, 2009
    Messages:
    387
    Likes Received:
    90
    Trophy Points:
    0
    the example is static but the code is not.

    if you feed the above code with the right array--->numbers[][]
    you will get what you want.

    p.s. you mentioned above that you know how to find the combinations
    so try something like this

    Code:
    public class Test{
        public Test(int numbers[]){
    //let's suppose that you have an integer array with the combinations and a value 0 or 1 to indicate if this combination is invalid(0) or valid(1)
            int value[]=new int[numbers.length];
            for (int i=0;i<numbers.length;i++){
                value[i]=1;
                for (int j=i-1;j>=0;j--){//check all the previous numbers in the array
                    if (value[j]==1){//if you found one that is valid then...        
                        if (countDigits(numbers[i],numbers[j])>=2) value[i]=0;//if the same digits is >=2 then this number is not valid
                    }
                }
            }
            for (int i=0;i<numbers.length;i++){//print results
                System.out.println("number="+numbers[i]+" valid="+value[i]);
            }
            
        }
        private int countDigits(int a,int b){//count same digits between a,b
            int count=0;
            String A=""+a;//convert to string
            String B=""+b;//convert to string
            for (int i=0;i<A.length();i++){//check A digit by digit
                for (int j=0;j<B.length();j++){//to B digit by digit
                    if (A.charAt(i)==B.charAt(j)) count++;//if 2 digits are the same increase count
                }
            }
            return count;
        }
        public static void main(String []args){
            CombinationGenerator combinations=new CombinationGenerator(5,3);
            int numbers[]=new int[combinations.getTotal().intValue()];
            int counter=-1;
            while (combinations.hasMore()){
                counter++;
                numbers[counter]=0;
                int value=1;
                int temp[]=combinations.getNext();
                for (int j=temp.length-1;j>=0;j--){
                    numbers[counter]+=(temp[j]+1)*value;
                    value*=10;
                }
            }
            new Test(numbers);
        }
    }
    
     
    nanachris and shabbir like this.

Share This Page