1. We have moved from vBulletin to XenForo and you are viewing the site in the middle of the move. Though the functional aspect of everything is working fine, we are still working on other changes including the new design on Xenforo.
    Dismiss Notice

generate combination with less than 2 same numbers each other

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

  1. nanachris

    nanachris New Member

    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

    send your code so far.
     
  3. nanachris

    nanachris New Member

    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

    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

    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

    The solution ought to be valid for all p-combinations from n
     
  7. virxen

    virxen New Member

    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