title: How to use Factoradic system to get or unrank the K-th permutations WITH repeated items
body: <p>Yesterday I spent the entire day trying to solve a problem that wants me to get the k-th permutation or unrank a permutation.
  I found the best way was factoradic numbers, after hours of Googling and reading dozens of pdfs\powerpoints I finally managed to make it work perfectly both with pencil and paper and by code.</p>
  
  <p>Problem now is, when there are repeated items.</p>
  
  <p>I tried everything, but couldn't get the thing to work the way it should.The factoradic always generates much bigger rank for a permutation, can't just let it "recognize" only non-repeated permutations.</p>
  
  <p>Does anyone know a way to use the actoradic system to unrank a permutation with repeated items ? (eg: abaac) ?
  If anyone knows, please I would love a small example and intuitive explanation, that sure will benifit many others in the future.</p>
  
  <p>Thanks a lot :)</p>
  
  <p>PS: Here is my attempted C++ code that I wrote MYSELF.I know its not optmized at all, but just to show you what I got so far:
  This code will work correct if no repeated items, but will be wrong with repeated items (next_permutation is not usable of course when say, I want the 1 billionth permutation).</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;cstdio&gt;
  #include &lt;string&gt;
  #include &lt;algorithm&gt;
  
  using namespace std;
  
  int f(int n) {
      if(n&lt;2) return 1;
      return n*f(n-1);
  }
  
  int pos(string&amp; s,char&amp; c) {
      for(int i=0;i&lt;s.size();++i) {
          if(s[i]==c) return i;
      }
      return -1;
  }
  
  int main() {
      const char* perm    =    "bedac";
      string original=perm;
      sort(original.begin(),original.end());
      string s=original;
      string t=perm;
      int res=0;
      for(;s!=t &amp;&amp; next_permutation(s.begin(),s.end());++res);
      cout&lt;&lt;"real:"&lt;&lt;res&lt;&lt;endl;
      s=original;
      string n;
      while(!s.empty()) {
          int p=pos(s,t[0]);
          n+=p;
          t.erase(0,1);
          s.erase(p,1);
      }
      for(res=0;!n.empty();(res+=n[0]*f(n.size()-1)),n.erase(0,1));
      cout&lt;&lt;"factoradix:"&lt;&lt;res&lt;&lt;endl;
      return 0;
  }
  </code></pre>