Find a function $f_m $ that enumerates all subsets of ${1,..,n}$ of cardinality $m$ in ascending order












1














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$.










share|cite|improve this question





























    1














    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$.










    share|cite|improve this question



























      1












      1








      1


      0





      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$.










      share|cite|improve this question















      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






      share|cite|improve this question















      share|cite|improve this question













      share|cite|improve this question




      share|cite|improve this question








      edited Nov 28 at 11:37

























      asked Nov 28 at 9:40









      Sudix

      8781316




      8781316






















          1 Answer
          1






          active

          oldest

          votes


















          2














          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.






          share|cite|improve this answer





















          • 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











          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
          });


          }
          });














          draft saved

          draft discarded


















          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









          2














          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.






          share|cite|improve this answer





















          • 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
















          2














          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.






          share|cite|improve this answer





















          • 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














          2












          2








          2






          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.






          share|cite|improve this answer












          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.







          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          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


















          • 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


















          draft saved

          draft discarded




















































          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.




          draft saved


          draft discarded














          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





















































          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







          Popular posts from this blog

          Wiesbaden

          Marschland

          Dieringhausen