Posts Tagged ‘Power Set’
One tree many possibilities: Part 3
Introduction
When I first began publishing content on this blog, I wrote a couple of posts entitled One tree many possibilities that covered how to enumerate the sets produced by different 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 derive closed form solutions to each of the counting techniques through analysis of their respective recurrence relations.
Preliminaries
The basic idea is that that the set 
Since we can have a variety of conceivable sets, we need to map sets of a given cardinality to a common set of the same cardinality. Let 
k-ary Cartesian Product
The k-ary cartesian product is the way of selecting
The process uses 
To count the number of elements, we need to count the number of nodes at depth
If we think of the tree having a height of 
Rearranging the second statement leads to 
k-Permutations
The permutation and k-permutation is a way of selecting 
The process uses 
To count the number of elements, we need to count the number of nodes at depth 
Using the same labeling scheme as in the k-ary cartesian product, we can interpret the first statement as any node at depth zero will be considered a leaf node and counted once. The second statement says that for each element in 
Rearranging the second statement leads to 
Power Set
The power set is the way of selecting zero items to the cardinality of the set items from a set where the order of the selection is not important and items are not placed back into the set after selection.
The process uses 
To count the number of elements, we need to count the number of nodes in the tree. We will write this using the following recurrence relation:
The first statement says for any node a depth zero we will count it once. The second statement states that for each element in 
Rearranging the second statement leads to 
k-Combinations
The k-combination is the way of selecting a fixed number of items from a set where the order of the selection is not important and items are not placed back into the set after selection.
The process is identical to the power set.
To count the number of elements, we need to count the number of nodes at depth
The first statement says for depth zero we will count once, the second statement states that we will add up whatever sum was produced by iterating over 
Important to notice that for 
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 
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;
}
One tree, many possibilities
Introduction
Given the finite set 
It should be evident from the example that the set of nodes at depth 
Now, if we change 
Without changing the definition of 
At this point, if we make a small change to 
Finally, without any further changes to the definition of 
Antimatroid, The 