posted 4 days ago
Hey, fun question! (Though this is not something covered in Math for Programmers... perhaps a future book!)
The power set of a set is the set of all of its subsets; it is a set of sets. Sets by their nature don't come with orders. It sounds like this is asking for all possible lists of length <= n whose entries are taken from some set. This is related to cartesian products and cartesian power sets more so than ordinary power sets.
Here's an example. If S is the set of possible values, like {4,5,6,7} then there's one singleton list for every element of S: [4], [5], [6], [7]
The cartesian product S x S is the set of all ordered pairs taken from the list, consisting of [4,4], [4,5], [4,6], [4,7], [5,4], [5,5], ... and so on (there are 4*4 = 16 of these)
The cartesian product S x S x S is the set of all ordered triples of elements of S, so [4,4,4], [4,4,5], and so on...
We also write S^n to be the n-fold cartesian product, so the cartesian product of n copies of S which looks like S x S x S x ... x S. This is the set of all ordered n-tuples of elements of S. For example, S^2 = S x S and S^4 = S x S x S x S, the set of all ordered 4-tuples. S^0 contains a 0-tuple of elements of S, i.e. an empty list. (I'm not sure how to write superscripts in this forum but, S^n is written like S to the nth power, indicating that it's a repeated product).
If you want, say, all possible lists of length <= 4 what you want to do is take the union of the carteisan powers S^0, S^1, S^2, S^3, and S^4, as in the combination of all elements of these sets. This is
So, the point is, this problem looks expressible in terms of set terminology, but perhaps not using the power set. Here's a Python solution, where the first function computes the nth cartesian power of a list elts of inputs, and then the second function computes their union