Indexing integer $k$-tuples

Question

At Multinomial permutation indexing is a great method for indexing all $k$-subsets and all sorted $k$-tuples. Below are a natural orderings for $k=3$ using that method. Subtract {0,1,2} from the subsets to get the sorted tuples.

What is a good way for indexing k-tuples? One main requirement is that all the tuples containing (0,1) would appear before the first tuple containing a 2.

I've found a few sorting methods for tuples that don't seem bad, but I haven't figured out an indexing scheme for them. I can't readily find 3-tuple or 4-tuple with index 777777777777. Here's one sorting method that also puts the ordered tuples first, but I don't know if that's best.

triples = SortBy[Tuples[Range[0, 4], {3}], {Max[#], Total[Abs[# - Sort[#]]], 
    Reverse[#]} &]; 
Graphics3D[{Blue, Line[triples]}, Boxed -> False] 

Is there some well-known method for indexing integer $k$-tuples?

Answer 1

The same general technique should work.

There are $(a+1)^k$ $k$-tuples with numbers in $\{0, \ldots, a\}$, of which $a^k$ contain only numbers in $\{0, \ldots, a-1\}$.

So your $3$-tuple with index $777777777777$:

• $9196^3 < 777777777777 \le 9197^3$ so the largest element is $9196$ and we want the $105016241$th tuple with a $9196$ but nothing larger.
• If the first element is less than $9196$ then the tail is a $2$-tuple which must contain at least one $9196$ and nothing larger. $\frac{105016241}{9197^2 - 9196^2} \approx 5709.58$, so the first element is $5709$ and the tail is the $10604$th $2$-tuple with a $9196$ but nothing larger.
• If the second element is less than $9196$ then its tail is a $1$-tuple which must contain at least one $9196$. $\frac{10604}{9197^1 - 9196^1} > 9196$ so the second element is $9196$ and the tail is the $1408$th $1$-tuple containing nothing larger than $9196$.
• The third element is therefore $1407$, and the entire tuple is $(5709, 9196, 1407)$.

---

Python code:

from itertools import count

def nth_tuple(n, k):
    """
    Gets the nth k-tuple in a sequence which has a non-decreasing maximum element of the tuple

    n: 1-indexed position in the sequence
    k: width of the tuple
    """

    def inner(n, k, limit, forced):
        if k == 1:
            return [limit] if forced else [n]
        elif forced:
            # If the first element is not limit, how many possible tails are there?
            forced_tails = (limit + 1) ** (k - 1) - limit ** (k - 1)
            first = min(n // forced_tails, limit)
            return [first] + inner(n - first * forced_tails, k - 1, limit, first < limit)
        else:
            # This is just a conversion to base (limit + 1)
            pow = (limit + 1) ** (k - 1)
            return [n // pow] + inner(n % pow, k - 1, limit, forced)

    # Switch to 0-indexed, because it's easier
    n -= 1

    # Find the limit
    limit = next(iter(x for x in count(0) if n < (x + 1) ** k))

    return inner(n - limit ** k, k, limit, True)