Antimatroid, The

Implementation

In my previous post, I wrote about how to construct a rule based tree that allows one to generate the outputs of a number of counting functions. In this installment, I am providing the corresponding implementation in C#. This source code in intended for pedagogical use only. Now, onto the show…

All five functions rely on the basic tree definition of which is treated as a kernel function in the implementation.

private List<List<T>> kernel<T>(List<T> S, Func<List<T>, int, List<T>> sigma, int N) {
    return kernel<T>(S, sigma, N, new List<T>());
}

private List<List<T>> kernel<T>(List<T> S, Func<List<T>, int, List<T>> sigma, int N, List<T> u) {
    List<List<T>> R = new List<List<T>>(new List<T>[] { u });
    if (N <= 0)
        return R;

    for (int n = 0; n < S.Count; n++) {
        List<T> v = new List<T>(u);
        v.Add(S[n]);
        R.AddRange(kernel<T>(sigma(S, n), sigma, N - 1, v));
    }

    return R;
}

Apart from the kernel, we still need a couple surjective functions to implement the remaining functions. As discussed in the previous post, we need two functions, one that returns all elements of a list except for a specified index, and one that returns all elements of a list greater than a specified index.

private List<T> notEqual<T>(List<T> S, int n) {
    return new List<T>(S.Where((x, m) => m != n));
}

private List<T> greaterThan<T>(List<T> S, int n) {
    return new List<T>(S.Where((x, m) => m > n));
}

The remaining implementations of the n-ary Cartesian Product, Permutation, k-Permutation, Power Set and k-Combination are now rather trivial.

public List<List<T>> nAryCartesianProduct<T>(List<T> S, int n) {
    List<List<T>> R = kernel<T>(S, (x, y) => x, n);
    R.RemoveAll((x) => x.Count < n);
    return R;
}

public List<List<T>> permutation<T>(List<T> S) {
    return kPermutation<T>(S, S.Count);
}

public List<List<T>> kPermutation<T>(List<T> S, int k) {
    List<List<T>> R = kernel<T>(S, notEqual, k);
    R.RemoveAll((x) => x.Count != k);
    return R;
}

public List<List<T>> powerset<T>(List<T> S) {
    return kernel<T>(S, greaterThan, S.Count);
}

public List<List<T>> kCombination<T>(List<T> S, int k) {
    List<List<T>> R = kernel<T>(S, greaterThan, k);
    R.RemoveAll((x) => x.Count != k);
    return R;
}

In the next post, I’ll wrap things up by going over time complexity, correctness and why this is all just a stepping stone to much more efficient approaches.

Introduction

Given the finite set and the surjective function , Let be a complete -ary tree of depth n such that , . For example, Let and , . Pictured bellow is with omitting for brevity.

It should be evident from the example that the set of nodes at depth is the -ary Cartesian product of .

Now, if we change to now be , where , the set of all leaf nodes at depth is the set of permutations of . Extending the example above, .

Without changing the definition of , it is possible to produce all possible -permutations from by selecting all nodes at depth .

At this point, if we make a small change to , every node in now represents the power set of . Again, using the example from above, .

Finally, without any further changes to the definition of , it is possible to produce all possible -combinations from , by selecting all nodes at depth .

is a very elegant way of representing and enumerating some of the most rudimentary combinatorial operations of introductory mathematics. In this series of post we’ll explore each operation and look at implementations, time complexities and possible applications.