1
$\begingroup$

Let $\Sigma$ be a finite set of symbols with total order. Let $C_k$ be the set of all $k$-multiset (unordered collection of $k$ elements from $S$, with repetition allowed). We can order all the elements of $C_k$ in lexicographic order and index each element in that order i.e a bijective function $f: C_k \to [ 1, |C_k| ]$ can be defined where $f(x)$ will be the position/rank of $x$ in such ordering (Here $|C_k| = \binom{k + |\Sigma| -1}{|\Sigma|-1})$. I am looking for such bijective function which can be computed for any $x \in C_k$ without having sort the elements or to refer to any other element of $C_k$ in any way. Can we build such function?

UPDATE: When repetition is not allowed, i.e. indexing $k$-subsets of a set is solved as follows: arrange $k$ elements in decreasing order. Let such an ordering be $c= c_k, ..., c_1$ ($c_k > c_{k-1}>...> c_1$), then $f(c) = \sum_{i = 1}^{k} \binom{c_i}{i} $ gives such a bijection. (Combinatorial Number System)

ADDITION: My original question is answered. This gives lexicographical ordering when k-combinations are taken as decreasing sequence. How do we define a function which gives ordering as that of lexicographic order when k-combinations are taken as increasing. Mind that these two ordering are not 'reverse' of each others. Eg. When $S=\{0,1,2,3\}$ and we want ordering of 2-sets then the increasing ordering would give the ordering as: 01, 02,03, 12, 13, 23; and the decreasing ordering would give then ordering as: 01, 02, 12, 03, 13, 23 .

$\endgroup$
  • 1
    $\begingroup$ Just consider $C_k\ni a\mapsto f(a_k+k-1, a_{k-1}+k-2, \dots,a_2+1,a_1)$ (where the $a_j$'s are arranged in decreasing order, $a_k\ge a_{k-1}\dots\ge a_1$). $\endgroup$ – Pietro Majer Oct 9 '13 at 19:46
  • $\begingroup$ @PietroMajer. I have added another sub-question, in cases where k-sets are ordered in increasing lexicographic order. $\endgroup$ – DurgaDatta Oct 10 '13 at 12:26
  • $\begingroup$ As to the new question: the two order relations are not reverse of of each other, true; yet they are isomorphic. $\endgroup$ – Pietro Majer Oct 10 '13 at 12:28
  • $\begingroup$ Correct. Now, my intent is not just indexing but also preserve the order. I am using these index where order is important. $\endgroup$ – DurgaDatta Oct 10 '13 at 12:29
  • 2
    $\begingroup$ I'm saying there is again simple order isomorphism. Precisely, between what you call the "increasing ordering" and the "reversed decreasing ordering". Take an increasing sequence $(a_i)$ to $(k-a_{k-i+1})$. E.g. $01, 02, 03, 12, 13, 23$ are mapped resp. to $23, 13, 03, 12, 02, 01$; then apply the previous $f$ valued in $\{1,2,3,4,5,6\}$ followed by $x\mapsto 7-x$. $\endgroup$ – Pietro Majer Oct 10 '13 at 12:53
1
$\begingroup$

@PietroMajer's comment essentially contained the answer already:

Define a bijection $\phi$ between $k$-multisubsets of $\{ 1,\ldots,n \}$ to $k$-subsets of $\{ 1,\ldots,n+k-1\}$ by sending $\{ c_0 \leq c_1 \leq \ldots \leq c_{k-1} \}$ to $\{ c_0 < c_1+1 < c_2 + 2 < \ldots < c_{k-1}+k-1 \}$.

This map sends lex order on the $k$-multisubsets to lex order on $k$-subsets. Thus, given your lex-position map $f$ on $k$-subsets provides the lex-position map $f \circ \phi$ on $k$-multisubsets.

$\endgroup$
  • $\begingroup$ ya, I was mistaken. I have added another sub-question (increasing k-sets). How do we modify $f$ now? $\endgroup$ – DurgaDatta Oct 10 '13 at 12:18
  • $\begingroup$ to be honest: I think it's time for you to figure it out yourself. Or have you tried to and you weren't able to do so? What did you try? What problems did you have? $\endgroup$ – Christian Stump Oct 10 '13 at 12:44
  • $\begingroup$ I tried to search the literature. I did not find the solution for the problem, but for similar ones. Based on them, I tried to modify them and verify computationally. I think it is not a trivial question. $\endgroup$ – DurgaDatta Oct 10 '13 at 12:48
  • $\begingroup$ What about this: take the $i$-th word in your increasing ordering, reverse it, and add it to the $i$-th last word in your decreasing ordering. What you get is always get $(3,3)$. Is this a coincidence, or might it give you a way of producing the order? $\endgroup$ – Christian Stump Oct 10 '13 at 12:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.