title: Porting permutation function from Python to C++
body: <p>I've been using an algorithm from a Stack Overflow answer: <a href="https://stackoverflow.com/a/9650593/4771889">https://stackoverflow.com/a/9650593/4771889</a>
  Namely the permute2() function.</p>
  
  <p>I've changed things a little for my purposes, and it generates the correct data that I need.</p>
  
  <p>Here is my Python version:</p>
  
  <pre><code>def permute(list, nextFixable, num, begin, end):
      if end == begin + 1:
          yield list
      else:
          for i in range(begin, end):
              if nextFixable[list[i]] == num[i]:
                  nextFixable[list[i]] += 1
                  num[begin], num[i] = num[i], num[begin]
                  list[begin], list[i] = list[i], list[begin]
                  for p in permute(list, nextFixable, num, begin + 1, end):
                      yield p
                  list[begin], list[i] = list[i], list[begin]
                  num[begin], num[i] = num[i], num[begin]
                  nextFixable[list[i]] -= 1
  
  
  if __name__ == "__main__":    
      list = [0, 1, 2]         
      nextFixable = {0:0, 1:0, 2:0}
      num = [0, 0, 0]
  
      for p in permute(list, nextFixable, num, 0, len(list)):
          print(p)
  </code></pre>
  
  <p>I've simplified the usage a little there to give a basic example.</p>
  
  <p>The output of this example is:</p>
  
  <pre><code>[0, 1, 2]
  [0, 2, 1]
  [1, 0, 2]
  [1, 2, 0]
  [2, 1, 0]
  [2, 0, 1]
  </code></pre>
  
  <p>Since my practical usage for this is for longer lists (not the trivial "0, 1, 2") I REALLY like the generator functionality used here (the yield statements).</p>
  
  <p>The problem is that Python is slow, and I sometimes have to wait a couple days to get a result. </p>
  
  <p>I'm not a C++ expert, but previously I've found that C++ is much faster when compared with Python.  So you can guess what I did next - I tried to rewrite this in C++ (Visual Studio 2015).</p>
  
  <p>Here's what I came up with:</p>
  
  <pre><code>#include "stdafx.h"
  
  #include &lt;iostream&gt; // for std::cout
  #include &lt;vector&gt; // for std::vector
  #include &lt;map&gt; // for std::map
  
  // https://blogs.msdn.microsoft.com/vcblog/2014/11/12/resumable-functions-in-c/
  #include &lt;experimental/generator&gt;
  using namespace std::experimental;
  using namespace std;
  
  using std::cout;
  using std::vector;
  using std::map;
  
  void print(vector&lt;unsigned short&gt; data) {
      cout &lt;&lt; "[";
      for (unsigned short i = 0; i &lt; data.size(); ++i) {
          cout &lt;&lt; (int)data[i];
          if (i &lt; data.size() - 1) {
              cout &lt;&lt; ", ";
          }
      }
      cout &lt;&lt; "]\n";
  }
  
  generator&lt;vector&lt;unsigned short&gt;&gt; permute(
      vector&lt;unsigned short&gt; list, 
      map&lt;unsigned short, unsigned short&gt; nextFixable, 
      vector&lt;unsigned short&gt; num, 
      unsigned short begin, 
      unsigned short end
  ) {
      if (end == begin + 1) {
          __yield_value list;
      }
      else {
          for (unsigned short i = begin; i &lt; end; ++i) {
              if (nextFixable[list[i]] == num[i]) {
                  nextFixable[list[i]]++;
                  swap(num[begin], num[i]);
                  swap(list[begin], list[i]);
                  for (auto p : permute(list, nextFixable, num, begin + 1, end)) {
                      __yield_value p;
                      swap(list[begin], list[i]);
                      swap(num[begin], num[i]);
                      nextFixable[list[i]]--;
                  }
              }
          }
      }
  }
  
  int main()
  {
      vector&lt;unsigned short&gt; list = { 0, 1, 2 };
      map&lt;unsigned short, unsigned short&gt; nextFixable = { {0, 0}, {1, 0}, {2, 0} };
      vector&lt;unsigned short&gt; num = { 0, 0, 0 };
  
      for (auto p : permute(list, nextFixable, num, 0, (unsigned short)list.size())) {
          print(p);
      }
  
      // Keep output window open.
      std::getchar();
      return 0;
  }
  </code></pre>
  
  <p>You can see I've referenced <a href="https://blogs.msdn.microsoft.com/vcblog/2014/11/12/resumable-functions-in-c/" rel="nofollow noreferrer">https://blogs.msdn.microsoft.com/vcblog/2014/11/12/resumable-functions-in-c/</a>
  which is what gives me the <em>__yield_value</em> feature.   (I presume this isn't portable, which is indeed going to be a problem for me eventually as I would prefer to run this in linux down the track, but for some early experiments it does the trick.)</p>
  
  <p>The code runs fine, but the output is:</p>
  
  <pre><code>[0, 1, 2]
  [0, 2, 1]
  [1, 2, 0]
  [2, 1, 0]
  </code></pre>
  
  <p>So let's compare to the Python output - it seems we have two lines missing:</p>
  
  <pre><code>[0, 1, 2] - Yes
  [0, 2, 1] - Yes
  [1, 0, 2] - Missing
  [1, 2, 0] - Yes
  [2, 1, 0] - Yes
  [2, 0, 1] - Missing
  </code></pre>
  
  <p>Usually at this point of writing a SO question, the answer jumps out at me from having to explain the problem.  In this case it hasn't.   </p>
  
  <p>It's possible I've made an incorrect language assumption, and I don't have the knowledge to correct myself.</p>
  
  <p>So to boil the question down - why is my port of the permute() function from Python to C++ not giving me the same output?</p>