Find a function $f_m $ that enumerates all subsets of ${1,..,n}$ of cardinality $m$ in ascending order
I'm Looking for a function
$f_m: {1,..,n} to {(Msubseteq{1,...,n}: |M|=m} $
that enumerates all subsets of ${1,..,n}$ of cardinality $m$ in ascending order.
For example, for the set ${1,2,3,4}$ we'd have:
$f_3(1)={ 1,2,3 }, f_3(2)= { 1,2,4 }, f_3(3)= { 1,3,4 }$
Algorithmically, we could generate $f_m$ for a set ${1,..,n}$ by putting all subsets $Msubseteq {1,..,n}$ with $|M|=m$ in a list $L$, then sorting it in ascending order (where a < b exactly iff for the first element a[i] with
a[i] != b[i] the inequality a[i] < b[i] holds), and we'd find that $L[i] = f_m(i)$, where $L[i]$ is the i-th element of the list (starting by 1).
Is there any mathematical definition of $f$ that can be calculated in polynomial time?
Okay, so far I think I've found the inverse of $f_m$:
Let $f_m: {1,..,n} to {(Msubseteq{1,...,n}: |M|=m} $ be defined as above.
Then we have
$$f_m^{-1}{a_1,...,a_k} = 1+ sum_{j=1}^{k-1} sum_{i=1}^{a_j-a_{j-1}-1}binom{n-a_{j-1}-i}{k-j}$$, where we define $a_0 :=0$.
As we already know that $f_m$ is bijective (otherwise it wouldn't be an enumeration), we know therefore, that for any $min {1,...,binom{n}{k}}$ there is a unique solution of
$$m = 1+ sum_{j=1}^{k-1} sum_{i=1}^{a_j-a_{j-1}-1}binom{n-a_{j-1}-i}{k-j}$$
for $a_1,...,a_n$, where for every $a_i$ holds $a_iin{1,...,n} $ and $a_1<...<a_n$.
special-functions
add a comment |
I'm Looking for a function
$f_m: {1,..,n} to {(Msubseteq{1,...,n}: |M|=m} $
that enumerates all subsets of ${1,..,n}$ of cardinality $m$ in ascending order.
For example, for the set ${1,2,3,4}$ we'd have:
$f_3(1)={ 1,2,3 }, f_3(2)= { 1,2,4 }, f_3(3)= { 1,3,4 }$
Algorithmically, we could generate $f_m$ for a set ${1,..,n}$ by putting all subsets $Msubseteq {1,..,n}$ with $|M|=m$ in a list $L$, then sorting it in ascending order (where a < b exactly iff for the first element a[i] with
a[i] != b[i] the inequality a[i] < b[i] holds), and we'd find that $L[i] = f_m(i)$, where $L[i]$ is the i-th element of the list (starting by 1).
Is there any mathematical definition of $f$ that can be calculated in polynomial time?
Okay, so far I think I've found the inverse of $f_m$:
Let $f_m: {1,..,n} to {(Msubseteq{1,...,n}: |M|=m} $ be defined as above.
Then we have
$$f_m^{-1}{a_1,...,a_k} = 1+ sum_{j=1}^{k-1} sum_{i=1}^{a_j-a_{j-1}-1}binom{n-a_{j-1}-i}{k-j}$$, where we define $a_0 :=0$.
As we already know that $f_m$ is bijective (otherwise it wouldn't be an enumeration), we know therefore, that for any $min {1,...,binom{n}{k}}$ there is a unique solution of
$$m = 1+ sum_{j=1}^{k-1} sum_{i=1}^{a_j-a_{j-1}-1}binom{n-a_{j-1}-i}{k-j}$$
for $a_1,...,a_n$, where for every $a_i$ holds $a_iin{1,...,n} $ and $a_1<...<a_n$.
special-functions
add a comment |
I'm Looking for a function
$f_m: {1,..,n} to {(Msubseteq{1,...,n}: |M|=m} $
that enumerates all subsets of ${1,..,n}$ of cardinality $m$ in ascending order.
For example, for the set ${1,2,3,4}$ we'd have:
$f_3(1)={ 1,2,3 }, f_3(2)= { 1,2,4 }, f_3(3)= { 1,3,4 }$
Algorithmically, we could generate $f_m$ for a set ${1,..,n}$ by putting all subsets $Msubseteq {1,..,n}$ with $|M|=m$ in a list $L$, then sorting it in ascending order (where a < b exactly iff for the first element a[i] with
a[i] != b[i] the inequality a[i] < b[i] holds), and we'd find that $L[i] = f_m(i)$, where $L[i]$ is the i-th element of the list (starting by 1).
Is there any mathematical definition of $f$ that can be calculated in polynomial time?
Okay, so far I think I've found the inverse of $f_m$:
Let $f_m: {1,..,n} to {(Msubseteq{1,...,n}: |M|=m} $ be defined as above.
Then we have
$$f_m^{-1}{a_1,...,a_k} = 1+ sum_{j=1}^{k-1} sum_{i=1}^{a_j-a_{j-1}-1}binom{n-a_{j-1}-i}{k-j}$$, where we define $a_0 :=0$.
As we already know that $f_m$ is bijective (otherwise it wouldn't be an enumeration), we know therefore, that for any $min {1,...,binom{n}{k}}$ there is a unique solution of
$$m = 1+ sum_{j=1}^{k-1} sum_{i=1}^{a_j-a_{j-1}-1}binom{n-a_{j-1}-i}{k-j}$$
for $a_1,...,a_n$, where for every $a_i$ holds $a_iin{1,...,n} $ and $a_1<...<a_n$.
special-functions
I'm Looking for a function
$f_m: {1,..,n} to {(Msubseteq{1,...,n}: |M|=m} $
that enumerates all subsets of ${1,..,n}$ of cardinality $m$ in ascending order.
For example, for the set ${1,2,3,4}$ we'd have:
$f_3(1)={ 1,2,3 }, f_3(2)= { 1,2,4 }, f_3(3)= { 1,3,4 }$
Algorithmically, we could generate $f_m$ for a set ${1,..,n}$ by putting all subsets $Msubseteq {1,..,n}$ with $|M|=m$ in a list $L$, then sorting it in ascending order (where a < b exactly iff for the first element a[i] with
a[i] != b[i] the inequality a[i] < b[i] holds), and we'd find that $L[i] = f_m(i)$, where $L[i]$ is the i-th element of the list (starting by 1).
Is there any mathematical definition of $f$ that can be calculated in polynomial time?
Okay, so far I think I've found the inverse of $f_m$:
Let $f_m: {1,..,n} to {(Msubseteq{1,...,n}: |M|=m} $ be defined as above.
Then we have
$$f_m^{-1}{a_1,...,a_k} = 1+ sum_{j=1}^{k-1} sum_{i=1}^{a_j-a_{j-1}-1}binom{n-a_{j-1}-i}{k-j}$$, where we define $a_0 :=0$.
As we already know that $f_m$ is bijective (otherwise it wouldn't be an enumeration), we know therefore, that for any $min {1,...,binom{n}{k}}$ there is a unique solution of
$$m = 1+ sum_{j=1}^{k-1} sum_{i=1}^{a_j-a_{j-1}-1}binom{n-a_{j-1}-i}{k-j}$$
for $a_1,...,a_n$, where for every $a_i$ holds $a_iin{1,...,n} $ and $a_1<...<a_n$.
special-functions
special-functions
edited Nov 28 at 11:37
asked Nov 28 at 9:40
Sudix
8781316
8781316
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
I'll introduce a slight change of notation that will hopefully make things easier to understand. First, for later recursions, I'll put the $n$ into the function definition as well. Second, instead of having the co-domain be sets of size $m$, I'll have it be $m$-tuples in increasing order. It should be clear that this is an equivalent formulation:
$$f^{n,m}: left{1,..,{n choose m}right} to {(e_1, ldots, e_m): e_1 < ldots < e_m, e_i in {1,ldots,n} forall i=1,ldots,m}$$.
The $i$-th component ($1 le i le m$) of the function value would then be denoted as $f_i^{n,m}$. So in the problem's example $f_1^{4,3}(1)=1, f_3^{4,3}(2)=4$, etc.
To tackle the problem, it makes sense to apply recursion, both accessing smaller $n$ and smaller $m$. To start the recursion, we note that
$$ f_1^{n,1} (x) = x, forall x in {1,ldots,n}$$
completely solves the $m=1$ case for all $n$, and that this is also all there is for $n=1$.
For any $n,m$ with $m > 1$ there are exactly $n-1 choose m-1$ tuples starting with $1$, exactly $n-2 choose m-1$ tuples starting with $2$, a.s.o. until there are exactly ${m-1 choose m-1} = 1$ tuples starting with $n-m+1$.
So to dermine $f_1^{n,m}(x)$, do something like (pseudocode)
$$r=1$$
$$y=x$$
$$text{loop: }y=y-{n-r choose m-1}$$
$$text{if } y > 0: r=r+1, text {goto loop}$$
$$y = y + {n-r choose m-1}$$
and we have $f_1^{n,m}(x)=r$ and get a value $y$ that we need later.
Once we've found $f_1^{n,m}(x)$, finding the remaining components is a matter of applying recursion. Since our first component is $r$, the remaining $m-1$ components must come from the set ${r+1,ldots,n}$. This is isomorphic to asking for increasing $m-1$ tuples in ${1,ldots,n-r}$, so we get
$$f_i^{n,m}(x) = f_{i-1}^{n-r,m-1}(?) + r, quad forall i=2,ldots,m$$
The "$+r$" comes from the fact that recursion works on ${1,ldots,n-r}$, the shift in $i$ is that we already know the 1st component of $f^{n,m}$ and the second, third,$ldots$ component in it is the first,second,$ldots$ component from the recursion.
The only mystery is the argument for which we should call $f_{i-1}^{n-r,m-1}$. It can't possibly be $x$ in all cases, as that may be to big for the domain of the function. That's the $y$-value we calculated. It describes what is 'left' of $x$ after we jumped over all the arguments that map to a first component that is less than $r$. So we finally have
$$f_i^{n,m}(x) = f_{i-1}^{n-r,m-1}(y) + r, quad forall i=2,ldots,m$$
++++
As for the running time of this algorithm, first let's find a suitable input size description. For $n$ that would be $log n$, as usual. As the output requires $m$ values, the algorithm by necessity has a time that is at least linear in $m$, so input size would be something like $max(log n, m)$.
The most time consuming part of the algorithm is calculating the binomial coefficients. Since the lower number of them is always $le m$, and the upper number always $le n$, this boils down to calculating at most $2m$ products of numbers less than $n$ and one final division. That is something that is polynomial in $log n$ and $m$.
The other part of the algorithms are a loop that runs at most $m$ times and a recursion that the goes at most $m$ levels deep. The remaining parts are simple operations and comparisons.
So this algorithm works indeed on polynomial time with $max(log n, m)$ as input size.
Thanks for this awesome answer! I've been wondering about this for quite some time, and seeing this feels like I've gained the missing pieces to some long due puzzles!
– Sudix
Nov 28 at 12:58
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',
autoActivateHeartbeat: false,
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%2f3016960%2ffind-a-function-f-m-that-enumerates-all-subsets-of-1-n-of-cardinalit%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
I'll introduce a slight change of notation that will hopefully make things easier to understand. First, for later recursions, I'll put the $n$ into the function definition as well. Second, instead of having the co-domain be sets of size $m$, I'll have it be $m$-tuples in increasing order. It should be clear that this is an equivalent formulation:
$$f^{n,m}: left{1,..,{n choose m}right} to {(e_1, ldots, e_m): e_1 < ldots < e_m, e_i in {1,ldots,n} forall i=1,ldots,m}$$.
The $i$-th component ($1 le i le m$) of the function value would then be denoted as $f_i^{n,m}$. So in the problem's example $f_1^{4,3}(1)=1, f_3^{4,3}(2)=4$, etc.
To tackle the problem, it makes sense to apply recursion, both accessing smaller $n$ and smaller $m$. To start the recursion, we note that
$$ f_1^{n,1} (x) = x, forall x in {1,ldots,n}$$
completely solves the $m=1$ case for all $n$, and that this is also all there is for $n=1$.
For any $n,m$ with $m > 1$ there are exactly $n-1 choose m-1$ tuples starting with $1$, exactly $n-2 choose m-1$ tuples starting with $2$, a.s.o. until there are exactly ${m-1 choose m-1} = 1$ tuples starting with $n-m+1$.
So to dermine $f_1^{n,m}(x)$, do something like (pseudocode)
$$r=1$$
$$y=x$$
$$text{loop: }y=y-{n-r choose m-1}$$
$$text{if } y > 0: r=r+1, text {goto loop}$$
$$y = y + {n-r choose m-1}$$
and we have $f_1^{n,m}(x)=r$ and get a value $y$ that we need later.
Once we've found $f_1^{n,m}(x)$, finding the remaining components is a matter of applying recursion. Since our first component is $r$, the remaining $m-1$ components must come from the set ${r+1,ldots,n}$. This is isomorphic to asking for increasing $m-1$ tuples in ${1,ldots,n-r}$, so we get
$$f_i^{n,m}(x) = f_{i-1}^{n-r,m-1}(?) + r, quad forall i=2,ldots,m$$
The "$+r$" comes from the fact that recursion works on ${1,ldots,n-r}$, the shift in $i$ is that we already know the 1st component of $f^{n,m}$ and the second, third,$ldots$ component in it is the first,second,$ldots$ component from the recursion.
The only mystery is the argument for which we should call $f_{i-1}^{n-r,m-1}$. It can't possibly be $x$ in all cases, as that may be to big for the domain of the function. That's the $y$-value we calculated. It describes what is 'left' of $x$ after we jumped over all the arguments that map to a first component that is less than $r$. So we finally have
$$f_i^{n,m}(x) = f_{i-1}^{n-r,m-1}(y) + r, quad forall i=2,ldots,m$$
++++
As for the running time of this algorithm, first let's find a suitable input size description. For $n$ that would be $log n$, as usual. As the output requires $m$ values, the algorithm by necessity has a time that is at least linear in $m$, so input size would be something like $max(log n, m)$.
The most time consuming part of the algorithm is calculating the binomial coefficients. Since the lower number of them is always $le m$, and the upper number always $le n$, this boils down to calculating at most $2m$ products of numbers less than $n$ and one final division. That is something that is polynomial in $log n$ and $m$.
The other part of the algorithms are a loop that runs at most $m$ times and a recursion that the goes at most $m$ levels deep. The remaining parts are simple operations and comparisons.
So this algorithm works indeed on polynomial time with $max(log n, m)$ as input size.
Thanks for this awesome answer! I've been wondering about this for quite some time, and seeing this feels like I've gained the missing pieces to some long due puzzles!
– Sudix
Nov 28 at 12:58
add a comment |
I'll introduce a slight change of notation that will hopefully make things easier to understand. First, for later recursions, I'll put the $n$ into the function definition as well. Second, instead of having the co-domain be sets of size $m$, I'll have it be $m$-tuples in increasing order. It should be clear that this is an equivalent formulation:
$$f^{n,m}: left{1,..,{n choose m}right} to {(e_1, ldots, e_m): e_1 < ldots < e_m, e_i in {1,ldots,n} forall i=1,ldots,m}$$.
The $i$-th component ($1 le i le m$) of the function value would then be denoted as $f_i^{n,m}$. So in the problem's example $f_1^{4,3}(1)=1, f_3^{4,3}(2)=4$, etc.
To tackle the problem, it makes sense to apply recursion, both accessing smaller $n$ and smaller $m$. To start the recursion, we note that
$$ f_1^{n,1} (x) = x, forall x in {1,ldots,n}$$
completely solves the $m=1$ case for all $n$, and that this is also all there is for $n=1$.
For any $n,m$ with $m > 1$ there are exactly $n-1 choose m-1$ tuples starting with $1$, exactly $n-2 choose m-1$ tuples starting with $2$, a.s.o. until there are exactly ${m-1 choose m-1} = 1$ tuples starting with $n-m+1$.
So to dermine $f_1^{n,m}(x)$, do something like (pseudocode)
$$r=1$$
$$y=x$$
$$text{loop: }y=y-{n-r choose m-1}$$
$$text{if } y > 0: r=r+1, text {goto loop}$$
$$y = y + {n-r choose m-1}$$
and we have $f_1^{n,m}(x)=r$ and get a value $y$ that we need later.
Once we've found $f_1^{n,m}(x)$, finding the remaining components is a matter of applying recursion. Since our first component is $r$, the remaining $m-1$ components must come from the set ${r+1,ldots,n}$. This is isomorphic to asking for increasing $m-1$ tuples in ${1,ldots,n-r}$, so we get
$$f_i^{n,m}(x) = f_{i-1}^{n-r,m-1}(?) + r, quad forall i=2,ldots,m$$
The "$+r$" comes from the fact that recursion works on ${1,ldots,n-r}$, the shift in $i$ is that we already know the 1st component of $f^{n,m}$ and the second, third,$ldots$ component in it is the first,second,$ldots$ component from the recursion.
The only mystery is the argument for which we should call $f_{i-1}^{n-r,m-1}$. It can't possibly be $x$ in all cases, as that may be to big for the domain of the function. That's the $y$-value we calculated. It describes what is 'left' of $x$ after we jumped over all the arguments that map to a first component that is less than $r$. So we finally have
$$f_i^{n,m}(x) = f_{i-1}^{n-r,m-1}(y) + r, quad forall i=2,ldots,m$$
++++
As for the running time of this algorithm, first let's find a suitable input size description. For $n$ that would be $log n$, as usual. As the output requires $m$ values, the algorithm by necessity has a time that is at least linear in $m$, so input size would be something like $max(log n, m)$.
The most time consuming part of the algorithm is calculating the binomial coefficients. Since the lower number of them is always $le m$, and the upper number always $le n$, this boils down to calculating at most $2m$ products of numbers less than $n$ and one final division. That is something that is polynomial in $log n$ and $m$.
The other part of the algorithms are a loop that runs at most $m$ times and a recursion that the goes at most $m$ levels deep. The remaining parts are simple operations and comparisons.
So this algorithm works indeed on polynomial time with $max(log n, m)$ as input size.
Thanks for this awesome answer! I've been wondering about this for quite some time, and seeing this feels like I've gained the missing pieces to some long due puzzles!
– Sudix
Nov 28 at 12:58
add a comment |
I'll introduce a slight change of notation that will hopefully make things easier to understand. First, for later recursions, I'll put the $n$ into the function definition as well. Second, instead of having the co-domain be sets of size $m$, I'll have it be $m$-tuples in increasing order. It should be clear that this is an equivalent formulation:
$$f^{n,m}: left{1,..,{n choose m}right} to {(e_1, ldots, e_m): e_1 < ldots < e_m, e_i in {1,ldots,n} forall i=1,ldots,m}$$.
The $i$-th component ($1 le i le m$) of the function value would then be denoted as $f_i^{n,m}$. So in the problem's example $f_1^{4,3}(1)=1, f_3^{4,3}(2)=4$, etc.
To tackle the problem, it makes sense to apply recursion, both accessing smaller $n$ and smaller $m$. To start the recursion, we note that
$$ f_1^{n,1} (x) = x, forall x in {1,ldots,n}$$
completely solves the $m=1$ case for all $n$, and that this is also all there is for $n=1$.
For any $n,m$ with $m > 1$ there are exactly $n-1 choose m-1$ tuples starting with $1$, exactly $n-2 choose m-1$ tuples starting with $2$, a.s.o. until there are exactly ${m-1 choose m-1} = 1$ tuples starting with $n-m+1$.
So to dermine $f_1^{n,m}(x)$, do something like (pseudocode)
$$r=1$$
$$y=x$$
$$text{loop: }y=y-{n-r choose m-1}$$
$$text{if } y > 0: r=r+1, text {goto loop}$$
$$y = y + {n-r choose m-1}$$
and we have $f_1^{n,m}(x)=r$ and get a value $y$ that we need later.
Once we've found $f_1^{n,m}(x)$, finding the remaining components is a matter of applying recursion. Since our first component is $r$, the remaining $m-1$ components must come from the set ${r+1,ldots,n}$. This is isomorphic to asking for increasing $m-1$ tuples in ${1,ldots,n-r}$, so we get
$$f_i^{n,m}(x) = f_{i-1}^{n-r,m-1}(?) + r, quad forall i=2,ldots,m$$
The "$+r$" comes from the fact that recursion works on ${1,ldots,n-r}$, the shift in $i$ is that we already know the 1st component of $f^{n,m}$ and the second, third,$ldots$ component in it is the first,second,$ldots$ component from the recursion.
The only mystery is the argument for which we should call $f_{i-1}^{n-r,m-1}$. It can't possibly be $x$ in all cases, as that may be to big for the domain of the function. That's the $y$-value we calculated. It describes what is 'left' of $x$ after we jumped over all the arguments that map to a first component that is less than $r$. So we finally have
$$f_i^{n,m}(x) = f_{i-1}^{n-r,m-1}(y) + r, quad forall i=2,ldots,m$$
++++
As for the running time of this algorithm, first let's find a suitable input size description. For $n$ that would be $log n$, as usual. As the output requires $m$ values, the algorithm by necessity has a time that is at least linear in $m$, so input size would be something like $max(log n, m)$.
The most time consuming part of the algorithm is calculating the binomial coefficients. Since the lower number of them is always $le m$, and the upper number always $le n$, this boils down to calculating at most $2m$ products of numbers less than $n$ and one final division. That is something that is polynomial in $log n$ and $m$.
The other part of the algorithms are a loop that runs at most $m$ times and a recursion that the goes at most $m$ levels deep. The remaining parts are simple operations and comparisons.
So this algorithm works indeed on polynomial time with $max(log n, m)$ as input size.
I'll introduce a slight change of notation that will hopefully make things easier to understand. First, for later recursions, I'll put the $n$ into the function definition as well. Second, instead of having the co-domain be sets of size $m$, I'll have it be $m$-tuples in increasing order. It should be clear that this is an equivalent formulation:
$$f^{n,m}: left{1,..,{n choose m}right} to {(e_1, ldots, e_m): e_1 < ldots < e_m, e_i in {1,ldots,n} forall i=1,ldots,m}$$.
The $i$-th component ($1 le i le m$) of the function value would then be denoted as $f_i^{n,m}$. So in the problem's example $f_1^{4,3}(1)=1, f_3^{4,3}(2)=4$, etc.
To tackle the problem, it makes sense to apply recursion, both accessing smaller $n$ and smaller $m$. To start the recursion, we note that
$$ f_1^{n,1} (x) = x, forall x in {1,ldots,n}$$
completely solves the $m=1$ case for all $n$, and that this is also all there is for $n=1$.
For any $n,m$ with $m > 1$ there are exactly $n-1 choose m-1$ tuples starting with $1$, exactly $n-2 choose m-1$ tuples starting with $2$, a.s.o. until there are exactly ${m-1 choose m-1} = 1$ tuples starting with $n-m+1$.
So to dermine $f_1^{n,m}(x)$, do something like (pseudocode)
$$r=1$$
$$y=x$$
$$text{loop: }y=y-{n-r choose m-1}$$
$$text{if } y > 0: r=r+1, text {goto loop}$$
$$y = y + {n-r choose m-1}$$
and we have $f_1^{n,m}(x)=r$ and get a value $y$ that we need later.
Once we've found $f_1^{n,m}(x)$, finding the remaining components is a matter of applying recursion. Since our first component is $r$, the remaining $m-1$ components must come from the set ${r+1,ldots,n}$. This is isomorphic to asking for increasing $m-1$ tuples in ${1,ldots,n-r}$, so we get
$$f_i^{n,m}(x) = f_{i-1}^{n-r,m-1}(?) + r, quad forall i=2,ldots,m$$
The "$+r$" comes from the fact that recursion works on ${1,ldots,n-r}$, the shift in $i$ is that we already know the 1st component of $f^{n,m}$ and the second, third,$ldots$ component in it is the first,second,$ldots$ component from the recursion.
The only mystery is the argument for which we should call $f_{i-1}^{n-r,m-1}$. It can't possibly be $x$ in all cases, as that may be to big for the domain of the function. That's the $y$-value we calculated. It describes what is 'left' of $x$ after we jumped over all the arguments that map to a first component that is less than $r$. So we finally have
$$f_i^{n,m}(x) = f_{i-1}^{n-r,m-1}(y) + r, quad forall i=2,ldots,m$$
++++
As for the running time of this algorithm, first let's find a suitable input size description. For $n$ that would be $log n$, as usual. As the output requires $m$ values, the algorithm by necessity has a time that is at least linear in $m$, so input size would be something like $max(log n, m)$.
The most time consuming part of the algorithm is calculating the binomial coefficients. Since the lower number of them is always $le m$, and the upper number always $le n$, this boils down to calculating at most $2m$ products of numbers less than $n$ and one final division. That is something that is polynomial in $log n$ and $m$.
The other part of the algorithms are a loop that runs at most $m$ times and a recursion that the goes at most $m$ levels deep. The remaining parts are simple operations and comparisons.
So this algorithm works indeed on polynomial time with $max(log n, m)$ as input size.
answered Nov 28 at 12:35
Ingix
3,214145
3,214145
Thanks for this awesome answer! I've been wondering about this for quite some time, and seeing this feels like I've gained the missing pieces to some long due puzzles!
– Sudix
Nov 28 at 12:58
add a comment |
Thanks for this awesome answer! I've been wondering about this for quite some time, and seeing this feels like I've gained the missing pieces to some long due puzzles!
– Sudix
Nov 28 at 12:58
Thanks for this awesome answer! I've been wondering about this for quite some time, and seeing this feels like I've gained the missing pieces to some long due puzzles!
– Sudix
Nov 28 at 12:58
Thanks for this awesome answer! I've been wondering about this for quite some time, and seeing this feels like I've gained the missing pieces to some long due puzzles!
– Sudix
Nov 28 at 12:58
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%2f3016960%2ffind-a-function-f-m-that-enumerates-all-subsets-of-1-n-of-cardinalit%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