add Cnm and Anm to CollectionUtil (#101)
* add Cmn to CollectionUtil
Change-Id: I873e5c41229a8743ca5753d11c3b5e608b2e9298
* add Anm function
Change-Id: Idcb24ba80c61fb53c9744d7ab5d2a379e16a4ad3
diff --git a/hugegraph-common/src/main/java/com/baidu/hugegraph/util/CollectionUtil.java b/hugegraph-common/src/main/java/com/baidu/hugegraph/util/CollectionUtil.java
index 85ab87c..6b6d638 100644
--- a/hugegraph-common/src/main/java/com/baidu/hugegraph/util/CollectionUtil.java
+++ b/hugegraph-common/src/main/java/com/baidu/hugegraph/util/CollectionUtil.java
@@ -20,9 +20,11 @@
package com.baidu.hugegraph.util;
import java.lang.reflect.Array;
+import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
+import java.util.Deque;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
@@ -30,6 +32,7 @@
import java.util.Map;
import java.util.Set;
import java.util.concurrent.ThreadLocalRandom;
+import java.util.function.Function;
public final class CollectionUtil {
@@ -236,4 +239,216 @@
}
return result;
}
+
+ /**
+ * Cross combine the A(n, n) combinations of each part in parts
+ * @param parts a list of part, like [{a,b}, {1,2}, {x,y}]
+ * @return List<List<Integer>> all combinations like
+ * [{a,b,1,2,x,y}, {a,b,1,2,y,x}, {a,b,2,1,x,y}, {a,b,2,1,y,x}...]
+ */
+ public static <T> List<List<T>> crossCombineParts(List<List<T>> parts) {
+ List<List<T>> results = new ArrayList<>();
+ Deque<List<T>> selected = new ArrayDeque<>();
+ crossCombineParts(parts, 0, selected, results);
+ return results;
+ }
+
+ private static <T> void crossCombineParts(List<List<T>> parts,
+ int level,
+ Deque<List<T>> selected,
+ List<List<T>> results) {
+ assert level < parts.size();
+ List<T> part = parts.get(level);
+ for (List<T> combination : anm(part)) {
+ selected.addLast(combination);
+
+ if (level < parts.size() - 1) {
+ crossCombineParts(parts, level + 1, selected, results);
+ } else if (level == parts.size() - 1) {
+ results.add(flatToList(selected));
+ }
+
+ selected.removeLast();
+ }
+ }
+
+ private static <T> List<T> flatToList(Deque<List<T>> parts) {
+ List<T> list = new ArrayList<>();
+ for (List<T> part : parts) {
+ list.addAll(part);
+ }
+ return list;
+ }
+
+ /**
+ * Traverse C(n, m) combinations of a list
+ * @param all list to contain all items for combination
+ * @param n m of C(n, m)
+ * @param m n of C(n, m)
+ * @return List<List<T>> all combinations
+ */
+ public static <T> List<List<T>> cnm(List<T> all, int n, int m) {
+ List<List<T>> combs = new ArrayList<>();
+ cnm(all, n, m, comb -> {
+ combs.add(comb);
+ return false;
+ });
+ return combs;
+ }
+
+ /**
+ * Traverse C(n, m) combinations of a list to find first matched
+ * result combination and call back with the result.
+ * @param all list to contain all items for combination
+ * @param n m of C(n, m)
+ * @param m n of C(n, m)
+ * @return true if matched any kind of items combination else false, the
+ * callback can always return false if want to traverse all combinations
+ */
+ public static <T> boolean cnm(List<T> all, int n, int m,
+ Function<List<T>, Boolean> callback) {
+ return cnm(all, n, m, 0, null, callback);
+ }
+
+ /**
+ * Traverse C(n, m) combinations of a list to find first matched
+ * result combination and call back with the result.
+ * @param all list to contain all items for combination
+ * @param n n of C(n, m)
+ * @param m m of C(n, m)
+ * @param current current position in list
+ * @param selected list to contains selected items
+ * @return true if matched any kind of items combination else false, the
+ * callback can always return false if want to traverse all combinations
+ */
+ private static <T> boolean cnm(List<T> all, int n, int m,
+ int current, List<T> selected,
+ Function<List<T>, Boolean> callback) {
+ assert n <= all.size();
+ assert m <= n;
+ assert current <= all.size();
+ if (selected == null) {
+ selected = new ArrayList<>(m);
+ }
+
+ if (m == 0) {
+ assert selected.size() > 0 : selected;
+ // All n items are selected
+ List<T> tmpResult = Collections.unmodifiableList(selected);
+ return callback.apply(tmpResult);
+ }
+ if (n == m) {
+ // No choice, select all n items, we don't update the `result` here
+ List<T> tmpResult = new ArrayList<>(selected);
+ tmpResult.addAll(all.subList(current, all.size()));
+ return callback.apply(tmpResult);
+ }
+
+ if (current >= all.size()) {
+ // Reach the end of items
+ return false;
+ }
+
+ // Select current item, continue to select C(m-1, n-1)
+ int index = selected.size();
+ selected.add(all.get(current));
+ ++current;
+ if (cnm(all, n - 1, m - 1, current, selected, callback)) {
+ // NOTE: we can pop the tailing items if want to keep result clear
+ return true;
+ }
+ // Not select current item, pop it and continue to select C(m-1, n)
+ selected.remove(index);
+ assert selected.size() == index : selected;
+ if (cnm(all, n - 1, m, current, selected, callback)) {
+ return true;
+ }
+
+ return false;
+ }
+
+ /**
+ * Traverse A(n, m) combinations of a list with n = m = all.size()
+ * @param all list to contain all items for combination
+ * @return List<List<T>> all combinations
+ */
+ public static <T> List<List<T>> anm(List<T> all) {
+ return anm(all, all.size(), all.size());
+ }
+
+ /**
+ * Traverse A(n, m) combinations of a list
+ * @param all list to contain all items for combination
+ * @param n m of A(n, m)
+ * @param m n of A(n, m)
+ * @return List<List<T>> all combinations
+ */
+ public static <T> List<List<T>> anm(List<T> all, int n, int m) {
+ List<List<T>> combs = new ArrayList<>();
+ anm(all, n, m, comb -> {
+ combs.add(comb);
+ return false;
+ });
+ return combs;
+ }
+
+ /**
+ * Traverse A(n, m) combinations of a list to find first matched
+ * result combination and call back with the result.
+ * @param all list to contain all items for combination
+ * @param n m of A(n, m)
+ * @param m n of A(n, m)
+ * @return true if matched any kind of items combination else false, the
+ * callback can always return false if want to traverse all combinations
+ */
+ public static <T> boolean anm(List<T> all, int n, int m,
+ Function<List<T>, Boolean> callback) {
+ return anm(all, n, m, null, callback);
+ }
+
+ /**
+ * Traverse A(n, m) combinations of a list to find first matched
+ * result combination and call back with the result.
+ * @param all list to contain all items for combination
+ * @param n m of A(n, m)
+ * @param m n of A(n, m)
+ * @param selected list to contains selected items
+ * @return true if matched any kind of items combination else false, the
+ * callback can always return false if want to traverse all combinations
+ */
+ private static <T> boolean anm(List<T> all, int n, int m,
+ List<Integer> selected,
+ Function<List<T>, Boolean> callback) {
+ assert n <= all.size();
+ assert m <= n;
+ if (selected == null) {
+ selected = new ArrayList<>(m);
+ }
+
+ if (m == 0) {
+ // All n items are selected
+ List<T> tmpResult = new ArrayList<>();
+ for (int i : selected) {
+ tmpResult.add(all.get(i));
+ }
+ return callback.apply(tmpResult);
+ }
+
+ for (int i = 0; i < all.size(); i++) {
+ if (selected.contains(i)) {
+ continue;
+ }
+ int index = selected.size();
+ selected.add(i);
+
+ // Select current item, continue to select A(m-1, n-1)
+ if (anm(all, n - 1, m - 1, selected, callback)) {
+ return true;
+ }
+
+ selected.remove(index);
+ assert selected.size() == index : selected;
+ }
+ return false;
+ }
}
diff --git a/hugegraph-common/src/test/java/com/baidu/hugegraph/unit/util/CollectionUtilTest.java b/hugegraph-common/src/test/java/com/baidu/hugegraph/unit/util/CollectionUtilTest.java
index a1e4750..72fc01e 100644
--- a/hugegraph-common/src/test/java/com/baidu/hugegraph/unit/util/CollectionUtilTest.java
+++ b/hugegraph-common/src/test/java/com/baidu/hugegraph/unit/util/CollectionUtilTest.java
@@ -417,4 +417,158 @@
Assert.assertEquals(ImmutableList.of("E", "D", "C", "B", "A"),
ImmutableList.copyOf(decrOrdered.values()));
}
+
+ @Test
+ public void testCrossCombineParts() {
+ List<List<Object>> parts;
+
+ parts = ImmutableList.of(ImmutableList.of("a", "b"),
+ ImmutableList.of(1, 2),
+ ImmutableList.of('x', 'y'));
+ List<List<Object>> combs = CollectionUtil.crossCombineParts(parts);
+ Assert.assertEquals(8, combs.size());
+ Assert.assertEquals(ImmutableList.of(
+ ImmutableList.of("a", "b", 1, 2, 'x', 'y'),
+ ImmutableList.of("a", "b", 1, 2, 'y', 'x'),
+ ImmutableList.of("a", "b", 2, 1, 'x', 'y'),
+ ImmutableList.of("a", "b", 2, 1, 'y', 'x'),
+ ImmutableList.of("b", "a", 1, 2, 'x', 'y'),
+ ImmutableList.of("b", "a", 1, 2, 'y', 'x'),
+ ImmutableList.of("b", "a", 2, 1, 'x', 'y'),
+ ImmutableList.of("b", "a", 2, 1, 'y', 'x')),
+ combs);
+
+ parts = ImmutableList.of(ImmutableList.of("a", "b", "c"),
+ ImmutableList.of(1, 2),
+ ImmutableList.of('x', 'y'));
+ Assert.assertEquals(24,
+ CollectionUtil.crossCombineParts(parts).size());
+
+ parts = ImmutableList.of(ImmutableList.of("a", "b", "c"),
+ ImmutableList.of(1, 2, 3),
+ ImmutableList.of('x', 'y'));
+ Assert.assertEquals(72,
+ CollectionUtil.crossCombineParts(parts).size());
+
+ parts = ImmutableList.of(ImmutableList.of("a", "b", "c"),
+ ImmutableList.of(1, 2, 3),
+ ImmutableList.of('x', 'y', 'z'));
+ Assert.assertEquals(216,
+ CollectionUtil.crossCombineParts(parts).size());
+ }
+
+ @Test
+ public void testCnm() {
+ List<Integer> list = ImmutableList.of(1, 2, 3, 4, 5);
+
+ // Test C(5, 2) with all combinations
+ List<List<Integer>> tuples = new ArrayList<>();
+ boolean found;
+ found = CollectionUtil.cnm(list, list.size(), 2, tuple -> {
+ tuples.add(new ArrayList<>(tuple));
+ return false;
+ });
+ Assert.assertFalse(found);
+ Assert.assertEquals(10, tuples.size());
+
+ Assert.assertEquals(10,
+ CollectionUtil.cnm(list, list.size(), 2).size());
+
+ // Test C(5, 2) with one combination
+ tuples.clear();
+ found = CollectionUtil.cnm(list, list.size(), 2, tuple -> {
+ if (tuple.equals(ImmutableList.of(2, 3))) {
+ tuples.add(new ArrayList<>(tuple));
+ return true;
+ }
+ return false;
+ });
+ Assert.assertTrue(found);
+ Assert.assertEquals(1, tuples.size());
+ Assert.assertEquals(ImmutableList.of(2, 3), tuples.get(0));
+
+ // Test C(5, 3) with all combinations
+ List<List<Integer>> triples = new ArrayList<>();
+ found = CollectionUtil.cnm(list, list.size(), 3, triple -> {
+ triples.add(new ArrayList<>(triple));
+ return false;
+ });
+ Assert.assertFalse(found);
+ Assert.assertEquals(10, triples.size());
+
+ Assert.assertEquals(10,
+ CollectionUtil.cnm(list, list.size(), 3).size());
+
+ // Test C(5, 3) with one combination
+ triples.clear();
+ found = CollectionUtil.cnm(list, list.size(), 3, triple -> {
+ if (triple.equals(ImmutableList.of(2, 3, 5))) {
+ triples.add(new ArrayList<>(triple));
+ return true;
+ }
+ return false;
+ });
+ Assert.assertTrue(found);
+ Assert.assertEquals(1, triples.size());
+ Assert.assertEquals(ImmutableList.of(2, 3, 5), triples.get(0));
+ }
+
+ @Test
+ public void testAnm() {
+ List<Integer> list = ImmutableList.of(1, 2, 3, 4, 5);
+
+ // Test A(5, 5) with all combinations
+ Assert.assertEquals(120, CollectionUtil.anm(list).size());
+
+ // Test A(5, 2) with all combinations
+ List<List<Integer>> tuples = new ArrayList<>();
+ boolean found;
+ found = CollectionUtil.anm(list, list.size(), 2, tuple -> {
+ tuples.add(new ArrayList<>(tuple));
+ return false;
+ });
+ Assert.assertFalse(found);
+ Assert.assertEquals(20, tuples.size());
+
+ Assert.assertEquals(20,
+ CollectionUtil.anm(list, list.size(), 2).size());
+
+ // Test A(5, 2) with one combination
+ tuples.clear();
+ found = CollectionUtil.anm(list, list.size(), 2, tuple -> {
+ if (tuple.equals(ImmutableList.of(2, 3))) {
+ tuples.add(new ArrayList<>(tuple));
+ return true;
+ }
+ return false;
+ });
+ Assert.assertTrue(found);
+ Assert.assertEquals(1, tuples.size());
+ Assert.assertEquals(ImmutableList.of(2, 3), tuples.get(0));
+
+ // Test A(5, 3) with all combinations
+ List<List<Integer>> triples = new ArrayList<>();
+ found = CollectionUtil.anm(list, list.size(), 3, triple -> {
+ triples.add(new ArrayList<>(triple));
+ return false;
+ });
+ Assert.assertFalse(found);
+ Assert.assertEquals(60, triples.size());
+
+ Assert.assertEquals(60,
+ CollectionUtil.anm(list, list.size(), 3).size());
+
+ // Test A(5, 3) with one combination
+ triples.clear();
+ found = CollectionUtil.anm(list, list.size(), 3, triple -> {
+ if (triple.equals(ImmutableList.of(2, 3, 5))) {
+ triples.add(new ArrayList<>(triple));
+ return true;
+ }
+ return false;
+ });
+ Assert.assertTrue(found);
+ Assert.assertEquals(1, triples.size());
+ Assert.assertEquals(ImmutableList.of(2, 3, 5), triples.get(0));
+ }
}
