@prelude/array - npm Package Compare versions

Comparing version 0.1.2 to 0.2.0

permutations.js

+import swap from './swap.js';
+import zeroes from './zeroes.js';
+/**
+ * Based on [Permutation Generation Methods, Robert Sedgewick](http://homepage.math.uiowa.edu/~goodman/22m150.dir/2007/Permutation%20Generation%20Methods.pdf).
+ * @returns permutations of an array.
+ */
+const permutations = function* (values) {
+    const n = values.length;
+    const c = zeroes(n);
+    let i = 1;
+    let k = 0;
+    yield values.slice();
+    while (i < n) {
+        if (c[i] < i) {
+            k = i % 2 && c[i];
+            swap(values, i, k);
+            ++c[i];
+            i = 1;
+            yield values.slice();
+        }
+        else {
+            c[i++] = 0;
+        }
+    }
+};
+export default permutations;
+//# sourceMappingURL=data:application/json;base64,eyJ2ZXJzaW9uIjozLCJmaWxlIjoicGVybXV0YXRpb25zLmpzIiwic291cmNlUm9vdCI6IiIsInNvdXJjZXMiOlsicGVybXV0YXRpb25zLnRzIl0sIm5hbWVzIjpbXSwibWFwcGluZ3MiOiJBQUFBLE9BQU8sSUFBSSxNQUFNLFdBQVcsQ0FBQTtBQUM1QixPQUFPLE1BQU0sTUFBTSxhQUFhLENBQUE7QUFFaEM7OztHQUdHO0FBQ0gsTUFBTSxZQUFZLEdBQ2hCLFFBQVEsQ0FBQyxFQUFLLE1BQVc7SUFDdkIsTUFBTSxDQUFDLEdBQUcsTUFBTSxDQUFDLE1BQU0sQ0FBQTtJQUN2QixNQUFNLENBQUMsR0FBRyxNQUFNLENBQUMsQ0FBQyxDQUFDLENBQUE7SUFDbkIsSUFBSSxDQUFDLEdBQUcsQ0FBQyxDQUFBO0lBQ1QsSUFBSSxDQUFDLEdBQUcsQ0FBQyxDQUFBO0lBQ1QsTUFBTSxNQUFNLENBQUMsS0FBSyxFQUFFLENBQUE7SUFDcEIsT0FBTyxDQUFDLEdBQUcsQ0FBQyxFQUFFO1FBQ1osSUFBSSxDQUFDLENBQUMsQ0FBQyxDQUFDLEdBQUcsQ0FBQyxFQUFFO1lBQ1osQ0FBQyxHQUFHLENBQUMsR0FBRyxDQUFDLElBQUksQ0FBQyxDQUFDLENBQUMsQ0FBQyxDQUFBO1lBQ2pCLElBQUksQ0FBQyxNQUFNLEVBQUUsQ0FBQyxFQUFFLENBQUMsQ0FBQyxDQUFBO1lBQ2xCLEVBQUUsQ0FBQyxDQUFDLENBQUMsQ0FBQyxDQUFBO1lBQ04sQ0FBQyxHQUFHLENBQUMsQ0FBQTtZQUNMLE1BQU0sTUFBTSxDQUFDLEtBQUssRUFBRSxDQUFBO1NBQ3JCO2FBQU07WUFDTCxDQUFDLENBQUMsQ0FBQyxFQUFFLENBQUMsR0FBRyxDQUFDLENBQUE7U0FDWDtLQUNGO0FBQ0gsQ0FBQyxDQUFBO0FBRUgsZUFBZSxZQUFZLENBQUEiLCJzb3VyY2VzQ29udGVudCI6WyJpbXBvcnQgc3dhcCBmcm9tICcuL3N3YXAuanMnXG5pbXBvcnQgemVyb2VzIGZyb20gJy4vemVyb2VzLmpzJ1xuXG4vKipcbiAqIEJhc2VkIG9uIFtQZXJtdXRhdGlvbiBHZW5lcmF0aW9uIE1ldGhvZHMsIFJvYmVydCBTZWRnZXdpY2tdKGh0dHA6Ly9ob21lcGFnZS5tYXRoLnVpb3dhLmVkdS9+Z29vZG1hbi8yMm0xNTAuZGlyLzIwMDcvUGVybXV0YXRpb24lMjBHZW5lcmF0aW9uJTIwTWV0aG9kcy5wZGYpLlxuICogQHJldHVybnMgcGVybXV0YXRpb25zIG9mIGFuIGFycmF5LlxuICovXG5jb25zdCBwZXJtdXRhdGlvbnMgPVxuICBmdW5jdGlvbiogPFQ+KHZhbHVlczogVFtdKTogR2VuZXJhdG9yPFRbXT4ge1xuICAgIGNvbnN0IG4gPSB2YWx1ZXMubGVuZ3RoXG4gICAgY29uc3QgYyA9IHplcm9lcyhuKVxuICAgIGxldCBpID0gMVxuICAgIGxldCBrID0gMFxuICAgIHlpZWxkIHZhbHVlcy5zbGljZSgpXG4gICAgd2hpbGUgKGkgPCBuKSB7XG4gICAgICBpZiAoY1tpXSA8IGkpIHtcbiAgICAgICAgayA9IGkgJSAyICYmIGNbaV1cbiAgICAgICAgc3dhcCh2YWx1ZXMsIGksIGspXG4gICAgICAgICsrY1tpXVxuICAgICAgICBpID0gMVxuICAgICAgICB5aWVsZCB2YWx1ZXMuc2xpY2UoKVxuICAgICAgfSBlbHNlIHtcbiAgICAgICAgY1tpKytdID0gMFxuICAgICAgfVxuICAgIH1cbiAgfVxuXG5leHBvcnQgZGVmYXVsdCBwZXJtdXRhdGlvbnNcbiJdfQ==

permutations.ts

+import swap from './swap.js'
+import zeroes from './zeroes.js'
+
+/**
+ * Based on [Permutation Generation Methods, Robert Sedgewick](http://homepage.math.uiowa.edu/~goodman/22m150.dir/2007/Permutation%20Generation%20Methods.pdf).
+ * @returns permutations of an array.
+ */
+const permutations =
+  function* <T>(values: T[]): Generator<T[]> {
+    const n = values.length
+    const c = zeroes(n)
+    let i = 1
+    let k = 0
+    yield values.slice()
+    while (i < n) {
+      if (c[i] < i) {
+        k = i % 2 && c[i]
+        swap(values, i, k)
+        ++c[i]
+        i = 1
+        yield values.slice()
+      } else {
+        c[i++] = 0
+      }
+    }
+  }
+
+export default permutations

index.js

@@ -17,2 +17,3 @@ import * as Cmp from '@prelude/cmp';
 import of from './of.js';
+import permutations from './permutations.js';
 import randomIndex from './random-index.js';
@@ -27,3 +28,3 @@ import shuffle from './shuffle.js';
 import zeroes from './zeroes.js';
-export { at, bounded, bsearch, clone, Cmp, deleteSwapRandom, first, groups, indices, last, maybeAt, maybeFirst, maybeLast, modulo, nulls, of, randomIndex, shuffle, shuffled, sort, sorted, swap, swapDelete, unique, zeroes };
-//# sourceMappingURL=data:application/json;base64,eyJ2ZXJzaW9uIjozLCJmaWxlIjoiaW5kZXguanMiLCJzb3VyY2VSb290IjoiIiwic291cmNlcyI6WyJpbmRleC50cyJdLCJuYW1lcyI6W10sIm1hcHBpbmdzIjoiQUFBQSxPQUFPLEtBQUssR0FBRyxNQUFNLGNBQWMsQ0FBQTtBQUNuQyxPQUFPLEVBQUUsTUFBTSxTQUFTLENBQUE7QUFDeEIsT0FBTyxPQUFPLE1BQU0sY0FBYyxDQUFBO0FBQ2xDLE9BQU8sT0FBTyxNQUFNLGNBQWMsQ0FBQTtBQUNsQyxPQUFPLEtBQUssTUFBTSxZQUFZLENBQUE7QUFDOUIsT0FBTyxnQkFBZ0IsTUFBTSx5QkFBeUIsQ0FBQTtBQUN0RCxPQUFPLEtBQUssTUFBTSxZQUFZLENBQUE7QUFDOUIsT0FBTyxNQUFNLE1BQU0sYUFBYSxDQUFBO0FBQ2hDLE9BQU8sT0FBTyxNQUFNLGNBQWMsQ0FBQTtBQUNsQyxPQUFPLElBQUksTUFBTSxXQUFXLENBQUE7QUFDNUIsT0FBTyxPQUFPLE1BQU0sZUFBZSxDQUFBO0FBQ25DLE9BQU8sVUFBVSxNQUFNLGtCQUFrQixDQUFBO0FBQ3pDLE9BQU8sU0FBUyxNQUFNLGlCQUFpQixDQUFBO0FBQ3ZDLE9BQU8sTUFBTSxNQUFNLGFBQWEsQ0FBQTtBQUNoQyxPQUFPLEtBQUssTUFBTSxZQUFZLENBQUE7QUFDOUIsT0FBTyxFQUFFLE1BQU0sU0FBUyxDQUFBO0FBQ3hCLE9BQU8sV0FBVyxNQUFNLG1CQUFtQixDQUFBO0FBQzNDLE9BQU8sT0FBTyxNQUFNLGNBQWMsQ0FBQTtBQUNsQyxPQUFPLFFBQVEsTUFBTSxlQUFlLENBQUE7QUFDcEMsT0FBTyxJQUFJLE1BQU0sV0FBVyxDQUFBO0FBQzVCLE9BQU8sTUFBTSxNQUFNLGFBQWEsQ0FBQTtBQUNoQyxPQUFPLElBQUksTUFBTSxXQUFXLENBQUE7QUFDNUIsT0FBTyxVQUFVLE1BQU0sa0JBQWtCLENBQUE7QUFDekMsT0FBTyxNQUFNLE1BQU0sYUFBYSxDQUFBO0FBQ2hDLE9BQU8sTUFBTSxNQUFNLGFBQWEsQ0FBQTtBQUVoQyxPQUFPLEVBQ0wsRUFBRSxFQUNGLE9BQU8sRUFDUCxPQUFPLEVBQ1AsS0FBSyxFQUNMLEdBQUcsRUFDSCxnQkFBZ0IsRUFDaEIsS0FBSyxFQUNMLE1BQU0sRUFDTixPQUFPLEVBQ1AsSUFBSSxFQUNKLE9BQU8sRUFDUCxVQUFVLEVBQ1YsU0FBUyxFQUNULE1BQU0sRUFDTixLQUFLLEVBQ0wsRUFBRSxFQUNGLFdBQVcsRUFDWCxPQUFPLEVBQ1AsUUFBUSxFQUNSLElBQUksRUFDSixNQUFNLEVBQ04sSUFBSSxFQUNKLFVBQVUsRUFDVixNQUFNLEVBQ04sTUFBTSxFQUNQLENBQUEiLCJzb3VyY2VzQ29udGVudCI6WyJpbXBvcnQgKiBhcyBDbXAgZnJvbSAnQHByZWx1ZGUvY21wJ1xuaW1wb3J0IGF0IGZyb20gJy4vYXQuanMnXG5pbXBvcnQgYm91bmRlZCBmcm9tICcuL2JvdW5kZWQuanMnXG5pbXBvcnQgYnNlYXJjaCBmcm9tICcuL2JzZWFyY2guanMnXG5pbXBvcnQgY2xvbmUgZnJvbSAnLi9jbG9uZS5qcydcbmltcG9ydCBkZWxldGVTd2FwUmFuZG9tIGZyb20gJy4vZGVsZXRlLXN3YXAtcmFuZG9tLmpzJ1xuaW1wb3J0IGZpcnN0IGZyb20gJy4vZmlyc3QuanMnXG5pbXBvcnQgZ3JvdXBzIGZyb20gJy4vZ3JvdXBzLmpzJ1xuaW1wb3J0IGluZGljZXMgZnJvbSAnLi9pbmRpY2VzLmpzJ1xuaW1wb3J0IGxhc3QgZnJvbSAnLi9sYXN0LmpzJ1xuaW1wb3J0IG1heWJlQXQgZnJvbSAnLi9tYXliZS1hdC5qcydcbmltcG9ydCBtYXliZUZpcnN0IGZyb20gJy4vbWF5YmUtZmlyc3QuanMnXG5pbXBvcnQgbWF5YmVMYXN0IGZyb20gJy4vbWF5YmUtbGFzdC5qcydcbmltcG9ydCBtb2R1bG8gZnJvbSAnLi9tb2R1bG8uanMnXG5pbXBvcnQgbnVsbHMgZnJvbSAnLi9udWxscy5qcydcbmltcG9ydCBvZiBmcm9tICcuL29mLmpzJ1xuaW1wb3J0IHJhbmRvbUluZGV4IGZyb20gJy4vcmFuZG9tLWluZGV4LmpzJ1xuaW1wb3J0IHNodWZmbGUgZnJvbSAnLi9zaHVmZmxlLmpzJ1xuaW1wb3J0IHNodWZmbGVkIGZyb20gJy4vc2h1ZmZsZWQuanMnXG5pbXBvcnQgc29ydCBmcm9tICcuL3NvcnQuanMnXG5pbXBvcnQgc29ydGVkIGZyb20gJy4vc29ydGVkLmpzJ1xuaW1wb3J0IHN3YXAgZnJvbSAnLi9zd2FwLmpzJ1xuaW1wb3J0IHN3YXBEZWxldGUgZnJvbSAnLi9zd2FwLWRlbGV0ZS5qcydcbmltcG9ydCB1bmlxdWUgZnJvbSAnLi91bmlxdWUuanMnXG5pbXBvcnQgemVyb2VzIGZyb20gJy4vemVyb2VzLmpzJ1xuXG5leHBvcnQge1xuICBhdCxcbiAgYm91bmRlZCxcbiAgYnNlYXJjaCxcbiAgY2xvbmUsXG4gIENtcCxcbiAgZGVsZXRlU3dhcFJhbmRvbSxcbiAgZmlyc3QsXG4gIGdyb3VwcyxcbiAgaW5kaWNlcyxcbiAgbGFzdCxcbiAgbWF5YmVBdCxcbiAgbWF5YmVGaXJzdCxcbiAgbWF5YmVMYXN0LFxuICBtb2R1bG8sXG4gIG51bGxzLFxuICBvZixcbiAgcmFuZG9tSW5kZXgsXG4gIHNodWZmbGUsXG4gIHNodWZmbGVkLFxuICBzb3J0LFxuICBzb3J0ZWQsXG4gIHN3YXAsXG4gIHN3YXBEZWxldGUsXG4gIHVuaXF1ZSxcbiAgemVyb2VzXG59XG4iXX0=
+export { at, bounded, bsearch, clone, Cmp, deleteSwapRandom, first, groups, indices, last, maybeAt, maybeFirst, maybeLast, modulo, nulls, of, permutations, randomIndex, shuffle, shuffled, sort, sorted, swap, swapDelete, unique, zeroes };
+//# sourceMappingURL=data:application/json;base64,eyJ2ZXJzaW9uIjozLCJmaWxlIjoiaW5kZXguanMiLCJzb3VyY2VSb290IjoiIiwic291cmNlcyI6WyJpbmRleC50cyJdLCJuYW1lcyI6W10sIm1hcHBpbmdzIjoiQUFBQSxPQUFPLEtBQUssR0FBRyxNQUFNLGNBQWMsQ0FBQTtBQUNuQyxPQUFPLEVBQUUsTUFBTSxTQUFTLENBQUE7QUFDeEIsT0FBTyxPQUFPLE1BQU0sY0FBYyxDQUFBO0FBQ2xDLE9BQU8sT0FBTyxNQUFNLGNBQWMsQ0FBQTtBQUNsQyxPQUFPLEtBQUssTUFBTSxZQUFZLENBQUE7QUFDOUIsT0FBTyxnQkFBZ0IsTUFBTSx5QkFBeUIsQ0FBQTtBQUN0RCxPQUFPLEtBQUssTUFBTSxZQUFZLENBQUE7QUFDOUIsT0FBTyxNQUFNLE1BQU0sYUFBYSxDQUFBO0FBQ2hDLE9BQU8sT0FBTyxNQUFNLGNBQWMsQ0FBQTtBQUNsQyxPQUFPLElBQUksTUFBTSxXQUFXLENBQUE7QUFDNUIsT0FBTyxPQUFPLE1BQU0sZUFBZSxDQUFBO0FBQ25DLE9BQU8sVUFBVSxNQUFNLGtCQUFrQixDQUFBO0FBQ3pDLE9BQU8sU0FBUyxNQUFNLGlCQUFpQixDQUFBO0FBQ3ZDLE9BQU8sTUFBTSxNQUFNLGFBQWEsQ0FBQTtBQUNoQyxPQUFPLEtBQUssTUFBTSxZQUFZLENBQUE7QUFDOUIsT0FBTyxFQUFFLE1BQU0sU0FBUyxDQUFBO0FBQ3hCLE9BQU8sWUFBWSxNQUFNLG1CQUFtQixDQUFBO0FBQzVDLE9BQU8sV0FBVyxNQUFNLG1CQUFtQixDQUFBO0FBQzNDLE9BQU8sT0FBTyxNQUFNLGNBQWMsQ0FBQTtBQUNsQyxPQUFPLFFBQVEsTUFBTSxlQUFlLENBQUE7QUFDcEMsT0FBTyxJQUFJLE1BQU0sV0FBVyxDQUFBO0FBQzVCLE9BQU8sTUFBTSxNQUFNLGFBQWEsQ0FBQTtBQUNoQyxPQUFPLElBQUksTUFBTSxXQUFXLENBQUE7QUFDNUIsT0FBTyxVQUFVLE1BQU0sa0JBQWtCLENBQUE7QUFDekMsT0FBTyxNQUFNLE1BQU0sYUFBYSxDQUFBO0FBQ2hDLE9BQU8sTUFBTSxNQUFNLGFBQWEsQ0FBQTtBQUVoQyxPQUFPLEVBQ0wsRUFBRSxFQUNGLE9BQU8sRUFDUCxPQUFPLEVBQ1AsS0FBSyxFQUNMLEdBQUcsRUFDSCxnQkFBZ0IsRUFDaEIsS0FBSyxFQUNMLE1BQU0sRUFDTixPQUFPLEVBQ1AsSUFBSSxFQUNKLE9BQU8sRUFDUCxVQUFVLEVBQ1YsU0FBUyxFQUNULE1BQU0sRUFDTixLQUFLLEVBQ0wsRUFBRSxFQUNGLFlBQVksRUFDWixXQUFXLEVBQ1gsT0FBTyxFQUNQLFFBQVEsRUFDUixJQUFJLEVBQ0osTUFBTSxFQUNOLElBQUksRUFDSixVQUFVLEVBQ1YsTUFBTSxFQUNOLE1BQU0sRUFDUCxDQUFBIiwic291cmNlc0NvbnRlbnQiOlsiaW1wb3J0ICogYXMgQ21wIGZyb20gJ0BwcmVsdWRlL2NtcCdcbmltcG9ydCBhdCBmcm9tICcuL2F0LmpzJ1xuaW1wb3J0IGJvdW5kZWQgZnJvbSAnLi9ib3VuZGVkLmpzJ1xuaW1wb3J0IGJzZWFyY2ggZnJvbSAnLi9ic2VhcmNoLmpzJ1xuaW1wb3J0IGNsb25lIGZyb20gJy4vY2xvbmUuanMnXG5pbXBvcnQgZGVsZXRlU3dhcFJhbmRvbSBmcm9tICcuL2RlbGV0ZS1zd2FwLXJhbmRvbS5qcydcbmltcG9ydCBmaXJzdCBmcm9tICcuL2ZpcnN0LmpzJ1xuaW1wb3J0IGdyb3VwcyBmcm9tICcuL2dyb3Vwcy5qcydcbmltcG9ydCBpbmRpY2VzIGZyb20gJy4vaW5kaWNlcy5qcydcbmltcG9ydCBsYXN0IGZyb20gJy4vbGFzdC5qcydcbmltcG9ydCBtYXliZUF0IGZyb20gJy4vbWF5YmUtYXQuanMnXG5pbXBvcnQgbWF5YmVGaXJzdCBmcm9tICcuL21heWJlLWZpcnN0LmpzJ1xuaW1wb3J0IG1heWJlTGFzdCBmcm9tICcuL21heWJlLWxhc3QuanMnXG5pbXBvcnQgbW9kdWxvIGZyb20gJy4vbW9kdWxvLmpzJ1xuaW1wb3J0IG51bGxzIGZyb20gJy4vbnVsbHMuanMnXG5pbXBvcnQgb2YgZnJvbSAnLi9vZi5qcydcbmltcG9ydCBwZXJtdXRhdGlvbnMgZnJvbSAnLi9wZXJtdXRhdGlvbnMuanMnXG5pbXBvcnQgcmFuZG9tSW5kZXggZnJvbSAnLi9yYW5kb20taW5kZXguanMnXG5pbXBvcnQgc2h1ZmZsZSBmcm9tICcuL3NodWZmbGUuanMnXG5pbXBvcnQgc2h1ZmZsZWQgZnJvbSAnLi9zaHVmZmxlZC5qcydcbmltcG9ydCBzb3J0IGZyb20gJy4vc29ydC5qcydcbmltcG9ydCBzb3J0ZWQgZnJvbSAnLi9zb3J0ZWQuanMnXG5pbXBvcnQgc3dhcCBmcm9tICcuL3N3YXAuanMnXG5pbXBvcnQgc3dhcERlbGV0ZSBmcm9tICcuL3N3YXAtZGVsZXRlLmpzJ1xuaW1wb3J0IHVuaXF1ZSBmcm9tICcuL3VuaXF1ZS5qcydcbmltcG9ydCB6ZXJvZXMgZnJvbSAnLi96ZXJvZXMuanMnXG5cbmV4cG9ydCB7XG4gIGF0LFxuICBib3VuZGVkLFxuICBic2VhcmNoLFxuICBjbG9uZSxcbiAgQ21wLFxuICBkZWxldGVTd2FwUmFuZG9tLFxuICBmaXJzdCxcbiAgZ3JvdXBzLFxuICBpbmRpY2VzLFxuICBsYXN0LFxuICBtYXliZUF0LFxuICBtYXliZUZpcnN0LFxuICBtYXliZUxhc3QsXG4gIG1vZHVsbyxcbiAgbnVsbHMsXG4gIG9mLFxuICBwZXJtdXRhdGlvbnMsXG4gIHJhbmRvbUluZGV4LFxuICBzaHVmZmxlLFxuICBzaHVmZmxlZCxcbiAgc29ydCxcbiAgc29ydGVkLFxuICBzd2FwLFxuICBzd2FwRGVsZXRlLFxuICB1bmlxdWUsXG4gIHplcm9lc1xufVxuIl19

index.ts

@@ -17,2 +17,3 @@ import * as Cmp from '@prelude/cmp'
 import of from './of.js'
+import permutations from './permutations.js'
 import randomIndex from './random-index.js'
@@ -45,2 +46,3 @@ import shuffle from './shuffle.js'
   of,
+  permutations,
   randomIndex,
@@ -47,0 +49,0 @@ shuffle,

package.json

 {
   "name": "@prelude/array",
-  "version": "0.1.2",
+  "version": "0.2.0",
   "description": "Array module.",
@@ -5,0 +5,0 @@ "type": "module",

No alert changes

Improved metrics

Total package byte prevSize

48029

8.37%

Number of package files

58

3.57%

Lines of code

570

10.68%

No dependency changes