title: Is it possible to write a function like next_permutation but that only permutes r values, instead of n?
body: <p>std::next_permutation (and std::prev_permutation) permute all values in the range <code>[first, last)</code> given for a total of n! permutations (assuming that all elements are unique).</p>
  
  <p>is it possible to write a function like this:</p>
  
  <pre><code>template&lt;class Iter&gt;
  bool next_permutation(Iter first, Iter last, Iter choice_last);
  </code></pre>
  
  <p>That permutes the elements in the range <code>[first, last)</code> but only chooses elements in the range <code>[first, choice_last)</code>. ie we have maybe 20 elements and want to iterate through all permutations of 10 choices of them, 20 P 10 options vs 20 P 20.</p>
  
  <ul>
  <li>Iter is a random access iterator for my purposes, but if it can be implemented as a bidirectional iterator, then great!</li>
  <li>The less amount of external memory needed the better, but for my purposes it doesn't matter.</li>
  <li>The chosen elements on each iteration are input to the first elements of the sequence.</li>
  </ul>
  
  <p><em>Is such a function possible to implement? Does anyone know of any existing implementations?</em></p>
  
  <p>Here is essentially what I am doing to hack around this. Suggestions on how to improve this are also welcome.</p>
  
  <ul>
  <li>Start with a vector <code>V</code> of <code>N</code> elements of which I want to visit each permutation of <code>R</code> elements chosen from it (<code>R &lt;= N</code>).</li>
  <li>Build a vector <code>I</code> of length <code>R</code> with values <code>{ 0, 1, 2, ... R - 1 }</code> to serve as an index to the elements of <code>V</code></li>
  <li>On each iteration, build a vector <code>C</code> of length <code>R</code> with values <code>{ V[I[0]], V[I[1]], ... V[I[R - 1]] }</code></li>
  <li>Do something with the values in <code>C</code>.</li>
  <li>Apply a function to permute the elements of <code>I</code> and iterate again if it was able to.</li>
  </ul>
  
  <p>That function looks like this:</p>
  
  <pre><code>bool NextPermutationIndices(std::vector&lt;int&gt; &amp;I, int N)
  {
      const int R = I.size();
      for (int i = R - 1; ; --i) {
          if (I[i] &lt; N - R + i) {
              ++I[i];
              return true;
          }
  
          if (i == 0)
              return false;
  
          if (I[i] &gt; I[i-1] + 1) {
              ++I[i-1];
              for (int j = i; j &lt; R; ++j)
                  I[j] = I[j-1] + 1;
              return true;
          }
      }
  }
  </code></pre>
  
  <p>That function is very complicated due to all the possible off-by-one errors, as well everything using it are more complicated than is probably necessary.</p>
  
  <hr>
  
  <p><strong><em>EDIT:</em></strong></p>
  
  <p>It turns out that it was <strong>significantly</strong> easier than I had even imagined. From <a href="http://photon.poly.edu/~hbr/boost/combinations.html" rel="nofollow noreferrer">here</a>, I was able to find exact implementations of many of the exact algorithms I needed (combinations, permutations, etc.).</p>
  
  <pre><code>template&lt;class BidirectionalIterator&gt;
  bool next_partial_permutation(BidirectionalIterator first,
                                BidirectionalIterator middle,
                                BidirectionalIterator last)
  {
      std::reverse(middle, last);
      return std::next_permutation(first, last);
  }
  </code></pre>
  
  <p>Plus there is a combination algorithm there that works in a similar way. The implementation of that is much more complication though.</p>