Antimatroid, The

thoughts on computer science, electronics, mathematics

One tree, many possibilities: Part 2

with one comment

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#. All five functions rely on the basic tree definition of T_{n}(S, \sigma) 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 n-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>> nCombination<T>(List<T> S, int n) {
    List<List<T>> R = kernel<T>(S, greaterThan, n);
    R.RemoveAll((x) => x.Count != k);
    return R;
}
Advertisements

Written by lewellen

2008-07-06 at 7:50 pm

One Response

Subscribe to comments with RSS.

  1. […] counting techniques. You can catch up on the idea in part one and the C# implementation in part two. In this post I’m going to cover how to take the knowledge from the first two posts and […]


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: