Helper data structure for AiGA.

MultiplePermuter.java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class MultiplePermuter<T> {
    private final List<List<T>> data;
    private final Deque<Integer> indexStack;
    private final List<List<List<T>>> result;
    private final int numberOfGroups;
    
    MultiplePermuter(List<List<T>> data) {
        this.data = data;
        this.indexStack = new ArrayDeque<>(data.size());
        this.result = new ArrayList<>(computeResultListSize());
        this.numberOfGroups = data.size();
    }
    
    void process() {
        int initialN = data.get(0).size();
        indexStack.addLast(initialN);
        processImpl(0);
    }
    
    List<List<List<T>>> getResult() {
        return result;
    }
    
    private static <T> List<List<T>> deepCopy(List<List<T>> data) {
        List<List<T>> copy = new ArrayList<>(data.size());
        
        for (List<T> group : data) {
            copy.add(new ArrayList<>(group));
        }
        
        return copy;
    }
    
    private void processImpl(int currentRecursionDepth) {
        if (currentRecursionDepth == numberOfGroups) {
            List<List<T>> deepCopy = deepCopy(data);
            result.add(deepCopy);
            return;
        }
        
        int n = indexStack.getLast();
        
        if (n == 1) {
           
            if (currentRecursionDepth == numberOfGroups - 1) {
                processImpl(numberOfGroups);
                return;
            }
            
            indexStack.addLast(data.get(currentRecursionDepth).size());
            processImpl(currentRecursionDepth + 1);
            return;
        }
        
        List<T> currentElements = data.get(currentRecursionDepth);
        
        for (int i = 0; i < n - 1; i++) {
            
            indexStack
                    .addLast(data.get(currentRecursionDepth)
                    .size());
            
            processImpl(currentRecursionDepth + 1);
            indexStack.removeLast();
            
            if (n % 2 == 0) {
                swap(currentElements, i, n - 1);
            } else {
                swap(currentElements, 0, n - 1);
            }
        }
        
        indexStack.addLast(data.get(currentRecursionDepth).size());
        processImpl(currentRecursionDepth + 1);
        indexStack.removeLast();
    }
    
    private int computeResultListSize() {
        int count = 1;
        
        for (List<T> group : data) {
            count *= factorial(group.size());
        }
        
        return count;
    }
    
    private static int factorial(int n) {
        switch (n) {
            case 0:
            case 1:
                return 1;
                
            default:
                return factorial(n - 1);
        }
    }
    
    static <T> void swap(List<T> list, int a, int b) {
        T tmp = list.get(a);
        list.set(a, list.get(b));
        list.set(b, tmp);
    }
}

Tests.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Tests {

    public static void main(String[] args) {
        List<List<Integer>> data = new ArrayList<>();
        List<Integer> group0 = new ArrayList<>();
        List<Integer> group1 = new ArrayList<>();
        
//        group0.add(12);
//        group0.add(13);
        group1.add(1);
        group1.add(2);
        group1.add(3);
        
//        data.add(group0);
        data.add(group1);
        
        MultiplePermuter<Integer> mp = new MultiplePermuter<>(data);
        
        mp.process();
        
        List<List<List<Integer>>> result = mp.getResult();
        
        String resultString = convertDataToString(result);
        
        System.out.println("Result:");
        System.out.println(resultString);
    }
    
    private static int toLength(int i) {
        return String.format("%d", i).length();
    }
    
    private static <T> String convertGroups(List<List<T>> groups) {
        StringBuilder sb = new StringBuilder();
        boolean first = true;
        
        for (List<T> group : groups) {
            if (first) {
                first = false;
            } else {
                sb.append(' ');
            }
            
            sb.append(group.toString());
        }
        
        return sb.toString();
    }
    
    private static <T> String convertDataToString(List<List<List<T>>> data) {
        StringBuilder sb = new StringBuilder();
        int lineNumberMaxWidth = toLength(data.size());
        String lineFormat = "%" + lineNumberMaxWidth + "d: %s\n";
        
        for (int i = 0, lineNumber = 1; i < data.size(); i++, lineNumber++) {
            sb.append(
                    String.format(
                            lineFormat, 
                            lineNumber, 
                            convertGroups(data.get(i))));
        }
        
        return sb.toString();
    }
    
    public static List<int[]> generateAllPermutations(int[] array) {
        List<int[]> permutationList = new ArrayList<>();
        generateAllPerumutationsImpl(array, array.length, permutationList);
        return permutationList;
    }
    
    public static List<int[][]> generateAllPermutationsMultiple(int[][] array) {
        List<int[][]> doublePermutationList = new ArrayList<>();
        generateAllDoublePermutationsImpl(array, array.length, 0, doublePermutationList);
        return doublePermutationList;
    }
    
    private static void 
        generateAllDoublePermutationsImpl(
                int[][] arrayOfArrays, 
                int n, 
                int currentArrayIndex, 
                List<int[][]> doublePermutationList) {
        
        if (currentArrayIndex == arrayOfArrays.length) {
            int[][] newPermutation = new int[arrayOfArrays.length][];
            
            newPermutation[0] = Arrays.copyOf(arrayOfArrays[0],
                                              arrayOfArrays[0].length);
            
            newPermutation[1] = Arrays.copyOf(arrayOfArrays[1],
                                              arrayOfArrays[1].length);
            
            doublePermutationList.add(newPermutation);
            return;
        }
        
        int[] currentArray = arrayOfArrays[currentArrayIndex];
        int m = currentArray.length;
        
        if (m == 1) {
            
            return;
        }
        
        for (int i = 0; i < m - 1; i++) {
            generateAllDoublePermutationsImpl(arrayOfArrays, 
                                              m - 1,
                                              currentArrayIndex + 1, 
                                              doublePermutationList);
            
            if (m % 2 == 0) {
                swap(currentArray, i, m - 1);
            } else {
                swap(currentArray, 0, m - 1);
            }
        }
        
        generateAllDoublePermutationsImpl(arrayOfArrays, 
                                          m,
                                          currentArrayIndex + 1,
                                          doublePermutationList);
    }
    
    private static void generateAllPerumutationsImpl(
            int[] array, 
            int n, 
            List<int[]> permutationList) {
        
        if (n == 1) {
            permutationList.add(Arrays.copyOf(array, array.length));
            return;
        }
        
        for (int i = 0; i < n - 1; i++) {
            generateAllPerumutationsImpl(array,
                                         n - 1, 
                                         permutationList);
            if (n % 2 == 0) {
                swap(array, i, n - 1);
            } else {
                swap(array, 0, n - 1);
            }
        }
            
        generateAllPerumutationsImpl(array, 
                                     n - 1,
                                     permutationList);
    }
    
    private static void swap(int[] array, int a, int b) {
        int tmp = array[a];
        array[a] = array[b];
        array[b] = tmp;
    }
}

Tests2.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Tests {

    public static void main(String[] args) {
//        perm(new int[]{ 0, 1, 2 }, new int[]{ 4, 5, 6 });
        List<int[][]> permutations = nperm(new int[]{ 0, 1, },
                                           new int[]{ 2, 3, },
                                           new int[]{ 4, });
        
        for (int[][] permutation : permutations) {
            System.out.println(Arrays.toString(permutation[0]) + " " +
                               Arrays.toString(permutation[1]));
        }
        
        System.out.println("total: " + permutations.size());
        
//        List<List<Integer>> data = new ArrayList<>();
//        List<Integer> group0 = new ArrayList<>();
//        List<Integer> group1 = new ArrayList<>();
//        
////        group0.add(12);
////        group0.add(13);
//        group1.add(1);
//        group1.add(2);
//        group1.add(3);
//        
////        data.add(group0);
//        data.add(group1);
//        
//        MultiplePermuter<Integer> mp = new MultiplePermuter<>(data);
//        
//        mp.process();
//        
//        List<List<List<Integer>>> result = mp.getResult();
//        
//        String resultString = convertDataToString(result);
//        
//        System.out.println("Result:");
//        System.out.println(resultString);
    }
    
    private static int toLength(int i) {
        return String.format("%d", i).length();
    }
    
    private static <T> String convertGroups(List<List<T>> groups) {
        StringBuilder sb = new StringBuilder();
        boolean first = true;
        
        for (List<T> group : groups) {
            if (first) {
                first = false;
            } else {
                sb.append(' ');
            }
            
            sb.append(group.toString());
        }
        
        return sb.toString();
    }
    
    private static <T> String convertDataToString(List<List<List<T>>> data) {
        StringBuilder sb = new StringBuilder();
        int lineNumberMaxWidth = toLength(data.size());
        String lineFormat = "%" + lineNumberMaxWidth + "d: %s\n";
        
        for (int i = 0, lineNumber = 1; i < data.size(); i++, lineNumber++) {
            sb.append(
                    String.format(
                            lineFormat, 
                            lineNumber, 
                            convertGroups(data.get(i))));
        }
        
        return sb.toString();
    }
    
    public static List<int[]> generateAllPermutations(int[] array) {
        List<int[]> permutationList = new ArrayList<>();
        generateAllPerumutationsImpl(array, array.length, permutationList);
        return permutationList;
    }
    
    public static List<int[][]> generateAllPermutationsMultiple(int[][] array) {
        List<int[][]> doublePermutationList = new ArrayList<>();
        generateAllDoublePermutationsImpl(array, array.length, 0, doublePermutationList);
        return doublePermutationList;
    }
    
    private static void 
        generateAllDoublePermutationsImpl(
                int[][] arrayOfArrays, 
                int n, 
                int currentArrayIndex, 
                List<int[][]> doublePermutationList) {
        
        if (currentArrayIndex == arrayOfArrays.length) {
            int[][] newPermutation = new int[arrayOfArrays.length][];
            
            newPermutation[0] = Arrays.copyOf(arrayOfArrays[0],
                                              arrayOfArrays[0].length);
            
            newPermutation[1] = Arrays.copyOf(arrayOfArrays[1],
                                              arrayOfArrays[1].length);
            
            doublePermutationList.add(newPermutation);
            return;
        }
        
        int[] currentArray = arrayOfArrays[currentArrayIndex];
        int m = currentArray.length;
        
        if (m == 1) {
            
            return;
        }
        
        for (int i = 0; i < m - 1; i++) {
            generateAllDoublePermutationsImpl(arrayOfArrays, 
                                              m - 1,
                                              currentArrayIndex + 1, 
                                              doublePermutationList);
            
            if (m % 2 == 0) {
                swap(currentArray, i, m - 1);
            } else {
                swap(currentArray, 0, m - 1);
            }
        }
        
        generateAllDoublePermutationsImpl(arrayOfArrays, 
                                          m,
                                          currentArrayIndex + 1,
                                          doublePermutationList);
    }
    
    private static void generateAllPerumutationsImpl(
            int[] array, 
            int n, 
            List<int[]> permutationList) {
        
        if (n == 1) {
            permutationList.add(Arrays.copyOf(array, array.length));
            return;
        }
        
        for (int i = 0; i < n - 1; i++) {
            generateAllPerumutationsImpl(array,
                                         n - 1, 
                                         permutationList);
            if (n % 2 == 0) {
                swap(array, i, n - 1);
            } else {
                swap(array, 0, n - 1);
            }
        }
            
        generateAllPerumutationsImpl(array, 
                                     n - 1,
                                     permutationList);
    }
    
    private static void swap(int[] array, int a, int b) {
        int tmp = array[a];
        array[a] = array[b];
        array[b] = tmp;
    }
    
    static List<int[][]> nperm(int[]... arrays) {
        List<int[][]> result = new ArrayList<>();
        nperm(arrays, arrays[0].length, 0, result);
        return result;
    }
    
    static void nperm(int[][] arrays, 
                      int n, 
                      int arrayIndex, 
                      List<int[][]> result) {
        
        if (arrayIndex == arrays.length - 1) {
            if (n == 1) {
                // Add new found group permutation:
                int[][] permutation = deepCopy(arrays);
                result.add(permutation);
                return;
            }
            
            if (n % 2 == 0) {
                for (int i = 0; i < n - 1; i++) {
                    nperm(arrays, n - 1, arrayIndex, result);
                    swap(arrays[arrayIndex], i, n - 1);
                }
            } else {
                for (int i = 0; i < n - 1; i++) {
                    nperm(arrays, n - 1, arrayIndex, result);
                    swap(arrays[arrayIndex], 0, n - 1);
                }
            }
            
            nperm(arrays, n - 1, arrayIndex, result);
        } else {
            // Here, arrayIndex < arrays.length - 1:
            if (n == 1) {
                nperm(arrays, 
                      arrays[arrayIndex + 1].length,
                      arrayIndex + 1, 
                      result);
                
                return;
            }
            
            if (n % 2 == 0) {
                for (int i = 0; i < n - 1; i++) {
                    nperm(arrays, n - 1, arrayIndex, result);
                    swap(arrays[arrayIndex], i, n - 1);
                }
            } else {
                for (int i = 0; i < n - 1; i++) {
                    nperm(arrays, n - 1, arrayIndex, result);
                    swap(arrays[arrayIndex], 0, n - 1);
                }
            }
            
            nperm(arrays, n - 1, arrayIndex, result);
        }
    }
    
    private static int[][] deepCopy(int[][] arrays) {
        int[][] deepCopy = new int[arrays.length][];
        
        for (int i = 0; i < arrays.length; i++) {
            int[] group = Arrays.copyOf(arrays[i], arrays[i].length);
            deepCopy[i] = group;
        }
        
        return deepCopy;
    }
    
    static void perm(int[] arr1, int[] arr2) {
        perm(arr1, arr2, arr1.length, 0);
    }
    
    static void perm(int[] arr1, int[] arr2, int n, int arrayIndex) {
        if (arrayIndex == 2) {
            return;
        }
        
        if (arrayIndex == 0) {
            if (n == 1) {
                perm(arr1, arr2, arr2.length, 1);
                return;
            }
            
            if (n % 2 == 0) {
                for (int i = 0; i < n - 1; i++) {
                    perm(arr1, arr2, n - 1, 0);
                    swap(arr1, i, n - 1);
                }
            } else {
                for (int i = 0; i < n - 1; i++) {
                    perm(arr1, arr2, n - 1, 0);
                    swap(arr1, 0, n - 1);
                }
            }
            
            perm(arr1, arr2, n - 1, 0);
        } else if (arrayIndex == 1) {
            if (n == 1) {
                System.out.println(
                        "[" 
                                + Arrays.toString(arr1) 
                                + Arrays.toString(arr2) 
                                + "]");
                return;
            }
            
            if (n % 2 == 0) {
                for (int i = 0; i < n - 1; i++) {
                    perm(arr1, arr2, n - 1, 1);
                    swap(arr2, i, n - 1);
                }
            } else {
                for (int i = 0; i < n - 1; i++) {
                    perm(arr1, arr2, n - 1, 1);
                    swap(arr2, 0, n - 1);
                }
            }
            
            perm(arr1, arr2, n - 1, 1);
        }
    }
}