D. Ataro D. Ataro - 24 days ago 7
Java Question

Permutation of a 2D array

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...

The first list is a sort of wrapper for the whole thing. It contains groupings of two lists containing symbols. This is because the symbols are not supposed to be seperate from one another when contained in a grouping.

The second list is always of length two, and each contains a list of unique symbols. As to why it is two, do not ask me for this question. It would be nice for this program to have the capability to also be able to deal with this list being greater than two in length.

The third list contains all the symbols, and there are two of those per wrapper, as stated above.

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]],


What I have tried so far is to put these into a good old traditional permutations method that works for a single array (or list, if you will), and tried to modify that into working with multidimensional arrays. Surely there is a good and simple way to do this, preferably with the use of recursion. Should there be a way without, that is totally okay.

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));
  }
}