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

• Prev by Date: Re: help functions
• Next by Date: Re: Help on Infinite Series
• Previous by thread: More on KSubsets
• Next by thread: Speed of Mathematica under Windows 95