[Math] Finding the Nth element in a list of all possible numbers

combinatoricselementary-number-theoryelementary-set-theory

This is an extension of my question found here:

Given some number of digits, each with a have a specified range from 1 to some number, what would be the Nth element in the list of all permutations of them found by first modifying the inner most digits.

For example, given 3 digits, the first one having a range of [1..3], second having [1..2] and third [1…4], the list would be

1 1 1
1 1 2
1 1 3
1 1 4
1 2 1
1 2 2
1 2 3
1 2 4
2 1 1
2 1 2
2 1 3
 ...

How would you find the Nth element of these types of sets? Conversely, given a number, how would you find the position in this set?

Best Answer

Let $S$ be the list of the number of possible value for each position in the list , and let $n$ be the position in the list. Let $i$ be the length of the elements of the list initially. The process for obtaining the element is: $q = n/(prod_{x=0}^{i}S_i)$

$n = n\bmod prod_{x=0}^{i}S_i+1$

$i = i-1$

And each successive value of $n$ is the $i$th digit of the element.

Given an element the position is $\sum_{x=0}^{\text{length of the elements of the list}}\prod_{x=0}^{i}\times(\text{xth digit of the element from left to right}-1)$

Basically this problem is a degenerate case (a general case) of converting into bases, except that 1 is used for 0, 2 for 1, (so 1111 in this list would map to 0000), etc. I'll post a proof soon. Not sure if it is correct; will verify this later. Also the output/input might be zero-indexed (starting from zero).

Related Question