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