Number combinations
Hello Everyone,
I am facing lots of problem with generating number combinations(without repeat). I did not find a suitable algorithm online, so that i can convert that into Java code. Here is what i want
For example,
if n=3
it shud generate
1
2
3
12
13
23
123
for n=5
it shud generate
1
2
3
4
5
12
13
14
15
23
24
25
34
35
45
123
124
125
134
135
145
234
235
245
345
1234
1235
1345
2345
12345
Can anyone tell me an algorithm or method to generate these type of combinations.
thanks,
Kedar
[770 byte] By [
Kedara] at [2007-10-2 6:50:03]
Let me be more clear with my question,
OK,
First the algorithm shud produce single digit number combination, then 2 digit .... up to n digits.
For example N=3
First step
1
2
3
Second step(it shud take combinations of the above two steps, We shud be able to skip the repeated combinations)
1 2
1 3
2 3
Third step(we shud take the combinations and combine to generate 3 step)
1 2 3 ( We dont consider 112,113,212,213,223,312,313,323 because we dont want the numbers to be repeated)
Let me give combinations for N=5
First step( length of 1)
1
2
3
4
5
Second Step(length of 2)
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
Fourth Step(length of 4)
1 2 3 4
1 2 3 5
1 2 4 5
1 3 4 5
2 3 4 5
Fifth step(length of 5)
1 2 3 4 5
Hopefully it shud be clear. Let me know if i m not clear with my question.
Thanks a lot,
Kedar.
Kedara at 2007-7-16 13:59:00 >
> Can anyone tell me an algorithm or method to generate
> these type of combinations.
Here's a way, say n = 4 we have:
4 combinations of length 1: [1], [2], [3], [4]
6 combinations of length 2: [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]
4 combinations of length 3: [1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]
1 combinations of length 4: [1, 2, 3, 4]
You can create the first combination of each length as an array of int's and then continue untill you have reached the last combination. Here's a start:
/**
> Executing: NumberCombinations
[1]
[2]
[3]
[4]
[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 4]
[1, 2, 3]
[1, 2, 4]
[1, 3, 4]
[2, 3, 4]
[1, 2, 3, 4]
> Execution finished.
*/
class NumberCombinations {
/**
* main
*/
public static void main(String[] args) {
int max = 4;
for(int i = 1; i <= max; i++) {
generate(i, max);
}
}
/**
* Generate an array of length 'n' and print
* every combination.
*/
private static void generate(int n, int mx) {
int[] array = new int[n];
for(int i = 0; i < n; i++) {
array[i] = i+1;
}
print(array);
while(!isLast(array, mx)) {
array = next(array, mx);
print(array);
}
}
/**
* Return the next combination, example:
* arr = {1,2,3}, mx = 4 will return {1,2,4},
* arr = {1,2,4}, mx = 4 will return {1,3,4}.
*/
private static int[] next(int[] arr, int mx) {
// your code
return arr;
}
/**
* Check if an array is the 'last' combination, for example:
* arr = {1,2,4}, mx = 4 will return false,
* arr = {2,3,4}, mx = 4 will return true.
*/
private static boolean isLast(int[] arr, int mx) {
// your code
return true;
}
/**
* print an array of int's
*/
private static void print(int[] arr) {
System.out.print("["+arr[0]);
for(int i = 1; i < arr.length; i++) {
System.out.print(", "+arr[i]);
}
System.out.println("]");
}
}
Good luck.
