(Fast way to) Get a combination given its position in (reverse-)lexicographic order
up vote
8
down vote
favorite
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).
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.
combinatorics combinations computational-mathematics
add a comment |
up vote
8
down vote
favorite
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).
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.
combinatorics combinations computational-mathematics
add a comment |
up vote
8
down vote
favorite
up vote
8
down vote
favorite
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).
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.
combinatorics combinations computational-mathematics
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).
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.
combinatorics combinations computational-mathematics
combinatorics combinations computational-mathematics
edited Apr 13 '17 at 12:20
Community♦
1
1
asked Jul 21 '15 at 9:00
van
1786
1786
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
up vote
3
down vote
To convert a lexicographic position to a combination:
Like the reverse problem discussed in Fast way to get a position of combination (without repetitions), a lexicographic position can be converted to a combination using combinatorial 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 ordinary binary number representations, let us define the leftmost position as MSB and the rightmost position 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, following the binary convention. The parameter $r$ is the number of ones to the right of the digit, including its own position.
For example,
$n=0$ for LSB and $n=5$ for MSB.
$r=3$ for leftmost one.
$r=1$ for rightmost one.
$r=2$ for the middle one.
Conversion From Lexicographic Position to Binary Tuple:
To convert a lexicographic position $L_number$ to its 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.
If place value $ge 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)$
If place value $< L_number$
- Move to next position $(n = n - 1)$
$textit{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}geqbinom{4}{3} = 4}$,
Result: $TRUE$,
Combination: $[ 0 1 . . . . ]$,
$r = 3-1 = 2$,
$L_n = L_n - 4 = 9-4=5$
Compare: ${ { L_n = 5}geqbinom{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}geqbinom{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}geqbinom{1}{0} = 1 } $,
Result: $FALSE$,
Combination: $[ 0 1 1 1 0 . ]$,
$r = 0$,
$L_n = 0$,
Compare: ${ { L_n = 0}geqbinom{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)$.
The 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
add a comment |
up vote
1
down vote
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}^kbinom{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 $xgeq 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 $igeq 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
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1368526%2ffast-way-to-get-a-combination-given-its-position-in-reverse-lexicographic-or%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
To convert a lexicographic position to a combination:
Like the reverse problem discussed in Fast way to get a position of combination (without repetitions), a lexicographic position can be converted to a combination using combinatorial 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 ordinary binary number representations, let us define the leftmost position as MSB and the rightmost position 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, following the binary convention. The parameter $r$ is the number of ones to the right of the digit, including its own position.
For example,
$n=0$ for LSB and $n=5$ for MSB.
$r=3$ for leftmost one.
$r=1$ for rightmost one.
$r=2$ for the middle one.
Conversion From Lexicographic Position to Binary Tuple:
To convert a lexicographic position $L_number$ to its 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.
If place value $ge 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)$
If place value $< L_number$
- Move to next position $(n = n - 1)$
$textit{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}geqbinom{4}{3} = 4}$,
Result: $TRUE$,
Combination: $[ 0 1 . . . . ]$,
$r = 3-1 = 2$,
$L_n = L_n - 4 = 9-4=5$
Compare: ${ { L_n = 5}geqbinom{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}geqbinom{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}geqbinom{1}{0} = 1 } $,
Result: $FALSE$,
Combination: $[ 0 1 1 1 0 . ]$,
$r = 0$,
$L_n = 0$,
Compare: ${ { L_n = 0}geqbinom{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)$.
The 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
add a comment |
up vote
3
down vote
To convert a lexicographic position to a combination:
Like the reverse problem discussed in Fast way to get a position of combination (without repetitions), a lexicographic position can be converted to a combination using combinatorial 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 ordinary binary number representations, let us define the leftmost position as MSB and the rightmost position 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, following the binary convention. The parameter $r$ is the number of ones to the right of the digit, including its own position.
For example,
$n=0$ for LSB and $n=5$ for MSB.
$r=3$ for leftmost one.
$r=1$ for rightmost one.
$r=2$ for the middle one.
Conversion From Lexicographic Position to Binary Tuple:
To convert a lexicographic position $L_number$ to its 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.
If place value $ge 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)$
If place value $< L_number$
- Move to next position $(n = n - 1)$
$textit{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}geqbinom{4}{3} = 4}$,
Result: $TRUE$,
Combination: $[ 0 1 . . . . ]$,
$r = 3-1 = 2$,
$L_n = L_n - 4 = 9-4=5$
Compare: ${ { L_n = 5}geqbinom{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}geqbinom{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}geqbinom{1}{0} = 1 } $,
Result: $FALSE$,
Combination: $[ 0 1 1 1 0 . ]$,
$r = 0$,
$L_n = 0$,
Compare: ${ { L_n = 0}geqbinom{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)$.
The 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
add a comment |
up vote
3
down vote
up vote
3
down vote
To convert a lexicographic position to a combination:
Like the reverse problem discussed in Fast way to get a position of combination (without repetitions), a lexicographic position can be converted to a combination using combinatorial 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 ordinary binary number representations, let us define the leftmost position as MSB and the rightmost position 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, following the binary convention. The parameter $r$ is the number of ones to the right of the digit, including its own position.
For example,
$n=0$ for LSB and $n=5$ for MSB.
$r=3$ for leftmost one.
$r=1$ for rightmost one.
$r=2$ for the middle one.
Conversion From Lexicographic Position to Binary Tuple:
To convert a lexicographic position $L_number$ to its 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.
If place value $ge 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)$
If place value $< L_number$
- Move to next position $(n = n - 1)$
$textit{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}geqbinom{4}{3} = 4}$,
Result: $TRUE$,
Combination: $[ 0 1 . . . . ]$,
$r = 3-1 = 2$,
$L_n = L_n - 4 = 9-4=5$
Compare: ${ { L_n = 5}geqbinom{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}geqbinom{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}geqbinom{1}{0} = 1 } $,
Result: $FALSE$,
Combination: $[ 0 1 1 1 0 . ]$,
$r = 0$,
$L_n = 0$,
Compare: ${ { L_n = 0}geqbinom{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)$.
The 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
To convert a lexicographic position to a combination:
Like the reverse problem discussed in Fast way to get a position of combination (without repetitions), a lexicographic position can be converted to a combination using combinatorial 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 ordinary binary number representations, let us define the leftmost position as MSB and the rightmost position 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, following the binary convention. The parameter $r$ is the number of ones to the right of the digit, including its own position.
For example,
$n=0$ for LSB and $n=5$ for MSB.
$r=3$ for leftmost one.
$r=1$ for rightmost one.
$r=2$ for the middle one.
Conversion From Lexicographic Position to Binary Tuple:
To convert a lexicographic position $L_number$ to its 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.
If place value $ge 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)$
If place value $< L_number$
- Move to next position $(n = n - 1)$
$textit{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}geqbinom{4}{3} = 4}$,
Result: $TRUE$,
Combination: $[ 0 1 . . . . ]$,
$r = 3-1 = 2$,
$L_n = L_n - 4 = 9-4=5$
Compare: ${ { L_n = 5}geqbinom{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}geqbinom{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}geqbinom{1}{0} = 1 } $,
Result: $FALSE$,
Combination: $[ 0 1 1 1 0 . ]$,
$r = 0$,
$L_n = 0$,
Compare: ${ { L_n = 0}geqbinom{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)$.
The 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
edited Nov 20 at 9:50
squeamish ossifrage
28519
28519
answered Jul 21 '15 at 10:11
Galaxy
332110
332110
add a comment |
add a comment |
up vote
1
down vote
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}^kbinom{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 $xgeq 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 $igeq 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
add a comment |
up vote
1
down vote
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}^kbinom{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 $xgeq 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 $igeq 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
add a comment |
up vote
1
down vote
up vote
1
down vote
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}^kbinom{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 $xgeq 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 $igeq 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
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}^kbinom{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 $xgeq 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 $igeq 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
edited Apr 13 '17 at 12:20
Community♦
1
1
answered Jul 22 '15 at 18:55
ccorn
8,21822046
8,21822046
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1368526%2ffast-way-to-get-a-combination-given-its-position-in-reverse-lexicographic-or%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown