Home » Core Java » Simple Combination Generation Algorithm.

Simple Combination Generation Algorithm.

Some times we come across situation of generating all possible combinations of given set of values or objects. One classical example of combination without repetition is Lottery System where lotteries are listed for all possible number combination but the one lucky combination wins that.

Another example of combination is number lock where we set a number combination as a key.Whichever be the need below is a simple algorithm of creating combination.

Combination means all possible arrangements of given set of values or objects.

Combinations2

Suppose we have been given set of some words or numbers or say letters like {a,b,c,d}. Then think how do we practically crate a combination.. Answere is you would probably pick an item say a

a,,,,

then you may place another item in the available space ex:

a,,b,

then you would put c and d.

a,c,b,

and then

a,c,b,d

This is how you have achieved one combination where we put first element ‘a’ at first position and arranged other three elements at vacant positions one by one. Like wise in next iteration we can place a at second positions and again place all element one by one in vacant positions.

We have mode this practical approach in algorithm where we pick first item and put in all possible positions and then pick second element and put in all possible positions.

We are using approach or recursion where we first position first element ‘a’ in all available possible position one by one in a loop and then we call subsequently same approach for other elements one by one. Simple here you go !

Here is a simple code written for this algorithm.



import java.util.Arrays;
public class PasswordGen {
static String[] options = {"a","b","c","d"};
static String[] places = new String[options.length];
static int count;

public static void main(String [] args){
  //Starting with initial position of a i.e. 0
  sequence(0,places.clone());
}

private static void sequence(int level, String[] holder){
  if(level>=options.length){
    //combination complete
    System.out.println(""+(++count) + " Combination " + Arrays.toString(holder));
    return ;
  }

  String val = options[level];
  String[] inrHolder = null;
  for(int c=0; c<holder.length; c++){
    inrHolder = holder.clone();
    if(inrHolder[c]==null){
      inrHolder[c]=val;
      sequence(level+1, inrHolder.clone());
    }
  }
  return ;
}
}



Output of the above program tested for sample a,b,c,d :

1 Combination [a, b, c, d]
2 Combination [a, b, d, c]
3 Combination [a, c, b, d]
4 Combination [a, d, b, c]
5 Combination [a, c, d, b]
6 Combination [a, d, c, b]
7 Combination [b, a, c, d]
8 Combination [b, a, d, c]
9 Combination [c, a, b, d]
10 Combination [d, a, b, c]
11 Combination [c, a, d, b]
12 Combination [d, a, c, b]
13 Combination [b, c, a, d]
14 Combination [b, d, a, c]
15 Combination [c, b, a, d]
16 Combination [d, b, a, c]
17 Combination [c, d, a, b]
18 Combination [d, c, a, b]
19 Combination [b, c, d, a]
20 Combination [b, d, c, a]
21 Combination [c, b, d, a]
22 Combination [d, b, c, a]
23 Combination [c, d, b, a]
24 Combination [d, c, b, a]

Advertisements

1 Comment

  1. Ahmed Sharif says:

    this is permutation, not combination.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: