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 .

Improve this question
$\endgroup$
6
  • 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
    Commented Oct 9, 2013 at 19:46
  • $\begingroup$ @PietroMajer. I have added another sub-question, in cases where k-sets are ordered in increasing lexicographic order. $\endgroup$
    – DurgaDatta
    Commented Oct 10, 2013 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
    Commented Oct 10, 2013 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
    Commented Oct 10, 2013 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
    Commented Oct 10, 2013 at 12:53

1 Answer 1

Reset to default
2
$\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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ ya, I was mistaken. I have added another sub-question (increasing k-sets). How do we modify $f$ now? $\endgroup$
    – DurgaDatta
    Commented Oct 10, 2013 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
    Commented Oct 10, 2013 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
    Commented Oct 10, 2013 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
    Commented Oct 10, 2013 at 12:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .