generate combination with less than 2 same numbers each other

nanachris's Avatar, Join Date: Oct 2010
Newbie 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
0
virxen's Avatar, Join Date: Nov 2009
Pro contributor
send your code so far.
0
nanachris's Avatar, Join Date: Oct 2010
Newbie 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 shabbir; 18Oct2010 at 17:41.. Reason: Code blocks
0
virxen's Avatar, Join Date: Nov 2009
Pro contributor
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, shabbir likes this
0
nanachris's Avatar, Join Date: Oct 2010
Newbie Member
Thanks Virxen for your help. But your program is static. I want to apply it on all 3-combinations from 1 to n
0
nanachris's Avatar, Join Date: Oct 2010
Newbie Member
Quote:
Originally Posted by nanachris View Post
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
The solution ought to be valid for all p-combinations from n
0
virxen's Avatar, Join Date: Nov 2009
Pro contributor
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, shabbir likes this