Axel's question
- To: mathgroup at smc.vnet.net
- Subject: [mg2415] Axel's question
- From: wself at viking.emcmt.edu (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
list.
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]
nthKSubset[n_,m_,k_]/;n<=Binomial[m-1,k-1]:=
Prepend[1+nthKSubset[n,m-1,k-1],1]
nthKSubset[n_,m_,k_]/;n>Binomial[m-1,k-1]:=
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[Rest[s]-1,m-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