Created
February 26, 2015 05:53
-
-
Save deostroll/cf71139f04d0be72ede8 to your computer and use it in GitHub Desktop.
Generic Combination implementation in java
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import java.util.ArrayList; | |
| import java.util.Iterator; | |
| import java.util.NoSuchElementException; | |
| public class Combinations<T> implements Iterable<ArrayList<T>> { | |
| private int totalCombinations; | |
| private int n, r; | |
| private int factorial(int n) { | |
| int p = 1; | |
| for (int i = n; i > 1; i--) { | |
| p *= i; | |
| } | |
| return p; | |
| } | |
| private ArrayList<T> seq; | |
| public Combinations(ArrayList<T> sequence, int r) { | |
| this.r = r; | |
| seq = sequence; | |
| n = sequence.size(); | |
| int num = 1; | |
| for (int i = n, j = n - r + 1; i >= j; i--) { | |
| num *= i; | |
| } | |
| totalCombinations = num / factorial(r); | |
| } | |
| @Override | |
| public Iterator<ArrayList<T>> iterator() { | |
| return new CombinationIterator(); | |
| } | |
| private class CombinationIterator implements Iterator<ArrayList<T>> { | |
| private int count = 0; | |
| private int[] pos; | |
| private CombinationIterator() { | |
| pos = new int [r]; | |
| for (int i = 0; i < r; i++) { | |
| pos[i] = i; | |
| } | |
| } | |
| @Override | |
| public boolean hasNext() { | |
| return count < totalCombinations; | |
| } | |
| @Override | |
| public ArrayList<T> next() { | |
| int l, m; | |
| if(!hasNext()) | |
| throw new NoSuchElementException(); | |
| ArrayList<T> combination = makeList(); | |
| //computing for next iteration | |
| int k = r - 1; | |
| if (pos[k] + 1 < n) { | |
| pos[k]++; | |
| } | |
| else { | |
| l = k - 1; | |
| while (l >= 0) { | |
| if (pos[l] + 1 < n - r + (l + 1)) { | |
| pos[l]++; | |
| m = l + 1; | |
| while (m <= k) { | |
| pos[m] = pos[m-1] + 1; | |
| m++; | |
| } | |
| break; | |
| } | |
| l--; | |
| } | |
| } | |
| count++; | |
| return combination; | |
| } | |
| private ArrayList<T> makeList(){ | |
| ArrayList<T> list = new ArrayList<T>(); | |
| for(int i = 0; i < r; i++) { | |
| list.add(seq.get(pos[i])); | |
| } | |
| return list; | |
| } | |
| } | |
| public static void main(String[] args){ | |
| //Making a combination sequence out of strings... | |
| String test1 = "abcde"; | |
| ArrayList<Character> converted = new ArrayList<Character>(); | |
| for (int i = 0; i < test1.length(); i++) { | |
| converted.add(test1.charAt(i)); | |
| } | |
| Combinations<Character> combCharacter | |
| = new Combinations<Character>(converted, 3); | |
| for (ArrayList<Character> arrayList : combCharacter) { | |
| for (Character character : arrayList) { | |
| System.out.print(character); | |
| } | |
| System.out.println(); | |
| } | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment