Go4Expert

Go4Expert (http://www.go4expert.com/)
-   Java (http://www.go4expert.com/forumdisplay.php?f=21)
-   -   generate combination with less than 2 same numbers each other (http://www.go4expert.com/showthread.php?t=23583)

nanachris 15Oct2010 21:00
generate combination with less than 2 same numbers each other
 
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 17Oct2010 22:16
Re: generate combination with less than 2 same numbers each other
 
send your code so far.

nanachris 18Oct2010 16:45
Re: generate combination with less than 2 same numbers each other
 
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;

  }
}

virxen 20Oct2010 01:24
Re: generate combination with less than 2 same numbers each other
 
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 29Mar2011 19:13
Re: generate combination with less than 2 same numbers each other
 
Thanks Virxen for your help. But your program is static. I want to apply it on all 3-combinations from 1 to n

nanachris 29Mar2011 20:05
Re: generate combination with less than 2 same numbers each other
 
Quote:
Originally Posted by nanachris (Post 73757)
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 30Mar2011 03:58
Re: generate combination with less than 2 same numbers each other
 
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);
    }
}


All times are GMT +5.5. The time now is 19:32.