Zachary Stence

A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:

012   021   102   120   201   210

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

#include<iostream>
#include<algorithm>
using namespace std;

//searches through the string and returns the index where a descending string called
//descEnd starts
int whereDesc(string s) {
  int i = s.length()-1;
  while (s[i-1] > s[i])
    i--;
  return i;
}

// returns the lexicographic permutation following s
string nextPerm(string s) {
  int d = whereDesc(s);
  if (d == s.length()-1) {
    swap(s[s.length()-1], s[s.length()-2]);
    return s;
  }
  else if (d == 0) {
    return "";
  }
  else {
    int c = d-1;
    for (int x = s.length()-1; x > c; x--) {
      if (s[x] > s[c]) {
        swap(s[x], s[c]);
        sort(s.begin()+d, s.end());
        return s;
      }
    }
  }
}

int main() {
  string s = "0123456789";
  string ans;
  
  for (int i = 0; i < 1000000; i++) {
    ans = s;
    s = nextPerm(s);
  }
  
  cout << ans << endl;
}

Answer: 2783915460