Generating group permutations: an extended Heap's algorithm in Java

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. <1, 2> <3, 4>
2. <1, 2> <4, 3>
3. <2, 1> <3, 4>
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>
* <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) {
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) {
} else {
}
}

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

// 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) {
} else {
}
}

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

• We've been over avoiding string concatenation during print, but it seems like that feedback isn't taking hold. Commented Jan 3 at 23:53
• @Reinderien Point. Commented Jan 5 at 17:48