Skip to content

Generate a series of tuples in lexicographical order

License

Notifications You must be signed in to change notification settings

chocolateboy/enumerator

Repository files navigation

enumerator

Build Status NPM Version

NAME

enumerator - generate a series of tuples in lexicographical order

FEATURES

  • no dependencies
  • ~500 B minified + gzipped
  • fully typed (TypeScript)
  • CDN builds (UMD): jsDelivr, unpkg

INSTALLATION

$ npm install @chocolatey/enumerator

SYNOPSIS

import { enumerate, enumerator } from '@chocolatey/enumerator'

const bits = [0, 1]
const words = ['foo', 'bar', 'baz', 'quux']

// generator
for (const value of enumerator([words, bits])) {
    console.log(value) // ["foo", 0], ["foo", 1], ["bar", 0] ... ["quux", 1]
}

// array
enumerate(bits, 2) // [[0, 0], [0, 1], [1, 0], [1, 1]]

DESCRIPTION

Enumerator generates a series of tuples in lexicographical order. Each tuple is an array of values drawn from a custom alphabet for each position. Values can be of any type.

The mechanism for generating the values is the same as an odometer, i.e. the rightmost dial/column is incremented for each result, moving left each time a dial rolls over, and halting when the leftmost dial rolls over, e.g.:

enumerate([[0, 1], [0, 1]]) // [[0, 0], [0, 1], [1, 0], [1, 1]]

In this example, the same alphabet is used for each position. As a shorthand, a single alphabet can be repeated n times by supplying n as the second argument, e.g.:

enumerate([0, 1], 2) // [[0, 0], [0, 1], [1, 0], [1, 1]]

Why?

Because we often face problems in which an exhaustive examination of all cases is necessary or desirable.

— Donald Knuth, The Art of Computer Programming, Section 7.2.1.1, Generating All n-Tuples.

EXPORTS

enumerate

  • Type:
    • <T>(alphabet: T[], length: number) => Array<T[]>
    • <T>(alphabets: T[][]) => Array<T[]>
  • Alias: generate
import { enumerate } from '@chocolatey/enumerator'

enumerate([0, 1], 2) // [[0, 0], [0, 1], [1, 0], [1, 1]]

Takes an array of alphabets, or a single alphabet and a length (number of times to repeat the alphabet), and returns an array of all the permutations of values from each alphabet in lexicographical order.

This is a wrapper around enumerator which gathers the generated values into an array, i.e. the following are equivalent:

const array1 = enumerate(...args)
const array2 = Array.from(enumerator(...args))

enumerator

  • Type:
    • <T>(alphabet: T[], length: number) => Generator<T[]>
    • <T>(alphabets: T[][]) => Generator<T[]>
  • Alias: generator
import { enumerator } from '@chocolatey/enumerator'

for (const value of enumerator([0, 1], 2)) {
    console.log(value) // [0, 0], [0, 1], [1, 0], [1, 1]
}

Takes an array of alphabets, or a single alphabet and a length (number of times to repeat the alphabet), and yields all the permutations of values from each alphabet in lexicographical order.

unfold

  • Type: <V>(obj: Record<string, V | V[]>) => [string, V][][]
import { unfold } from '@chocolatey/enumerator'

const options = {
    color: ['black', 'pink'],
    size: ['small', 'large'],
    discount: false,
}

const alphabets = unfold(options)
[
    [["color", "black"], ["color", "pink"]], // 0
    [["size", "small"], ["size", "large"]],  // 1
    [["discount", false]]                    // 2
]

Takes a plain object and flattens it into an array of arrays of key/value pairs suitable for use as alphabets. The object is unchanged. The object's values are coerced to arrays, so if a single value is already an array, it will need to be wrapped in another array, e.g.:

// before x
const data = {
    loc: [x, y],
}

// after ✔
const data = {
    loc: [[x, y]],
}

EXAMPLES

Generating passwords

Suppose you've protected a Word document or zipfile with the password "rosebud", but can't remember if any letters were uppercase, if it was one word or two, or if there were any substitutions. A list of candidate passwords can be generated by:

const alphabets = [
    ['r', 'R'],
    ['o', 'O', '0'],
    ['s', 'S', '5'],
    ['e', 'E', '3'],
    ['', ' '],
    ['b', 'B'],
    ['u', 'U'],
    ['d', 'D'],
]

const passwords = enumerate(alphabets).map(it => it.join(''))

This generates 864 different candidates, including "rosebud", "r053buD", "Rose Bud", and "ROSEBUD".

Combining options

Although any types can be used as values, a specific task may require some data munging to encode its choices as alphabets. To this end, a helper function, unfold, is available which translates a plain object into an array of alphabets of key/value pairs representing an option or feature.

For example, if a product is available with the following options:

  • color: red, black, pink
  • size: small, medium, large

- the permutations can be generated with:

import { enumerate, unfold } from '@chocolatey/enumerator'

const options = {
    color: ['red', 'black', 'pink'],
    size: ['small', 'medium', 'large'],
}

const alphabets = unfold(options)
const products = enumerate(alphabets).map(Object.fromEntries)

- which yields the following result:

[
    { color: 'red', size: 'small' },
    { color: 'red', size: 'medium' },
    { color: 'red', size: 'large' },
    { color: 'black', size: 'small' },
    { color: 'black', size: 'medium' },
    { color: 'black', size: 'large' },
    { color: 'pink', size: 'small' },
    { color: 'pink', size: 'medium' },
    { color: 'pink', size: 'large' }
]

DEVELOPMENT

NPM Scripts

The following NPM scripts are available:

  • build - compile the library for testing and save to the target directory
  • build:doc - generate the README's TOC (table of contents)
  • build:release - compile the library for release and save to the target directory
  • clean - remove the target directory and its contents
  • rebuild - clean the target directory and recompile the library
  • repl - launch a node REPL with the library loaded
  • test - recompile the library and run the test suite
  • test:run - run the test suite
  • typecheck - sanity check the library's type definitions

COMPATIBILITY

SEE ALSO

JavaScript

Perl

VERSION

1.1.1

AUTHOR

chocolateboy

COPYRIGHT AND LICENSE

Copyright © 2020-2021 by chocolateboy.

This is free software; you can redistribute it and/or modify it under the terms of the MIT license.