# generate combination with less than 2 same numbers each other

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

1. ### nanachrisNew 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. ### virxenNew Member

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

3. ### nanachrisNew 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. ### virxenNew 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. ### nanachrisNew 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. ### nanachrisNew 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. ### virxenNew 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.