Update: I have created an npm package for Combinatoricsjs.

I have been quite inactive in the blogging sphere due to finishing classes (I'm a graduate, whoo!), interviewing, and traveling. On that note, if anyone is actively hiring, I am looking for software engineering positions. My resume is posted here.

Why I Created Combinatorics.js

My last post on math.js described how I am actively working on a Combinatorics module for the math.js library. However,
to implement more advanced functions, I would need to create objects that really should not belong in math.js. This is because to modularize math.js, these objects and interfaces (discussed below) should be separated into components. Additionally, since Combinatorics is an obscure branch of mathematics, the underpinnings should reside on its own. After talking to the math.js collaborators, establishing a stand alone Combinatorics library is a better decision. So, I created my own library! Although I have separated from math.js, my goal is to have math.js add my library as a dependency so those who are using math.js can also apply my functions if needed.

Code Structure and Design

Since my goal is to create a Javascript Combinatorics library as a part of math.js, I wanted to use similar dependencies and structure as math.js. This includes using Grunt and Gulp for automating the build processes, q and underscore in development, and assert and mocha for testing. It is fairly straightforward and seems to be the common Javascript package structure.

In the previous post, I mentioned Permutations as objects. For the design, I created the Permutation as an interface for objects to implement. These objects will contain the functions in Permutation, but also have distinct responsibilities. Similarly, a graph will be an interface, which directed, undirected, etc. will implement. Also, I will need to have utility functions that I previously explained, such as Bell Numbers, Stirling numbers, and several others. However, this will not be introduced in the Permutation object, and will reside in a separate utility directory.

Combinatorics Objects/Functions to Implement In Short Future

Poset

Consider a the set of positive integers, $Z^+$, $\lbrace 1, 2, \ldots \rbrace$. One particularly significant relation between each element is how they are ordered - the next element is greater than the previous. If we take another set, $\lbrace 1, 3, 4, 2, 5, 7, 6 \rbrace$, we see that, although every element does not satisfy the relation, there are subsets of increasing integers. Some subsets are $\lbrace 1, 3, 4 \rbrace$, $\lbrace 1, 3, 4, 5, 7 \rbrace$ and several others.

Technically speaking, the set of subsets of increasing numbers is a partial order on the set of original numbers. This leads us to the topic of partially ordered sets, or Posets for short. Without getting too technical, a Poset is a set of ordered elements, but pairs of elements do not have to satisfy the relation.

(Anti) Chains

Taking the Poset $P = \lbrace 1, 2, 3, 4, 5, 6 \rbrace$, and the divisibility relation, $\lbrace 1, 2, 4 \rbrace$ has every element divisible by one another: 2 is divisible by 1, 4 is divisible by 2 and 1. Contrastingly, the set $\lbrace 1, 3, 5 \rbrace$ does not work. Combinatorially speaking, $\lbrace 1, 2, 4 \rbrace$ and $\lbrace 1, 3, 5 \rbrace$, are called chains and anti-chains, respectively. Although chains and anti-chains are interesting (to some), an important property is finding the smallest (minimum) and largest (maximum) chain and anti-chain. The cardinality of maximum anti-chain describes the width of the Poset and the maximum chain is the height. There are more states of the Poset object that will need to be implemented.

Algorithmically, we can find the maximum chain with a given relation similar to finding the longest increasing subsequence in $O(nlog(n))$ time.

Contains/Avoids

Another property of Posets is containing or avoiding subsequences. For example, take the Poset $P=\lbrace 1, 2, 3, 4, 5 \rbrace$, it is obvious that $P$ contains the subsequence $\lbrace 1, 2, 3 \rbrace$. Intuitively, we can see that a Poset contains a subsequence by scanning the Poset. However, this is not the only property of containing another sequence.

Let's take a more colorful example than the one above. Stack sorting is a method where a Poset is inputted into a stack, such that the goal is to output an ordered sequence. Intuitively, you can either push or pop elements to and from the stack, respectively, starting with the first element working towards the last one.

Take the Poset $$P = \lbrace 3, 1, 2 \rbrace$$. If we try to stack sort $P$, the set of operations is:

  • Push 3
  • Push 1
  • Pop 1
  • Push 2
  • Pop 2
  • Pop 3

Notice that the Poset $P = \lbrace 5, 1, 3, 2, 4 \rbrace$ also contains $\lbrace 3, 1, 2 \rbrace$. We relate the subsequence to the elements in the Poset. If $c \lt a \lt b$ are elements in $P$ picked left to right, but not necessarily consecutive, then $P$ contains $\lbrace 3, 1, 2 \rbrace$.

The set of operations to sort $P$ is as follows:

  • Push 5
  • Push 1
  • Pop 1
  • Push 3
  • Push 2
  • Pop 2
  • Pop 3
  • Push 4
  • Pop 4
  • Pop 5

To illustrate Permutation-avoiding, try sorting $P = \lbrace 2, 3, 1 \rbrace$. The set of operations is:

  • Push 2
  • Push 3
  • Push 1
  • Pop 1
  • Uh... I'm stuck.

So we see that $P$ cannot be sorted! Hence $P$ is $\lbrace 2, 3, 1 \rbrace$-avoiding.

Conclusion

One of my favorite aspects of Combinatorics.js is implementing these abstruse algorithms. However, since it is too abstruse and much fewer people study Combinatorics than more recognized branches of math, it's hard to find reliable collaborators or any collaborator for that regard. On that note, if any of this sounds interesting to you, feel free to contribute in any way that you can!