Suppose we have a sequence of sequences <1, 2> <3, 4>. There, we have two groups: <1, 2> and <3, 4>. The idea is to permute <1, 2>, and for each such permutation permute the <3, 4>. So all possible permutations are:
<1, 2> <3, 4><1, 2> <4, 3><2, 1> <3, 4><2, 1> <4, 3>
Also, my algorithm can handle both null elements (which are considered to be smaller than any non-null element by the comparator), and null or empty groups.
Actually, what you are about to see is an extended Heap's algorithm.
(The entire repository is at GitHub.)
Code
com.github.coderodde.util.combinatorics.MultipleGroupPermuter.java:
package com.github.coderodde.util.combinatorics; import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.Objects; /** * This class provides a method for generating permutations over groups of * elements. If the groups are {@code <1, 2>, null, <3, 4>, <5>}, the all * permutations produced by the method {@link computeGroupPermutations} are: * <ul> * <li>{@code [1, 2] null [3, 4] [5]}</li> * <li>{@code [1, 2] null [4, 3] [5]}</li> * <li>{@code [2, 1] null [3, 4] [5]}</li> * <li>{@code [2, 1] null [4, 3] [5]}</li> * </ul>. * <p> * Unfortunately, this permuter cannot "collapse" equal group permutation in * case some groups have equal elements. For example, {@code <null, 1, null>} * won't produce * <ul> * <li>{@code [1, null, null]}</li> * <li>{@code [null, 1, null]}</li> * <li>{@code [null, null, 1]},</li> * </ul> * but instead * <ol> * <li>{@code [1, null, null]}</li> * <li>{@code [1, null, null]}</li> * <li>{@code [null, 1, null]}</li> * <li>{@code [null, 1, null]}</li> * <li>{@code [null, null, 1]}</li> * <li>{@code [null, null, 1]}.</li> * </ol> * There is, however, a simple technique to mitigate the above issue: put all * the group permutations into a {@link HashSet}, and then call * {@code toArray()} on the hash set in order to obtain the unique group * permutations. * * @param <T> the type of the group element. */ public final class MultipleGroupPermuter<T> { // The actual group list. Will be modified by the computeGroupPermutations // method. private final List<List<T>> data; private final List<List<List<T>>> result; /** * Constructs this object with a given group list. * * @param groupList the list of groups. */ public MultipleGroupPermuter(List<List<T>> groupList) { Objects.requireNonNull(groupList, "The input group list is null."); this.data = groupList; this.result = new ArrayList<>(getNumberOfResultPermutations()); } /** * Returns the list holding all the group permutations. The algorithm under * the hood is an extended * <a href="https://en.wikipedia.org/wiki/Heap%27s_algorithm"> * Heap's algorithm</a>. * * @return the list of all the group permutations. */ public List<List<List<T>>> computeGroupPermutations() { Objects.requireNonNull(data, "The input data is null."); if (data.isEmpty()) { return new ArrayList<>(1); } computeGroupPermutationsImpl(getGroupSize(data.get(0)), 0); return result; } private void computeGroupPermutationsImpl(int n, int listIndex) { if (listIndex == data.size() - 1) { if (n == 1 || n == 0) { result.add(deepCopyGroupPermutation()); return; } if (n % 2 == 0) { for (int i = 0; i < n - 1; i++) { computeGroupPermutationsImpl(n - 1, listIndex); Collections.swap(data.get(listIndex), i, n - 1); } } else { for (int i = 0; i < n - 1; i++) { computeGroupPermutationsImpl(n - 1, listIndex); Collections.swap(data.get(listIndex), 0, n - 1); } } computeGroupPermutationsImpl(n - 1, listIndex); } else { // Here, listIndex < data.size() - 1: if (n == 1 || n == 0) { computeGroupPermutationsImpl( getGroupSize(data.get(listIndex + 1)), listIndex + 1); return; } if (n % 2 == 0) { for (int i = 0; i < n - 1; i++) { computeGroupPermutationsImpl(n - 1, listIndex); Collections.swap(data.get(listIndex), i, n - 1); } } else { for (int i = 0; i < n - 1; i++) { computeGroupPermutationsImpl(n - 1, listIndex); Collections.swap(data.get(listIndex), 0, n - 1); } } computeGroupPermutationsImpl(n - 1, listIndex); } } private List<List<T>> deepCopyGroupPermutation() { List<List<T>> copy = new ArrayList<>(data.size()); for (List<T> group : data) { if (group == null) { copy.add(null); } else { copy.add(new ArrayList<>(group)); } } return copy; } private int getNumberOfResultPermutations() { int numberOfPermutations = 1; for (List<T> group : data) { numberOfPermutations *= factorial(getGroupSize(group)); if (numberOfPermutations <= 0) { throw new IllegalArgumentException( "The current invocation would yell too many group " + "permutations."); } } return numberOfPermutations; } private static int factorial(int n) { switch (n) { case 0: case 1: return 1; default: return n * factorial(n - 1); } } private static <T> int getGroupSize(List<T> list) { if (list == null) { return 0; } return list.size(); } } com.github.coderodde.util.combinatorics.MultipleGroupPermuterDemo.java:
package com.github.coderodde.util.combinatorics; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.HashMap; import java.util.List; import java.util.Map; import java.util.Objects; public final class MultipleGroupPermuterDemo { public static void main(String[] args) { List<List<Integer>> data = new ArrayList<>(); data.add(null); data.add(Arrays.asList(1, 2, 3)); data.add(Arrays.asList(4)); data.add(Arrays.asList()); data.add(Arrays.asList(null, 6, 7, 5)); data.add(Arrays.asList()); data.add(null); // Make sure 'data' remains intact since the permuter modifies the order // of elements in the input data: List<List<Integer>> dataCopy = copyData(data); // Compute all the group permutations: List<List<List<Integer>>> groupPemutationList = new MultipleGroupPermuter<>(dataCopy) .computeGroupPermutations(); // Put all the group permutations into lexicographic order: sort(groupPemutationList); // Print all the group permutations in lexicographic order: System.out.println( convertGroupPemutationsToString(groupPemutationList)); // Build the map mapping each unique group permutations to its // multiplicity: Map<List<List<Integer>>, Integer> frequencyMap = new HashMap<>(groupPemutationList.size()); for (List<List<Integer>> groupPermutation : groupPemutationList) { frequencyMap.put(groupPermutation, frequencyMap.getOrDefault( groupPermutation, 0) + 1); } System.out.println( "Distinct group permutations: " + frequencyMap.size()); System.out.println( "Total group permutations: " + countAllPermutations(frequencyMap)); } /** * Counts the total number of group permutations stored in the * {@code frequencyMap}. * * @param <T> the element type of groups. * @param frequencyMap the map mapping each unique group permutation to its * multiplicity. * * @return the total number of group permutations. */ private static <T> int countAllPermutations(Map<List<List<T>>, Integer> frequencyMap) { int numberOfAllPermutations = 0; for (Integer count : frequencyMap.values()) { numberOfAllPermutations += count; } return numberOfAllPermutations; } /** * Computes the string representing the input group permutations. * * @param <T> the element type of groups. * @param groupPermutationList the list of group permutations. * @return the string describing all the group * permutations. */ private static <T> String convertGroupPemutationsToString( List<List<List<T>>> groupPermutationList) { StringBuilder stringBuilder = new StringBuilder(); boolean first = true; int numberOfGroupPemutations = groupPermutationList.size(); int maximumLineNumberWidth = Integer.toString(numberOfGroupPemutations).length(); String format = "%" + maximumLineNumberWidth + "d: %s"; int lineNumber = 1; for (List<List<T>> groupPermutation : groupPermutationList) { if (first) { first = false; } else { stringBuilder.append('\n'); } String groupPemutationString = convertGroupPemutationToString(groupPermutation); stringBuilder.append( String.format( format, lineNumber++, groupPemutationString)); } return stringBuilder.toString(); } /** * Returns the string representing the input of a single group permutation. * * @param <T> the element type of groups. * @param groupPemutation the input group permutation. * @return the string representing the input group. */ private static <T> String convertGroupPemutationToString(List<List<T>> groupPemutation) { StringBuilder stringBuilder = new StringBuilder(); boolean first = true; for (List<T> group : groupPemutation) { if (first) { first = false; } else { stringBuilder.append(' '); } stringBuilder.append(Objects.toString(group)); } return stringBuilder.toString(); } /** * Returns the deep copy of {@code data}. We need this in order to keep the * actual data for the permuter intact. * * @param <T> the element type of groups. * @param data the data to deep copy. * @return the deep copy of the input data. */ private static <T> List<List<T>> copyData(List<List<T>> data) { List<List<T>> deepCopy = new ArrayList<>(data.size()); for (List<T> list : data) { if (list == null) { deepCopy.add(null); } else { deepCopy.add(new ArrayList<>(list)); } } return deepCopy; } /** * Sorts the input group permutation list into lexicographic order. Note * that this sort routine deems {@code null} values less than any other * non-null integer. * * @param groupPermutationList the list of all the group permutations. */ private static void sort(List<List<List<Integer>>> groupPermutationList) { GroupComparator<Integer> groupComparator = new GroupComparator<>(Integer::compareTo); GroupPermutationComparator<Integer> groupPermutationComparator = new GroupPermutationComparator<>(groupComparator); Collections.sort(groupPermutationList, groupPermutationComparator); } } com.github.coderodde.util.combinatorics.GroupComparator.java:
package com.github.coderodde.util.combinatorics; import java.util.Comparator; import java.util.List; /** * This class implements a comparator for comparing the groups. Note that it * won't accept groups of different sizes and will throw an * {@link IllegalArgumentException}. * * @param <T> the element type of a group. */ public final class GroupComparator<T> implements Comparator<List<T>> { private final Comparator<T> elementComparator; public GroupComparator(Comparator<T> elementComparator) { this.elementComparator = elementComparator; } @Override public int compare(List<T> group1, List<T> group2) { if (group1 == null) { if (group2 == null) { // Both null: return 0; } else { // group1 null and group2 is non null: return -1; } } else { // Here, group1 != null: if (group2 == null) { return 1; } } // Here, both group1 and group2 are not null: if (group1.size() != group2.size()) { // Size mismatch, throw: throw new IllegalArgumentException( "The input groups are of differnt sizes. " + group1.size() + " vs. " + group2.size()); } // Here, group1 != null and group2 != null and both of the same size: for (int i = 0; i < group1.size(); i++) { T element1 = group1.get(i); T element2 = group2.get(i); if (element1 == null) { if (element2 == null) { return 0; } else { return -1; } } else { // Here, element1 != null: if (element2 == null) { return 1; } } int cmp = elementComparator.compare(element1, element2); if (cmp != 0) { // Found a different spot, return: return cmp; } } // Here, both group1 and group2 are the same: return 0; } } com.github.coderodde.util.combinatorics.GroupPermutationComparator.java:
package com.github.coderodde.util.combinatorics; import java.util.Comparator; import java.util.List; /** * This class implements a comparator comparing group permutations It accepts * only group permutations of the same size. If the aforementioned invariant is * broken, this comparator throws {@link IllegalArgumentException}. * * @param <T> the element type of groups. */ public final class GroupPermutationComparator<T> implements Comparator<List<List<T>>> { private final Comparator<List<T>> groupComparator; public GroupPermutationComparator(Comparator<List<T>> groupComparator) { this.groupComparator = groupComparator; } @Override public int compare(List<List<T>> groupPermutation1, List<List<T>> groupPermutation2) { if (groupPermutation1.size() != groupPermutation2.size()) { throw new IllegalArgumentException( "The input group permutations are of different size. " + groupPermutation1.size() + " vs. " + groupPermutation2.size()); } for (int i = 0; i < groupPermutation1.size(); i++) { List<T> group1 = groupPermutation1.get(i); List<T> group2 = groupPermutation2.get(i); int cmp = groupComparator.compare(group1, group2); if (cmp != 0) { return cmp; } } return 0; } } Demo output
The demo program prints:
1: null [1, 2, 3] [4] [] [null, 6, 7, 5] [] null 2: null [1, 2, 3] [4] [] [null, 7, 6, 5] [] null 3: null [1, 2, 3] [4] [] [null, 5, 6, 7] [] null 4: null [1, 2, 3] [4] [] [null, 6, 5, 7] [] null 5: null [1, 2, 3] [4] [] [null, 7, 5, 6] [] null 6: null [1, 2, 3] [4] [] [null, 5, 7, 6] [] null 7: null [1, 2, 3] [4] [] [5, null, 6, 7] [] null 8: null [1, 2, 3] [4] [] [5, null, 7, 6] [] null 9: null [1, 2, 3] [4] [] [5, 6, null, 7] [] null 10: null [1, 2, 3] [4] [] [5, 6, 7, null] [] null 11: null [1, 2, 3] [4] [] [5, 7, null, 6] [] null 12: null [1, 2, 3] [4] [] [5, 7, 6, null] [] null 13: null [1, 2, 3] [4] [] [6, null, 7, 5] [] null 14: null [1, 2, 3] [4] [] [6, null, 5, 7] [] null 15: null [1, 2, 3] [4] [] [6, 5, null, 7] [] null 16: null [1, 2, 3] [4] [] [6, 5, 7, null] [] null 17: null [1, 2, 3] [4] [] [6, 7, null, 5] [] null 18: null [1, 2, 3] [4] [] [6, 7, 5, null] [] null 19: null [1, 2, 3] [4] [] [7, null, 6, 5] [] null 20: null [1, 2, 3] [4] [] [7, null, 5, 6] [] null 21: null [1, 2, 3] [4] [] [7, 5, null, 6] [] null 22: null [1, 2, 3] [4] [] [7, 5, 6, null] [] null 23: null [1, 2, 3] [4] [] [7, 6, null, 5] [] null 24: null [1, 2, 3] [4] [] [7, 6, 5, null] [] null 25: null [1, 3, 2] [4] [] [null, 5, 6, 7] [] null 26: null [1, 3, 2] [4] [] [null, 6, 5, 7] [] null 27: null [1, 3, 2] [4] [] [null, 7, 5, 6] [] null 28: null [1, 3, 2] [4] [] [null, 5, 7, 6] [] null 29: null [1, 3, 2] [4] [] [null, 7, 6, 5] [] null 30: null [1, 3, 2] [4] [] [null, 6, 7, 5] [] null 31: null [1, 3, 2] [4] [] [5, null, 6, 7] [] null 32: null [1, 3, 2] [4] [] [5, null, 7, 6] [] null 33: null [1, 3, 2] [4] [] [5, 6, null, 7] [] null 34: null [1, 3, 2] [4] [] [5, 6, 7, null] [] null 35: null [1, 3, 2] [4] [] [5, 7, null, 6] [] null 36: null [1, 3, 2] [4] [] [5, 7, 6, null] [] null 37: null [1, 3, 2] [4] [] [6, null, 5, 7] [] null 38: null [1, 3, 2] [4] [] [6, null, 7, 5] [] null 39: null [1, 3, 2] [4] [] [6, 5, null, 7] [] null 40: null [1, 3, 2] [4] [] [6, 5, 7, null] [] null 41: null [1, 3, 2] [4] [] [6, 7, null, 5] [] null 42: null [1, 3, 2] [4] [] [6, 7, 5, null] [] null 43: null [1, 3, 2] [4] [] [7, null, 5, 6] [] null 44: null [1, 3, 2] [4] [] [7, null, 6, 5] [] null 45: null [1, 3, 2] [4] [] [7, 5, null, 6] [] null 46: null [1, 3, 2] [4] [] [7, 5, 6, null] [] null 47: null [1, 3, 2] [4] [] [7, 6, null, 5] [] null 48: null [1, 3, 2] [4] [] [7, 6, 5, null] [] null 49: null [2, 1, 3] [4] [] [null, 7, 6, 5] [] null 50: null [2, 1, 3] [4] [] [null, 6, 7, 5] [] null 51: null [2, 1, 3] [4] [] [null, 6, 5, 7] [] null 52: null [2, 1, 3] [4] [] [null, 5, 6, 7] [] null 53: null [2, 1, 3] [4] [] [null, 5, 7, 6] [] null 54: null [2, 1, 3] [4] [] [null, 7, 5, 6] [] null 55: null [2, 1, 3] [4] [] [5, null, 6, 7] [] null 56: null [2, 1, 3] [4] [] [5, null, 7, 6] [] null 57: null [2, 1, 3] [4] [] [5, 6, null, 7] [] null 58: null [2, 1, 3] [4] [] [5, 6, 7, null] [] null 59: null [2, 1, 3] [4] [] [5, 7, null, 6] [] null 60: null [2, 1, 3] [4] [] [5, 7, 6, null] [] null 61: null [2, 1, 3] [4] [] [6, null, 7, 5] [] null 62: null [2, 1, 3] [4] [] [6, null, 5, 7] [] null 63: null [2, 1, 3] [4] [] [6, 5, null, 7] [] null 64: null [2, 1, 3] [4] [] [6, 5, 7, null] [] null 65: null [2, 1, 3] [4] [] [6, 7, null, 5] [] null 66: null [2, 1, 3] [4] [] [6, 7, 5, null] [] null 67: null [2, 1, 3] [4] [] [7, null, 6, 5] [] null 68: null [2, 1, 3] [4] [] [7, null, 5, 6] [] null 69: null [2, 1, 3] [4] [] [7, 5, null, 6] [] null 70: null [2, 1, 3] [4] [] [7, 5, 6, null] [] null 71: null [2, 1, 3] [4] [] [7, 6, null, 5] [] null 72: null [2, 1, 3] [4] [] [7, 6, 5, null] [] null 73: null [2, 3, 1] [4] [] [null, 6, 7, 5] [] null 74: null [2, 3, 1] [4] [] [null, 7, 6, 5] [] null 75: null [2, 3, 1] [4] [] [null, 5, 6, 7] [] null 76: null [2, 3, 1] [4] [] [null, 6, 5, 7] [] null 77: null [2, 3, 1] [4] [] [null, 7, 5, 6] [] null 78: null [2, 3, 1] [4] [] [null, 5, 7, 6] [] null 79: null [2, 3, 1] [4] [] [5, null, 6, 7] [] null 80: null [2, 3, 1] [4] [] [5, null, 7, 6] [] null 81: null [2, 3, 1] [4] [] [5, 6, null, 7] [] null 82: null [2, 3, 1] [4] [] [5, 6, 7, null] [] null 83: null [2, 3, 1] [4] [] [5, 7, null, 6] [] null 84: null [2, 3, 1] [4] [] [5, 7, 6, null] [] null 85: null [2, 3, 1] [4] [] [6, null, 7, 5] [] null 86: null [2, 3, 1] [4] [] [6, null, 5, 7] [] null 87: null [2, 3, 1] [4] [] [6, 5, null, 7] [] null 88: null [2, 3, 1] [4] [] [6, 5, 7, null] [] null 89: null [2, 3, 1] [4] [] [6, 7, null, 5] [] null 90: null [2, 3, 1] [4] [] [6, 7, 5, null] [] null 91: null [2, 3, 1] [4] [] [7, null, 6, 5] [] null 92: null [2, 3, 1] [4] [] [7, null, 5, 6] [] null 93: null [2, 3, 1] [4] [] [7, 5, null, 6] [] null 94: null [2, 3, 1] [4] [] [7, 5, 6, null] [] null 95: null [2, 3, 1] [4] [] [7, 6, null, 5] [] null 96: null [2, 3, 1] [4] [] [7, 6, 5, null] [] null 97: null [3, 1, 2] [4] [] [null, 7, 5, 6] [] null 98: null [3, 1, 2] [4] [] [null, 5, 7, 6] [] null 99: null [3, 1, 2] [4] [] [null, 7, 6, 5] [] null 100: null [3, 1, 2] [4] [] [null, 6, 7, 5] [] null 101: null [3, 1, 2] [4] [] [null, 6, 5, 7] [] null 102: null [3, 1, 2] [4] [] [null, 5, 6, 7] [] null 103: null [3, 1, 2] [4] [] [5, null, 7, 6] [] null 104: null [3, 1, 2] [4] [] [5, null, 6, 7] [] null 105: null [3, 1, 2] [4] [] [5, 6, null, 7] [] null 106: null [3, 1, 2] [4] [] [5, 6, 7, null] [] null 107: null [3, 1, 2] [4] [] [5, 7, null, 6] [] null 108: null [3, 1, 2] [4] [] [5, 7, 6, null] [] null 109: null [3, 1, 2] [4] [] [6, null, 7, 5] [] null 110: null [3, 1, 2] [4] [] [6, null, 5, 7] [] null 111: null [3, 1, 2] [4] [] [6, 5, null, 7] [] null 112: null [3, 1, 2] [4] [] [6, 5, 7, null] [] null 113: null [3, 1, 2] [4] [] [6, 7, null, 5] [] null 114: null [3, 1, 2] [4] [] [6, 7, 5, null] [] null 115: null [3, 1, 2] [4] [] [7, null, 5, 6] [] null 116: null [3, 1, 2] [4] [] [7, null, 6, 5] [] null 117: null [3, 1, 2] [4] [] [7, 5, null, 6] [] null 118: null [3, 1, 2] [4] [] [7, 5, 6, null] [] null 119: null [3, 1, 2] [4] [] [7, 6, null, 5] [] null 120: null [3, 1, 2] [4] [] [7, 6, 5, null] [] null 121: null [3, 2, 1] [4] [] [null, 7, 6, 5] [] null 122: null [3, 2, 1] [4] [] [null, 6, 7, 5] [] null 123: null [3, 2, 1] [4] [] [null, 6, 5, 7] [] null 124: null [3, 2, 1] [4] [] [null, 5, 6, 7] [] null 125: null [3, 2, 1] [4] [] [null, 5, 7, 6] [] null 126: null [3, 2, 1] [4] [] [null, 7, 5, 6] [] null 127: null [3, 2, 1] [4] [] [5, null, 6, 7] [] null 128: null [3, 2, 1] [4] [] [5, null, 7, 6] [] null 129: null [3, 2, 1] [4] [] [5, 6, null, 7] [] null 130: null [3, 2, 1] [4] [] [5, 6, 7, null] [] null 131: null [3, 2, 1] [4] [] [5, 7, null, 6] [] null 132: null [3, 2, 1] [4] [] [5, 7, 6, null] [] null 133: null [3, 2, 1] [4] [] [6, null, 7, 5] [] null 134: null [3, 2, 1] [4] [] [6, null, 5, 7] [] null 135: null [3, 2, 1] [4] [] [6, 5, null, 7] [] null 136: null [3, 2, 1] [4] [] [6, 5, 7, null] [] null 137: null [3, 2, 1] [4] [] [6, 7, null, 5] [] null 138: null [3, 2, 1] [4] [] [6, 7, 5, null] [] null 139: null [3, 2, 1] [4] [] [7, null, 6, 5] [] null 140: null [3, 2, 1] [4] [] [7, null, 5, 6] [] null 141: null [3, 2, 1] [4] [] [7, 5, null, 6] [] null 142: null [3, 2, 1] [4] [] [7, 5, 6, null] [] null 143: null [3, 2, 1] [4] [] [7, 6, null, 5] [] null 144: null [3, 2, 1] [4] [] [7, 6, 5, null] [] null Distinct group permutations: 144 Total group permutations: 144 Critique request
As always, I would to hear anything that comes to mind.
