refactor(transducers): update permutations()/permutationsN(), add tests

thi-ng · Mar 2, 2018 · 488462e · 488462e
1 parent 91938ed
commit 488462e
Show file tree

Hide file tree

Showing 2 changed files with 98 additions and 6 deletions.
diff --git a/packages/transducers/src/iter/permutations.ts b/packages/transducers/src/iter/permutations.ts
@@ -1,17 +1,22 @@
 import { range } from "./range";
-import { repeatedly } from "./repeatedly";
+import { isArray } from "@thi.ng/checks/is-array";
+import { isString } from "@thi.ng/checks/is-string";
 
 /**
  * Iterator yielding the Cartesian Product of the given iterables.
- * All iterables MUST be finite!
+ * All iterables MUST be finite! If any of the given iterables is
+ * empty the iterator yields no values.
  *
  * ```
  * [...permutations(range(3), "ab")]
  * // [ ['a', 0], ['a', 1], ['a', 2],
  * //   ['b', 0], ['b', 1], ['b', 2] ]
  *
- * [...iterator(map((x) => x.join("")), permutations("ab", "-", tx.range(3)))]
+ * [...iterator(map((x: any[]) => x.join("")), permutations("ab", "-", tx.range(3)))]
  * // ['a-0', 'a-1', 'a-2', 'b-0', 'b-1', 'b-2']
+ *
+ * [...permutations([], "", range(0))]
+ * // []
  * ```
  *
  * @param src
@@ -22,8 +27,11 @@ export function permutations<A, B, C>(a: Iterable<A>, b: Iterable<B>, c: Iterabl
 export function permutations<A, B, C, D>(a: Iterable<A>, b: Iterable<B>, c: Iterable<C>, d: Iterable<D>): IterableIterator<[A, B, C, D]>;
 export function* permutations(...src: Iterable<any>[]): IterableIterator<any[]> {
     const n = src.length - 1;
+    if (n < 0) {
+        return;
+    }
     const step = new Array(n + 1).fill(0);
-    const realized = src.map((s) => [...s]);
+    const realized = src.map((s: any) => isArray(s) || isString(s) ? s : [...s]);
     const total = realized.reduce((acc, x) => acc * x.length, 1);
     for (let i = 0; i < total; i++) {
         const tuple = [];
@@ -58,6 +66,14 @@ export function* permutations(...src: Iterable<any>[]): IterableIterator<any[]>
  * @param n
  * @param m
  */
-export function permutationsN(n: number, m = n): IterableIterator<number[]> {
-    return permutations.apply(null, [...repeatedly(() => range(m), n)]);
+export function permutationsN(n: number, m = n, offsets?: number[]): IterableIterator<number[]> {
+    if (offsets && offsets.length < n) {
+        throw new Error("not sufficient offsets given");
+    }
+    const seqs = [];
+    while (--n >= 0) {
+        const o = offsets ? offsets[n] : 0;
+        seqs[n] = range(o, o + m);
+    }
+    return permutations.apply(null, seqs);
 }
diff --git a/packages/transducers/test/permutations.ts b/packages/transducers/test/permutations.ts
@@ -0,0 +1,76 @@
+import { swizzler } from "../src/func/swizzler";
+import { permutations, permutationsN } from "../src/iter/permutations";
+import { range } from "../src/iter/range";
+import { iterator } from "../src/iterator";
+import { map } from "../src/xform/map";
+
+import * as assert from "assert";
+
+describe("permutations", () => {
+    it("empty", () => {
+        assert.deepEqual([...permutations([])], []);
+        assert.deepEqual([...permutations("")], []);
+        assert.deepEqual([...permutations(range(0))], []);
+        assert.deepEqual([...permutations([], [])], []);
+        assert.deepEqual([...permutations([], "")], []);
+        assert.deepEqual([...permutations(range(0), "")], []);
+        assert.deepEqual([...permutations([], "a")], []);
+        assert.deepEqual([...permutations("", "a")], []);
+        assert.deepEqual([...permutations("", "ab")], []);
+        assert.deepEqual([...permutations.apply(null, [])], []);
+    });
+    it("single", () => {
+        assert.deepEqual(
+            [...permutations("a", "-", range(1))],
+            [["a", "-", 0]]
+        );
+        assert.deepEqual(
+            [...permutations("a", "-", range(2))],
+            [["a", "-", 0], ["a", "-", 1]]
+        );
+        assert.deepEqual(
+            [...permutations("a", "-+", range(2))],
+            [["a", "-", 0], ["a", "-", 1], ["a", "+", 0], ["a", "+", 1]]
+        );
+    });
+    it("transformed", () => {
+        assert.deepEqual(
+            [...iterator(map((x: any[]) => x.join("")), permutations("ab", "-", range(2)))],
+            ['a-0', 'a-1', 'b-0', 'b-1']
+        );
+    });
+    it("swizzle", () => {
+        assert.deepEqual(
+            [...iterator(map((x: string[]) => swizzler(x)({ x: 0, y: 1, z: 2 })), permutations("xyz", "xyz", "xyz"))],
+            [...permutationsN(3)]
+        );
+    });
+});
+
+describe("permutationsN", () => {
+    it("empty", () => {
+        assert.deepEqual([...permutationsN(0)], []);
+    });
+    it("one", () => {
+        assert.deepEqual([...permutationsN(1)], [[0]]);
+    });
+    it("two", () => {
+        assert.deepEqual([...permutationsN(2)], [[0, 0], [0, 1], [1, 0], [1, 1]]);
+    });
+    it("two/three", () => {
+        assert.deepEqual(
+            [...permutationsN(2, 3)],
+            [
+                [0, 0], [0, 1], [0, 2],
+                [1, 0], [1, 1], [1, 2],
+                [2, 0], [2, 1], [2, 2]
+            ]
+        );
+    });
+    it("with offsets", () => {
+        assert.deepEqual([...permutationsN(2, 2, [100, 1000])], [[100, 1000], [100, 1001], [101, 1000], [101, 1001]]);
+    });
+    it("insufficient offsets", () => {
+        assert.throws(() => permutationsN(2, 2, [0]));
+    });
+});