The solutions in the article certainly aren’t, with their for and while loops.
I think that’s moving the goalposts.
It depends on your cost model. If your cost model is with respect to n, this requirement does not move the goalposts because the solution in the article does not depend on n and k is fixed. Computing (1) the natural number corresponding to any n choose k subset or (2) the subset corresponding to any natural number n takes constant time (assuming a constant cost model for all naturals).
So, the result is in T. You subtract n, leaving 4, and use whatever bijection you had for T to decode that into an element of T.
If, on the other hand, you had n-4, you know it must decode to an element of S, and directly use its decoder to find that element.
If you have a bijection between the items of some finite set S and {1,…,n} and a bijection between the items of some other finite set T disjunct with S and {1,…,m}, constructing a bijection between S ∪ T and {1,…,n+m} is trivial. For example, map the items of S to {1,n} as before and the items of T to {n+1,…n+m}, adding n to each of the values that you originally mapped each item of T to.
If you have a third finite set disjunct with S and T, it’s disjunct with S ∪ T, so you can repeat this construction.
“All subsets whose size is at most k” is the union of “all subsets whose size is zero”, “all subsets whose size is 1”, “all subsets whose size is 2”, … “ all subsets whose size is k”, and those sets are finite and disjunct, so you can use the above to construct such a mapping.
(as long as the set of common items is computable, “disjunct” is not essential in the above, but it would make the mapping more complex. “Finite” also isn’t necessary, as long as they’re countably infinite and you have finitely many sets. I think even a countably infinite number of countably infinite sets would work)