D. Ataro - 6 months ago 30

Java Question

Here comes another question about permutations. I have done everything I can to formulate my problem as good as I possibly can. Feel free to ask questions if there is something you do not understand.

I have a list, containing a list, containing a list, containing a symbol.

`List<List<List<Symbol>>> list = new ArrayList<List<List<Symbol>>>();`

The symbol class simply takes on a value and keeps track of some important features of what I am creating. All the symbols in the structure are different from one another.

There are however some difficulties as to just switching places in all different ways, since...

What I want with this is to generate all possible permutations and analyze them. That is, I would like the symbols to switch into all possible combination whilst still being contained within its respective list.

This could look something like this (written in pseudo-code, depicting the list-like structure mentioned above).

`[[a, b, c], [d, e, f]],`

[[g, h, i, j], [k, l, m, n]],

[[o, p], [q, r]],

[[s, t, u], [v, x, y]],

An example for what one of the (possibly thousands) of permutations could be, is this.

`[[c, a, b], [d, f, e]],`

[[g, h, j, i], [k, l, m, n]],

[[o, p], [q, r]],

[[s, t, u], [v,y, x]],

Once again, if you have any questions above what I just wrote, feel free to post a comment.

Kind regards,

Answer

Here is a recursive solution. `permutationsList`

can take lists with an arbitrary number of dimensions. Btw. the example you gave has nearly 3 million permutations. My program takes several seconds to calculate all of them.

```
import java.util.*;
public class Perm {
static <T> List<List<T>> permutations(List<T> list) {
if(list.isEmpty()) return new LinkedList<>();
List<List<T>> result = new LinkedList<>();
for(int i = 0; i < list.size(); i++) {
T elem = list.get(i);
List<T> copy = new LinkedList<>(list);
copy.remove(i);
List<List<T>> permRest = permutations(copy);
if(permRest.isEmpty()) permRest.add(new LinkedList<>());
for(List<T> perm: permRest) {
List<T> permCopy = new LinkedList<>(perm);
permCopy.add(0, elem);
result.add(permCopy);
}
}
return result;
}
@SuppressWarnings("unchecked")
static List<List> permutationsLists(List list) {
if(list.size() == 0) {
return new LinkedList<>();
} if(!(list.get(0) instanceof List)) {
return permutations(list);
} else {
List<List> permutationsFirst = permutationsLists((List)list.get(0));
List<List> permutationsRest = (List<List>)permutationsLists(list.subList(1, list.size()));
if(permutationsRest.size() == 0) permutationsRest.add(new LinkedList());
List<List> result = new LinkedList<>();
for(List pf: permutationsFirst) {
for(List pr: permutationsRest) {
List copy = new LinkedList(pr);
copy.add(0, pf);
result.add(copy);
}
}
return result;
}
}
public static void main(String[] args) {
/*
List<List<List<String>>> list = Arrays.asList(
Arrays.asList(Arrays.asList("a", "b", "c"), Arrays.asList("d", "e", "f")),
Arrays.asList(Arrays.asList("g", "h", "i", "j"), Arrays.asList("k", "l", "m", "n")),
Arrays.asList(Arrays.asList("o", "p"), Arrays.asList("q", "r")),
Arrays.asList(Arrays.asList("s", "t", "u"), Arrays.asList("v", "w", "x"))
);
*/
List<List<Integer>> list = Arrays.asList(Arrays.asList(1,2,3), Arrays.asList(4,5));
System.out.println(permutationsLists(list));
}
}
```