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