Java generates force member permutations from grouped members
I have a set of N groups, each group contains a variable number of elements. I want a function that will return all possible permutations (lengths from 1 to N) of all elements, where only one element per group can appear in any permutation.
For example, consider 2 groups {A, B}
and {C, D, E}
Then I want to return the following lists:
{A}, {B}, {C}, {D}, {E}, {AC}, {AD}, {AE}, {BC}, {BD}, {BE}, {CA}, {CB}, {DA}, {DB}, {EA}, {EB}
I tried to write a recursive function, but I cannot get it to work ... Here is what I have so far. Any help with his work would be much appreciated.
public class Test {
public static void main(String[] args) {
List<String> g1 = new ArrayList<String>();
g1.add("a");
g1.add("b");
List<String> g2 = new ArrayList<String>();
g2.add("c");
g2.add("d");
g2.add("e");
List<List<String>> groups = new ArrayList<List<String>>();
groups.add(g1);
groups.add(g2);
int size = 2;
List<List<String>> perms = generatePermutations(groups, size);
System.out.println(perms.size());
}
private static List<List<String>> generatePermutations(List<List<String>> groups, int size) {
List<List<String>> permutations = new ArrayList<List<String>>();
if ( groups.size() == 0 ) {
return permutations;
}
int n = groups.size();
for ( int i=0; i<n; i++ ) {
List<List<String>> otherGroups = new ArrayList<List<String>>(groups);
otherGroups.remove(i);
for ( int j=0; j<groups.get(i).size(); j++ ) {
String aKey = groups.get(i).get(j);
for ( List<String> subPerm : generatePermutations(otherGroups, size - 1) ) {
List<String> newList = new ArrayList<String>();
newList.add(aKey);
newList.addAll(subPerm);
permutations.add(newList);
}
}
}
return permutations;
}
}
source to share
When I have to solve problems like this, I always try to break them down into smaller tasks, each of which results in a different method call instead of using many inner loops from the beginning.
I would do something like this
public class Main {
public static void main(String[] args) {
char[] x={'A','B'},y={'C','D','E'},z={'F','G','H','I'};
char[][]group={x,y,z};
perm(group);
}
static void perm(char[][]g){
// Reorganize "g" changing the order of the components (x, y and z in this case)
// in all possible ways and call perm2().
// Here you perform the "upper level" permutation between sets.
// In this case it will result in 6 calls
perm2(g);
}
static void perm2(char[][]g){
// perform a "lower level" permutation on the given order of x, y, z
}
}
which is easier to check and verify. After all, when you find a solution, you can think of "compressing" the solution in a single method with multiple inner loops.
Hope it helps!
source to share
I may not understand the problem ... but I think the problem is a little confusing. I would like to help, but I need to understand the problem a little better. If I understood correctly, you need:
Find the set of permissions from the "set of sets", specified as an input:
{A,B} {C,D,E} --> {} {A,B} {C,D,E} {{A,B},{C,D,E}}
Then we calculate the Cartesian product of each member of the force set:
{} {A,B} {C,D,E} {{A,B},{C,D,E}} --> {} {A,B} {C,D,E} {AC,AD,AE,BC,BD,BE}
And then calculate the permutations over the contents of the resulting sets:
{} {A,B} {C,D,E} {AC,AD,AE,BC,BD,BE} --> {} {A,B} {C,D,E} {AC,AD,AE,BC,BD,BE,CA,DA,EA,CB,DB,EB}
Finally, all the sets will be "flattened" into one set:
{A,B,C,D,EAC,AD,AE,BC,BD,BE,CA,DA,EA,CB,DB,EB}
This is true? There are ways to calculate force, cartesian production, and permutation recursively.
source to share