## One tree, many possibilities: Part 2

### 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 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; }

[…] 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 […]

One tree many possibilities: Part 3 « Antimatroid, The2011-02-01 at 8:16 am