Generate all combinations of place without redundancy in Java

Question

I want an algorithm to display all possibes combinations. A person can not work in several jobs simultaneously. In the example below if there are only 5 people and 3 jobs. So there are 5 X 4 X 3 combinations, So 60 combinations. The solution should be done in Java. I can use the Guava library. I look particularly good development practice (not just the solution).

IN:

John,Peter,Dylan,Bryan,Pharell and Job A, Job B, Job C

OUT:

Solution 1:
Job A: John
Job B: Peter
Job C: Dylan

Solution 2:
Job A: Pharell
Job B: John
Job C: Peter

Solution 3:
Job A: John
Job B: Pharell
Job C: Peter

...

Solution 60:
Job A: John
Job B: Pharell
Job C: Bryan

use a Set. Generate solutions and add them to the set; any redundancies will be eliminated. There are probably more efficient ways, but this is IMOP the easiest to code. The Set is parametrized, so you'll need a class to represent all the data and you'll need to override equals and getHashCode. — D. Ben Knoble, Sep 27 '15 at 21:24
As you can see, you always have A, B, C in this order from the second set. Just ignore it and solve the following problem: find all permutations of 3 elements that can be obtained using elements from a 5-element set. Recursion will help you. — ROMANIA_engineer, Sep 27 '15 at 21:44
This Q&A lists a bunch of relevant algorithms: http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n. Read it, pick one, code it in Java. — Stephen C, Sep 27 '15 at 22:19
Only "helpYou" understand my question.(I look particularly good development practice (not just the solution). great thank you !!! — Stéphane GRILLON, Sep 28 '15 at 12:16
yes bhspencer, I try and I have a solution but I looking for the best development practice (not just the solution). — Stéphane GRILLON, Sep 28 '15 at 21:22

score 1 · Accepted Answer · edited May 23 '17 at 10:27

Here you can see a solution based on amit's answer for subsets and guava - Collections2 for permutations:

import com.google.common.collect.Collections2;

import java.util.*;

public class Test {
    private static void getSubsets(List<String> superSet, int idx, Set<String> current, List solution) {
        if (current.size() == 3) {
            solution.add(new HashSet<>(current));
            return;
        }
        if (idx == superSet.size()) {
            return;
        }
        String x = superSet.get(idx);
        current.add(x);
        getSubsets(superSet, idx + 1, current, solution);
        current.remove(x);
        getSubsets(superSet, idx + 1, current, solution);
    }

    public static List<Set<Integer>> getSubsets(List<String> superSet) {
        List res = new ArrayList<>();
        getSubsets(superSet, 0, new HashSet<>(), res);
        return res;
    }

    public static void main(String[] args) {
        List<String> initialSet = new ArrayList<String>() {{
            add("John");
            add("Peter");
            add("Dylan");
            add("Bryan");
            add("Pharell");
        }};
        List<Set<Integer>> subsets = getSubsets(initialSet);
        int counter = 1;
        for (Set s : subsets) {
            Collection<List<String>> results = Collections2.permutations(s);
            for (List<String> words : results) {
                System.out.println("Solution " + counter++);
                System.out.println("Job A: " + words.get(0));
                System.out.println("Job B: " + words.get(1));
                System.out.println("Job C: " + words.get(2));
                System.out.println();
            }
        }
    }
}

So, because you always have A, B and C in this order, they were ignored during the implementation. You can see them only when I print the output. So, the problem became: find all 3-element permutations for a 5-element set.

Firstly, there were generated all 3-element sets for a 5-element set and then every obtained set was permuted.

Generate all combinations of place without redundancy in Java

1 Answers1