Find out all combinations and permutations - Java

Question

I am all new here and also a beginner. I am working on a personal project (developing an app for personal use). I am a bit stuck and yes, I did search around but couldn't find much. My aim is to find all possible combinations. Let's say I have a finite number of lists defined like:

List<String> AList contains {"a1","a2","a3","a4"} 
List<String> BList contains {"b1","b2","b3"} 
List<String> CList contains {"c1","c2","c3","c4","c5"} 
List<String> DList contains {"d1","d2"}

I would like to find all combinations with:

1) the combination a1 a2 vein the same as a2 a1 and so on

2) the number of elements per result set not being fixed: a combination possibility is per example merging all lists into one.. or each element in a list of its own or merging two elements in a list and the rest in another.. and so on..

I know it has to be a recursive function.. but that how far i am right now.. Any help would be appreciated. Thanks

I will suggest you to use Guava library's Collection2 class instead of writing your own method to generate permutation and combinations. There are so many cases like duplicate elements and many more you have to handle if you write your own code. Link to Guava Library: http://docs.guava-libraries.googlecode.com/git-history/release/javadoc/index.html Collection2: http://www.grepcode.com/file/repo1.maven.org/maven2/com.google.guava/guava/14.0/com/google/common/collect/Collections2.java#Collections2.permutations%28java.util.Collection%29 — Vaibhav Raj, Jun 16 '13 at 14:33

score 1 · Answer 1 · answered Jun 16 '13 at 15:23

Here is a utility class I implemented for this purpose a while ago. It uses array of int instead of list of String but it should give you the idea:

public final class Math {

    private Math() {
    }

    public static int[][] ncks(int n, int k) {
        int[] ks = new int[k];
        for (int i = 0; i < ks.length; i++) {
            ks[i] = i + 1;
        }

        int[][] ncks = new int[nck(n, k)][];

        boolean done = false;
        for (int j = 0; !done; j++) {
            ncks[j] = Arrays.copyOf(ks, ks.length);
            done = getNext(ks, n, k);
        }
        return ncks;
    }

    private static int nck(int n, int k) {
        int d = 1;
        int r = 1;

        int m = java.lang.Math.max(k, n - k) + 1;
        for (; m <= n; m++, d++) {
            r *= m;
            r /= d;
        }
        return r;
    }

    private static boolean getNext(int[] num, int n, int k) {
        int target = k - 1;

        num[target]++;
        if (num[target] > ((n - (k - target)) + 1)) {
            while (num[target] > ((n - (k - target)))) {
                target--;
                if (target < 0) {
                    break;
                }
            }

            if (target < 0) {
                return true;
            }

            num[target]++;
            for (int i = target + 1; i < num.length; i++) {
                num[i] = num[i - 1] + 1;
            }
        }
        return false;
    }

}

@SamithaChathuranga Have a look at [combinations](http://en.wikipedia.org/wiki/Combination) in WikiPedia — Attila T, Oct 07 '14 at 14:05

score 0 · Accepted Answer · answered Jun 16 '13 at 14:33

i did a similar thing for myself, this however would give you permutations of a1 a2 etc and not combinations, meaning the order does not matter.

public void permutation(String prefix, String str) {
    int n = str.length();
    if (n==0){}
    else {
        for (int i = 0; i < n; i++)
            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
    }

}

With this logic, you would have to turn your Lists into one long string and then send this method your string

Find out all combinations and permutations - Java

2 Answers2

Linked