Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
1995
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 1995

[Date Index] [Thread Index] [Author Index]

Search the Archive

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