Intereting Posts

For each $y \in \mathbb{R}$ either no $x$ with $f(x) = y$ or two such values of $x$. Show that $f$ is discontinuous.
Evaluation of $ \int\frac{\sqrt{\sin x}}{\sqrt{\sin x}+\sqrt{\cos x}}dx$
Cross product: matrix transformation identity
Functional Equation : If $(x-y)f(x+y) -(x+y)f(x-y) =4xy(x^2-y^2)$ for all x,y find f(x).
Prove that there are two frogs in one square.
The Fourier transform of a “comb function” is a comb function?
Fixed point in a continuous function
prove that the order of $2$ mod p is $2^{n+1}$
The $2^{nd}$, $4^{th}$ and $9^{th}$ terms of an AP
Power Series With Bernoulli Numbers
Integral of $\int e^{2x} \sin 3x\, dx$
Minimal $T_0$-topologies
Uniform continuity question
Relation: pairwise and mutually
XOR is commutative, associative, and its own inverse. Are there any other such functions?

*This question is the inverse of the Fast way to get a position of combination (without repetitions).*

Given all $\left(\!\!\binom{n}{k}\!\!\right)$ combinations without repetitions (in either lexicographic or reverse-lexicographic order), **what would be the most efficient way to translate/map/lookup a
position of the combination to the combination ($k$-tuple) itself?**

I need this to be fast for combinations of $\left(\!\!\binom{70}{7}\!\!\right)$ order of magnitude – very large, but not exceeding 2 billion (fits into `int32`

maximum value).

- Combinatorial proof of the identity ${n+1\choose k+1}={k\choose k}+{k+1\choose k}+…+{n-1\choose k}+{n\choose k}$
- What are the total number of ordered permutations of a list of elements (possibly repeated)?
- In how many ways can we put $31$ people in $3$ rooms?
- Tiling of regular polygon by rhombuses
- Finding out this combination
- In how many ways can these people be arranged for a photograph?

Below is an example of $\left(\!\!\binom{6}{3}\!\!\right)$, where the aim is to *quickly* translate value `9`

to tuple `(a, d, f)`

, while in the real problem $5 <= k <= 8$.

$$\begin{array}

{cccccc|c}

a&b&c&d&e&f&^{combination}/_{sort\_order}&

\\\hline

x&x&x& & & &1\\

x&x& &x& & &2\\

x&x& & &x& &3\\

x&x& & & &x&4\\

x& &x&x& & &5\\

x& &x& &x& &6\\

x& &x& & &x&7\\

x& & &x&x& &8\\

x& & &x& &x&9\\

x& & & &x&x&10\\

.&.&.&.&.&.&.\\

& & &x&x&x&20\\

\end{array}$$

I know that I could pre-calculate all the combinations and reverse the lookup dictionary. However, such dictionary would not be efficient in terms of memory usage. Therefore I am looking for either calculation-based approach, or a more efficient data structure to perform this mapping, and be able to process about 1 million such lookups during data processing job.

*Note: the position can be 0-based.*

- Vandermonde's Identity: How to find a closed formula for the given summation
- The number of subspaces of a vector space forming direct sum with a given subpace
- Universal algorithm to estimate probability of drawing certain combination of coloured balls
- How many zeros are there at $1000!$ in the base $24$
- How many ways can you put 8 red, 6 green and 7 blue balls in 4 indistinguishable bins?
- Is there a closed-form equation for $n!$? If not, why not?
- Odd and even numbers in Pascal's triangle-Sierpinski's triangle
- All the ternary n-words with an even sum of digits and a zero.
- Sums related to the Euler totient function
- Integer partition of n into k parts recurrence

**To convert lixicographic position to the combination:**

Like the reverse problem discussed in Fast way to get a position of combination (without repetitions) , the lexicographic position can be converted to the combination using cominatorial digit place values.

Let us define the tuple $[a,b,c]$ as a binary number $[0 0 0 1 1 1]$ and assign it the lexicographic order ZERO and henceforth treat each combination as a binary number.

Next we define the Least Significant Bit (LSB) and the Most Significant Bit (MSB). To be consistent with our ordinary binary number representations, let us define the left most position as MSB and the right most bit as LSB. Because we are picking three objects out of six, each corresponding binary tuple would have three ones and three zeros. Ones represent the objects selected and zeros represent the objects not selected.

Now define the place value to each digit. In ordinary binary numbers, digit place values start at LSB and go to MSB taking values $\{1,2,4,\cdots,2^n,\cdots \}$. Here $n$ is used as the position of the digit from LSB. Likewise combinatorial place value is defined as $\binom{n}{r}$. Where $n$ is the position of the digit from the LSB, same as binary convention. The parameter $r$ is the number of one’s to the right of the digit including its own position.

For example,

$n=0$ for LSB and $n=5$ for MSB.

$r=3$ for left most one.

$r=1$ for right most one.

$r=2$ for the middle one.

**Conversion From Lexicographic Position to Binary Tuple:**

To convert the lexicographic position, L_number, to corresponding combination, L_number is compared against the place value of the digit. The comparison starts at MSB. If the place value is less than L_number, the corresponding binary number is set to one and L_number is decremented by the place value.

Place value $>$ L_number

- Place ONE in that position
- Update L_number = L_number – place value
- Decrement $r$ in $\binom{n}{r}$
- Compare L_number to place value at next position to right $(n = n – 1)$

place vlaue $<$ L_number

- Move to next position $(n = n – 1)$

$Example:$

Find the combination of three objects from six at the lexicographic place $9$.

$L_n = 9$,

Compare: $\{ \{ L_n = 9\} \geq \binom{5}{3} = 10 \} $,Result:$FALSE$,

Combination: $[ 0 . . . . . ]$,

$r = 3$,

$L_n = 9$

Compare: $\{\{ L_n = 9\}\geq\binom{4}{3} = 4\}$,

Result: $TRUE$,

Combination: $[ 0 1 . . . . ]$,

$r = 3-1 = 2$,

$L_n = L_n – 4 = 9-4=5$

Compare: $\{ \{ L_n = 5\}\geq\binom{3}{2} = 3 \} $,

Result: $TRUE$,

Combination: $[ 0 1 1 . . . ]$,

$r = 2-1 = 1$,

$L_n = L_n – 3 = 5-3=2$

Compare: $\{\{ L_n = 2\}\geq\binom{2}{1} = 2 \} $,

Result: $TRUE$,

Combination: $[ 0 1 1 1 . . ]$,

$r = 1-1 = 0$,

$L_n = L_n – 2 = 2-2=0$

Compare: $\{ \{ L_n = 0\}\geq\binom{1}{0} = 1 \} $,

Result: $FALSE$,

Combination: $[ 0 1 1 1 0 . ]$,

$r = 0$,

$L_n = 0$,

Compare: $\{ \{ L_n = 0\}\geq\binom{0}{0} = 1 \} $,

Result: $FALSE$,

Combination: $[ 0 1 1 1 0 0 ]$,

$r = 1-1 = 0$,

$L_n = L_n – 2 = 2-2=0$

Since the final answer is $[0 1 1 1 0 0]$, the lexicographic order 9 corresponds to combination (c,d,e).

Following function returns an array of binary values, given the size of the objects $n$, the number of objects to be picked $r$ and the lexicographic order $m$.

```
function [out]=encode2ts(n,r,m)
%Encodes the input integer 'm' to a constant weight code of n-digits with r-ones
%Most significant digit at highest index.
out=zeros(1,n);
while (n>0)
if (n>r & r>=0)
y = nchoosek(n-1,r);
else
y = 0;
end
if (m>=y)
m = m - y;
out(n) = 1;
r = r - 1;
else
out(n) = 0;
end
n = n - 1;
end
```

For the preliminaries I have to refer you to my answer to the position-finding problem.

In particular, I will use reverse-lexicographic ordering and zero-based indices

because it is simpler.

Transforming to one-based indices and positions with lexicographic ordering,

as in your example table, can be done

by replacing the input position with its distance to $\binom{n}{k}$

and by transforming the output tuple from $(i_0,\ldots,i_{k-1})$

to $(n−i_{k-1},\ldots,n−i_0)$.

To recap: A $k$-index is herein defined to be a $k$-tuple of strictly increasing nonnegative integers.

For a $k$-index $I$, its zero-based position (or compressed index) $\operatorname{ordx}(I)$ is defined as the number of $k$-indices that are reverse-lexicographically smaller than $I$.

Denoting $I = (i_0,\ldots,i_{k-1})$, we have worked out the explicit formula

$$\operatorname{ordx}(I) = \sum_{r=1}^k\binom{i_{r-1}}{r} \tag{1}$$

Using $(1)$ and

$$\operatorname{ordx}(I) < \operatorname{ordx}\bigl((0,\ldots,k-2,i_{k-1}+1)\bigr) = \binom{i_{k-1}+1}{k}$$

we can deduce

$$\binom{i_{k-1}}{k} \leq \operatorname{ordx}(I) < \binom{i_{k-1}+1}{k}

\tag{2}$$

Given the requirement that $k$-index elements be nonnegative

and strictly increasing, we also know that $i_{k-1}\geq k-1$.

Now $\binom{x}{k}$ is a degree-$k$ polynomial in $x$ with zeros

$0,\ldots,k-1$ and positive leading coefficient,

so $\binom{x}{k}$ is nonnegative, unbounded, and strictly monotonic

for $x\geq k-1$, beginning with $\binom{k-1}{k}=0$,

so there exists precisely one solution $i_{k-1}\geq k-1$ for $(2)$.

From $(1)$ and $(2)$ we can figure out an algorithm to recover $i_{k-1}$

and ultimately all of $I$ from $s = \operatorname{ordx}(I)$.

Note that it requires explicit knowledge of the tuple length $k$:

**Function** $\operatorname{xord}(k, s)$:

**Input:**tuple length $k$, zero-based position $s$.-
**Output:**The $k$-index $I$ such that $\operatorname{ordx}(I) = s$.- If $k = 0$, return an empty tuple.
- Find $i$ such that $i\geq k-1$ and $b := \binom{i}{k}

\leq s < \binom{i+1}{k}$. - Set the $(k-1)$-index

$(i_0,\ldots,i_{k-2}) = \operatorname{xord}(k-1, s-b)$. - Return $(i_0,\ldots,i_{k-2},i)$.

The Python implementation below uses loops instead of function call recursion.

The search for $i_{k-1}$ with suitable $\binom{i}{k}$ proceeds upward;

once found, the remaining $i_r$ are found by downward search.

The binomial coefficients are computed on the fly, requiring less than about

$2i_{k-1}$ multiplications and divisions in total.

The search for $\binom{i}{1} = s$ is shortcut to $i = s$.

In the answer to the question about finding the position

$\operatorname{ordx}(I)$, I have also demonstrated a variant named

$\operatorname{ords}$ which allows repeated elements, that is,

combinations with replacement: Just replace every $i_r$ in the above discussion

with $i_r + r$, then the latter forms a strictly increasing sequence even when

the former is merely nondecreasing. Code for the corresponding inverse function

$\operatorname{sord}$ is given below; and for the sake of brevity,

I have implemented `xord`

in terms of `sord`

:

```
def xord(k, sk):
"""
Inverse function of ``ordx``, given output tuple size
and compressed index.
"""
return [i + r for r,i in enumerate(sord(k, sk))]
```

Alternatively, you might implement `xord`

like `sord`

below,

but with all output assignments of the form `idx[r] = j`

changed to `idx[r] = j + r`

, including the case `r = 1`

.

```
def sord(k, sk):
"""
Inverse function of ``ords``, given output tuple size
and compressed index.
"""
# Allocate output array. Content does not matter here, only length.
idx = [0] * k
if k == 0: return idx
s = sk
if k > 1:
# Find j such that binomial(j+k-1,k) <= s < binomial(j+k,k)
j = 0
prev_b = 0
b = 1
while b <= s:
# Maintain invariants:
# prev_b == binomial(j+k-1,k), b == binomial(j+k,k)
prev_b = b
j += 1
b *= j + k
b //= j
b = prev_b
# j is now the greatest index occurring in the tuple.
# From now on, we will search backwards, decreasing j.
for r in xrange(k-1, 1, -1):
# b == binomial(j+r,r+1) <= s < binomial(j+r+1,r+1)
idx[r] = j
s -= b
# Update to b = binomial(j+r-1,r)
b *= r + 1
b //= j + r
# Find j such that binomial(j+r-1,r) <= s < binomial(j+r,r)
while b > s:
j -= 1
b *= j
b //= j + r
# Simplified handling of r = 1
# b == binomial(j+r,r+1) <= s < binomial(j+r+1,r+1)
idx[1] = j
s -= b
# Simplified handling of r = 0
# binomial(j+r,r+1) == s iff j == s
idx[0] = s
return idx
```

If you use fixed-width integer variables, take care that the variable `b`

has enough bits available for the intermediate multiplications.

Verifying that `ordx`

inverts `xord`

can be done with something like:

```
assert ordx([]) == 0
assert xord(0, 0) == []
for k in xrange(1, 9):
for s in xrange(10000):
assert ordx(xord(k, s)) == s
```

- Finding the limit of a recursive sequence $x_{n+1}=\frac{1}{2}(x_{n}+\frac{M}{x_{n}})$
- Fibonacci combinatorial identity: $F_{2n} = {n \choose 0} F_0 + {n\choose 1} F_1 + … {n\choose n} F_n$
- relation between $W^{1,\infty}$ and $C^{0,1}$
- Continuous functions on discrete product topology
- my plane is not vertical, How to update 3D coordinate of point cloud to lie on a 3D vertical plane
- Gamma of 3z using triplication formula:
- Suppose that we flip a coin until either it comes up tails twice or we have flipped six times. What is the expected number of times we flip the coin?
- Notation for “the highest power of $p$ that divides $n$”
- Infinite Series: Fibonacci/ $2^n$
- Eccentered Circles – determine space between circle at a given location
- If $\sum a_n$ converges then $\sum (-1)^n \frac {a_n}{1+a_n^2}$ converges?
- Where am I violating the rules?
- Factor a polynomial
- Finding all groups with given property
- Uniform continuity of $f(x)=x^{\frac{2}{3}}\log x$ on $[0, \infty)$