[nanachris]

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

[virxen]

send your code so far.

[nanachris]

This is the 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;

  }
}

[virxen]

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.

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]

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

[nanachris]

Quote:

Originally Posted by nanachris

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

[virxen]

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

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