Skip to content

Commit 5eced35

Browse files
hmkcodehmkcode
committed
new algorithms
new algorithms
1 parent 7b30dc2 commit 5eced35

4 files changed

Lines changed: 196 additions & 9 deletions

File tree

‎java-combinations/README.md‎

Lines changed: 5 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -1,12 +1,8 @@
1-
Non-Recursive Algorithm for Finding Combination
2-
===============================================
1+
Algorithms for Finding all Possible Combinations of k Elements in an Array with Java Implementation
2+
===================================================================================================
33

4-
Here is a generic non-recursive algorithm for finding all possible combination for an array of objects.
4+
Refer to the [http://hmkcode.github.io/calculate-find-all-possible-combinations-of-an-array-using-java/](http://hmkcode.github.io/calculate-find-all-possible-combinations-of-an-array-using-java/) for more info.
55

6-
For example, if we have an Array of elements=`{"A","B","C","D","E"}` and we want to find the combination of these elements taken 3 at a time.
7-
Using math we can find the number of possible combination using a known [formula](https://en.wikipedia.org/wiki/Combination).
6+
Given an array of size N e.g. `e={'A','B','C','D','E'}` **N=5**, we want to find all possible combinations of K elements in that array. For example, if K=3 then one possible combination is of array **e** is `{'A','B','C'}. Here we have three different algorithms for finding *k*-combinations of an array.
87

9-
However, to find those combinations we need an algorithm to do so.
10-
Below image explains the steps taken by the algorithm to find the results.
11-
12-
![combinations](http://hmkcode.github.io/images/java/combinations.png)
8+
![combinations](http://hmkcode.github.io/images/java/combinations_forwardbackward.png)

‎java-combinations/src/main/java/com/hmkcode/ForwardBackward.java‎

Lines changed: 94 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,94 @@
1+
package com.hmkcode;
2+
3+
4+
5+
public class ForwardBackward {
6+
7+
8+
public static void main(String[] args){
9+
Object[] elements = new Object[] {'A','B','C','D','E'};
10+
combination(elements,3);
11+
}
12+
13+
14+
public static void combination(Object[] elements, int K){
15+
16+
// get the length of the array
17+
// e.g. for {'A','B','C','D'} => N = 4
18+
int N = elements.length;
19+
20+
if(K > N){
21+
System.out.println("Invalid input, K > N");
22+
return;
23+
}
24+
25+
// calculate the possible combinations
26+
c(N,K);
27+
28+
// init combination index array
29+
int pointers[] = new int[K];
30+
31+
32+
int r = 0; // index for combination array
33+
int i = 0; // index for elements array
34+
35+
while(r >= 0){
36+
37+
// forward step if i < (N + (r-K))
38+
if(i <= (N + (r - K))){
39+
pointers[r] = i;
40+
41+
// if combination array is full print and increment i;
42+
if(r == K-1){
43+
print(pointers, elements);
44+
i++;
45+
}
46+
else{
47+
// if combination is not full yet, select next element
48+
i = pointers[r]+1;
49+
r++;
50+
}
51+
}
52+
53+
// backward step
54+
else{
55+
r--;
56+
if(r >= 0)
57+
i = pointers[r]+1;
58+
59+
}
60+
}
61+
}
62+
63+
64+
65+
private static int c(int n, int r){
66+
int nf=fact(n);
67+
int rf=fact(r);
68+
int nrf=fact(n-r);
69+
int npr=nf/nrf;
70+
int ncr=npr/rf;
71+
72+
System.out.println("C("+n+","+r+") = "+ ncr);
73+
74+
return ncr;
75+
}
76+
77+
private static int fact(int n)
78+
{
79+
if(n == 0)
80+
return 1;
81+
else
82+
return n * fact(n-1);
83+
}
84+
85+
86+
private static void print(int[] combination, Object[] elements){
87+
88+
String output = "";
89+
for(int z = 0 ; z < combination.length;z++){
90+
output += elements[combination[z]];
91+
}
92+
System.out.println(output);
93+
}
94+
}

‎java-combinations/src/main/java/com/hmkcode/Recursive.java‎

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
package com.hmkcode;
2+
3+
import java.util.Arrays;
4+
import java.util.List;
5+
6+
public class Recursive {
7+
8+
public static void main(String[] args) {
9+
10+
List<String> e = Arrays.asList("A", "B", "C", "D", "E");
11+
combination(e, 3, "");
12+
13+
}
14+
static int counter = 0;
15+
public static void combination(List<String> e, int K, String c){
16+
17+
if(e.size() < K)
18+
return;
19+
20+
if(K == 1)
21+
for(String s:e)
22+
print(c+s);
23+
else if(e.size() == K){
24+
for(String s:e)
25+
c+=s;
26+
print(c);
27+
}
28+
else if(e.size() > K)
29+
for(int i = 0 ; i < e.size() ; i++)
30+
combination(e.subList(i+1, e.size()), K-1, c+e.get(i));
31+
32+
}
33+
34+
public static void print(String c){
35+
counter++;
36+
System.out.println(counter+"\t"+c);
37+
}
38+
}

‎java-combinations/src/main/java/com/hmkcode/Shifting.java‎

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
package com.hmkcode;
2+
3+
public class Shifting
4+
{
5+
public static void main( String[] args )
6+
{
7+
String[] e = {"A","B","C","D","E"};
8+
int K = 3;
9+
}
10+
public static void combination(Object[] e, int K){
11+
12+
int[] ignore = new int[e.length-K]; // --> [0][0]
13+
int[] combination = new int[K]; // --> [][][]
14+
15+
for(int w = 0; w < ignore.length; w++){ // --> [3][4]
16+
ignore[w] = e.length - K +(w+1);
17+
//System.out.println(ignore[w]);
18+
}
19+
20+
int i = 0;
21+
int r = 0;
22+
int g = 0;
23+
boolean terminate = false;
24+
while(!terminate){
25+
while(i < e.length && r < K){
26+
27+
if(i != ignore[g]){
28+
combination[r] = i;
29+
System.out.print(e[combination[r]]+" ");
30+
r++;
31+
i++;
32+
}
33+
else{
34+
g++;
35+
36+
if(g == ignore.length)
37+
g--;
38+
39+
i++;
40+
}
41+
}
42+
i = 0; r=0; g =0;
43+
System.out.println("");
44+
45+
terminate = true;
46+
47+
for(int w = 0 ; w < ignore.length; w++){
48+
if(ignore[w] > w){
49+
ignore[w]--;
50+
51+
if(w > 0)
52+
ignore[w-1] = ignore[w]-1;
53+
terminate = false;
54+
break;
55+
}
56+
}
57+
}
58+
}
59+
}

0 commit comments

Comments
 (0)