Add some additional utilities

This adds some list/set utilities, including an implementation of 'plain
changes' for generating list permutations that I suspect needs some
debugging.

2 files changed, 164 insertions, 0 deletions

diff --git a/base/src/main/java/bjc/utils/funcutils/ListUtils.java b/base/src/main/java/bjc/utils/funcutils/ListUtils.java
index b86017b..55e0afa 100644
--- a/base/src/main/java/bjc/utils/funcutils/ListUtils.java
+++ b/base/src/main/java/bjc/utils/funcutils/ListUtils.java
@@ -3,6 +3,7 @@ package bjc.utils.funcutils;
 import java.util.ArrayList;
 import java.util.Iterator;
 import java.util.List;
+import java.util.LinkedList;
 import java.util.function.Function;
 import java.util.function.Supplier;
 
@@ -311,4 +312,122 @@ public class ListUtils {
 
 		return res;
 	}
+
+	/**
+	 * Generate all of the permuations of a list.
+	 *
+	 * This is a version of Algorith P (Plain Changes) from Knuth (vol 4A,
+	 * pg 322)
+	 *
+	 * @param list
+	 * 	The list to generate permutations from.
+	 * @return The list of permutations of the list.
+	 */
+	public static <T> List<List<T>> permuteList(List<T> list) {
+		List<List<T>> permutes = new LinkedList<>();
+
+		/*
+		 * Special-case small usages.
+		 */
+		if(list.size() == 0) {
+			return permutes;
+		}
+
+		if(list.size() == 1) {
+			permutes.add(list);
+
+			return permutes;
+		}
+
+		if(list.size() == 2) {
+			T elm1 = list.get(0);
+			T elm2 = list.get(1);
+
+			List<T> currPerm = new ArrayList<>(2);
+
+			currPerm.add(elm1);
+			currPerm.add(elm2);
+
+			permutes.add(currPerm);
+
+			currPerm = new ArrayList<>(2);
+
+			currPerm.add(elm2);
+			currPerm.add(elm1);
+
+			permutes.add(currPerm);
+
+			return permutes;
+		}
+
+		int[] auxC = new int[list.size()];
+		int[] auxO = new int[list.size()];
+
+		for(int i = 0; i < list.size(); i++) {
+			auxC[i] = 0;
+			auxO[i] = 1;
+		}
+
+		List<T> currentPermute = new ArrayList<>(list.size());
+		for(T elm : list) {
+			currentPermute.add(elm);
+		}
+		permutes.add(currentPermute);
+
+		int j = list.size() - 1;
+		int s = 0;
+
+		while(true) {
+			int q = auxC[j] + auxO[j];
+
+			if(q < 0) {
+				auxO[j] = -auxO[j];
+				j -= 1;
+
+				continue;
+			}
+
+			if(q == j) {
+				if(j == 0) break;
+
+				s += 1;
+
+				auxO[j] = -auxO[j];
+				j -= 1;
+
+				continue;
+			}
+
+			int idx1 = j - auxC[j] + s;
+			int idx2 = j - q - s;
+
+			swapList(list, idx1, idx2);
+
+			auxC[j] = q;
+
+			currentPermute = new ArrayList<>(list.size());
+			for(T elm : list) {
+				currentPermute.add(elm);
+			}
+			permutes.add(currentPermute);
+
+			j = list.size() - 1;
+			s = 0;
+		}
+
+		return permutes;
+	}
+
+	private static <T> List<List<T>> powerList(List<T> list) {
+		List<List<T>> results = new LinkedList<>();
+
+		return results;
+	}
+
+	private static <T> void swapList(List<T> list, int a, int b) {
+		T tmp = list.get(a);
+
+		list.set(a, list.get(b));
+		list.set(b, tmp);
+	}
 }
diff --git a/base/src/main/java/bjc/utils/funcutils/SetUtils.java b/base/src/main/java/bjc/utils/funcutils/SetUtils.java
new file mode 100644
index 0000000..eac417c
--- /dev/null
+++ b/base/src/main/java/bjc/utils/funcutils/SetUtils.java
@@ -0,0 +1,45 @@
+package bjc.utils.funcutils;
+
+import java.util.ArrayList;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Set;
+
+public class SetUtils {
+	public static <T> Set<Set<T>> powerSet(Set<T> originalSet) {
+		Set<Set<T>> sets = new HashSet<Set<T>>();
+
+		if (originalSet.isEmpty()) {
+			sets.add(new HashSet<T>());
+			return sets;
+		}
+
+		List<T> list = new ArrayList<T>(originalSet);
+
+		T head = list.get(0);
+
+		Set<T> rest = new HashSet<T>(list.subList(1, list.size()));
+
+		for (Set<T> set : powerSet(rest)) {
+			Set<T> newSet = new HashSet<T>();
+
+			newSet.add(head);
+			newSet.addAll(set);
+
+			sets.add(newSet);
+			sets.add(set);
+		}
+
+		return sets;
+	}
+
+	public static <T> Set<T> toSet(T... elms) {
+		Set<T> set = new HashSet<>();
+
+		for(T elm : elms) {
+			set.add(elm);
+		}
+
+		return set;
+	}
+}