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.
