Everyone knows the powerset. It's extremely useful and I seem to see it everywhere now days. It always seems to be hidden in some problem where if you think about it hard enough you'll see in some way that the powerset is involved. 2^n is an obvious one, but anything binary seems to be deeply related to the powerset, even binary tree's. Of course they show up things like the binomial formula/combination values, and anything that is based on those(so one will find it in the zeta function hiding somewhere too, probably in many places if they could crack open the zeta function enough to find a valid representation. One starts to realize that in math essentially anything can be represented in some fashion as anything else with the right equations.
Everything below uses the list or non-commutative version of the powerset and combinations: [1,2] != [2,1]
My problem is much simpler though. I have a set of n things where I would like to find the easiest way to iterate through the k-sized combinations with the following criterion: Only one element can and must change as we iterate through the elements except when it is necessary to not repeat a previous combination.
E.g., Let $P$ be the k-combinations-n which is a subset of the powerset. Find mapping such that $p_i = T[p_{i-1}]$ with $p_0 \in P$ and $T$ generations $p_k$ such as that $p_k$ has the smallest and simplest variation possible.
All I would like to do is find the easiest mental way to iterate through a set of k-combinations-n so I can solve some mechanical problems. I have some combination already and I wanted to start with it and move to another combination that has the smallest number of changes(which is 1 and there are (k-1)-combinations-n that satisfy this but we have to choose the optimal one that aids in memorization(generally this is so one can simply sequence the pattern in some natural way)).
It is possible to represent each k-combination-n as bit pattern and the decimal representation to index the set of k-combination-n. This allows us to have an iterator for the set but moving from n to n+1 generally as no "natural" pattern in terms of decimal understanding. In binary though the representation is quite easy as we are just iterating through the binary integers.
An example, let k = 4 and n = 4 then (the set of) all the k-combinations-n is
1234 1243 1324 1342 1423 1432
2134 2143 2314 2341 2413 2431
3124 3142 3214 3241 3412 3421
4123 4132 4213 4231 4312 4321
I've memorized these 24 combinations of {1,2,3,4} so I can do mechanical work more meticulously. The above is not necessarily the best but it seems the most logical way to get through combinations in a descent order. One notes that it is simply a series of swaps(as we go down the list) minimize interorder jumps.
I would essentially like to generalize all this so I can work with larger set sizes. In particular this is for n=11 and k=7. An astute reader might be able to ascertain that particular case but, in fact, it is one of many. Hence, because of the complexity, finding the most efficient way to memorize the general case, within reason, is desirable. This is only about iteration rather than searching, there are only $7! \cdot {} _{11}C_{11-7} = 1663200$ possibilities which may seem like a lot but really isn't. We only want to memorize how to iteration and not memorize every combination. A sort of differential approach. This is so we can start at any combination and simple start iterating through all the combinations knowing we will eventually iterate through all of them each combination be iterated on only once.
It's a tremendous power to how to be able to iterate through the powerset in a precise way. Does anyone have such an algorithm handy?
