Re: More on KSubsets

*To*: mathgroup at smc.vnet.net*Subject*: [mg2456] Re: More on KSubsets*From*: wagner at goober.cs.colorado.edu (Dave Wagner)*Date*: Wed, 8 Nov 1995 23:46:31 -0500*Organization*: University of Colorado, Boulder

In article <47mtfn$4nd at ralph.vnet.net>, Will Self <wself at viking.emcmt.edu> wrote: >Axel's question about KSubsets has some interesting variations. >For example, there is another possibly useful order on the k-subsets, >different from the lexicographic one. For a finite subset s of the non-negative integers, compute the number n such that the digits in the >binary representation for n corresponding to elements of s are 1, and the >rest of the digits are 0. For the set {0,1,3} the associated number would >be 2^0 + 2^1 + 2^3 = 11. > >Now you can order the subsets s according to their associated numbers n. >It's no problem to create the function nthSubset, which gives the nth >subset in this ordering, but what about the function nthKSubset, which >for a given k would return the nth k-subset in this ordering? Anyone >have a nice way to do this? Well, I don't know if this is "nice" or not, but here goes. To see where I'm headed, consider the following example of enumerating the k-subsets on the integers where k = 2: Rank Bits Decimal 1 000111 7 2 001011 11 3 001101 13 4 001110 14 5 010011 19 6 010101 21 7 010110 22 8 011001 25 9 011010 26 10 011100 28 11 100011 35 Number the bit positions starting with 0 on the right. Note that there are Binomial[d,2] subsets in which the high-order bit is in position d, because that's how many ways there are to arrange the remaining k-1=2 bits in positions 0..d-1. The following function computes the position of the high-order bit in the nth k-subset: In[1]:= hidigit[n_, k_] := Module[{s=1, d=k-1}, While[s < n, s += Binomial[++d, k-1]]; d ] In[2]:= Table[hidigit[i,3], {i,20}] Out[2]= {2, 3, 3, 3, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5} I'm also going to need the following function. bsum[k,n0,n] computes the sums of the binomial coefficients B[n0,k]+B[n0+1,k]+ ... +B[n,k]. In[3]:= bsum[k_,0,n_] := Binomial[n+1, k+1] bsum[k_,n0_,n_] := bsum[k,0,n] - bsum[k,0,n0-1] /; n0>0 Now nthKSubset is defined recursively as follows: In[5]:= nthKSubset[n_, k_] := Module[{d = hidigit[n,k]}, Flatten[ {nthKSubset[n-bsum[k-1,k-1,d-1],k-1], d} ] ] nthKSubset[1, k_] := Range[0,k-1] Here's a demonstration: In[7]:= Table[nthKSubset[i,3], {i,11}] Out[7]= {{0, 1, 2}, {0, 1, 3}, {0, 2, 3}, {1, 2, 3}, {0, 1, 4}, {0, 2, 4}, {1, 2, 4}, {0, 3, 4}, {1, 3, 4}, {2, 3, 4}, {0, 1, 5}} The decimal equivalents of the above are: In[8]:= Function[x, Fold[#1 + 2^#2&, 0, x]] /@ % Out[8]= {7, 11, 13, 14, 19, 21, 22, 25, 26, 28, 35} Here's an example with k=4: In[9]:= Table[nthKSubset[i,4], {i,10}] Out[9]= {{0, 1, 2, 3}, {0, 1, 2, 4}, {0, 1, 3, 4}, {0, 2, 3, 4}, {1, 2, 3, 4}, {0, 1, 2, 5}, {0, 1, 3, 5}, {0, 2, 3, 5}, {1, 2, 3, 5}, {0, 1, 4, 5}} In[10]:= Function[x, Fold[#1 + 2^#2&, 0, x]] /@ % Out[10]= {15, 23, 27, 29, 30, 39, 43, 45, 46, 51} Dave Wagner Principia Consulting (303) 786-8371 dbwagner at princon.com http://www.princon.com/princon