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

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; } }

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(); } }

Thanks Virxen for your help. But your program is static. I want to apply it on all 3-combinations from 1 to n

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); } }