MathGroup Archive 1995

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

Search the Archive

Axel's question

  • To: mathgroup at
  • Subject: [mg2415] Axel's question
  • From: wself at (Will Self)
  • Date: Sun, 5 Nov 1995 16:05:06 -0500

Axel asked a very interesting question related to the function KSubsets in
the Combinatorica package.  That function generates a list of all k-subsets
(subsets of length k) of a given set.  Axel wanted to know how to create just 
the nth such k-subset without generating them all.  He also wanted to know
how to do the reverse: given a subset, find its rank, that is, where it occurs 
in the list generated by KSubsets, once again without actually generating the 

It's interesting to do it recursively, any yet more interesting that going
both ways is essentially the same.  And even more interesting is that
the recursion mimics quite closely the recursive definition for the
binomial coefficients.  Here it is without any error checking.  Note that
this relies on the Mathematica phenomenon 1 + {1,2,3} gives {2,3,4}.
I'm just doing it when the given set is Range[m].  Once you have that,
it's easy enough to do it for any other given set.

nthKSubset::usage =
	"nthKSubset[n, m, k] gives the subset of Range[m] of size k which
	appears at location n in the lexicographic ordering of these subsets."

nthKSubset[n_,m_,1]:= {n}

nthKSubset[1,m_,m_]:= Range[m]


1+nthKSubset[n-Binomial[m-1,k-1], m-1,k]

(*  Try this  *)

axel = Table[nthKSubset[x,7,3],{x,1,Binomial[7,3]}]

rank::usage =
	"For a subset s of Range[m], sorted in increasing order,
	rank[s, m] gives its location in the lexicographic ordering of the
	subsets of Range[m] having length Length[s]."

rank[{n_},m_]/;n<=m := n

rank[s_,m_]/;s==Range[m] := 1

rank[s_,m_]/;First[s]==1 :=

rank[s_,m_]/;First[s]>1 :=
Binomial[m-1,Length[s]-1] + rank[s-1,m-1]

(*  Now try this  *)

rank[#,7]& /@ axel

Maybe someone can suggest a better term than "rank".

Will Self

  • Prev by Date: Re: Troubles with Windows 95
  • Next by Date: Re: Troubles with Windows 95
  • Previous by thread: Re: 3D Cluster Detection
  • Next by thread: Re: running on IBM RS6000 Model 43P