#include <iostream>
#include <string>

using namespace std;

void show(string s, int a[], int N, string t)
{ cout << s << ":";
  for (int i = 1; i <= N; i += 1)
    cout << " " << a[i];
  cout << t; }

string stndrdth(int n)
{ int d = n % 10;
  if (d == 0 || d > 3 || n / 10 == 1)
    return "th";
  else if (d == 1)
    return "st";
  else if (d == 2)
    return "nd";
  return "rd"; }

class permuter
{ protected:
    int pos[27];
    int inuse[27];
    int N;
  public:
    int perm[27];
    permuter(int n);
    bool next(); };

permuter::permuter(int n)
{ N = n;
  for (int i = 0; i < N; i += 1)
  { pos[i] = 1;
    inuse[i] = 0; }
  pos[n] = 0; }

bool permuter::next()
{ int n = N;
  for (int i = 1; i <= N; i += 1)     // this loop only needed for demonstration
    perm[i] = 0;

  cout << "\nupdate position array\n";
  /* pos array says which unused variable should go into the permutation next.
     with N = 4, pos[1] goes from 1 to 4, pos[2] from 1 to 3, pos[3] 1 to 2, pos[4] always 1
     just like counting in binary for all combinations, but columns have different maxima.
     Updating pos comes before creating the next permutation, so it must start being
     the otherwise not permissible { 1, 1, 1, 1, ...., 0 }                                   */
  while (n > 0)
  { pos[n] += 1;
    if (pos[n] <= N + 1 - n)
      break;
    pos[n] = 1;
    n -= 1;
    show("   pos", pos, N, "");
    cout << ", column " << n << " at max so resets\n"; }
  show("   pos", pos, N, "");
  cout << ", column " << n << " not at max so incremented\n";

  if (n == 0) 
  { cout << "   column 0 not 0 so finished\n";
    return false; }

  for (int i = 1; i <= N; i += 1)
    inuse[i] = 0;
  cout << "generate permutation\n";
  /*            start with empty permutation,
                for i = 1 to N inclusive
                   find pos[i]th unused variable
                   add it to the permutation
                   mark it as used                */
  for (int i = 1; i <= N; i += 1)
  { int w = pos[i];
    cout << "   i = " << i << ", w = pos[i] = pos[" << i << "] = " << w << ", find " << w << stndrdth(w) << " unused variable\n";
    for (int j = 1; j <= N; j += 1)
    { cout << "      j = " << j;           // j loop looks for wth unused variable
      show(", inuse", inuse, N, "");
      cout << ", inuse[j] = " << inuse[j] << "\n";
      if (! inuse[j])
      { w -= 1;                            // this variable is unused, but has w counted down yet?
        cout << "         w = " << w << ", noticed variable " << j << " is unused, ";
        if (w == 0)
        { cout << "and using it\n";
          perm[i] = j;
          inuse[j] = 1;
          show("           pos", pos, N, "\n");
          show("         inuse", inuse, N, "\n");
          show("          perm", perm, N, "\n");
          break; }
        else
          cout << "but w not 0 yet\n"; } } }

  cout << "finally\n";
  show("     pos", pos, N, "\n");
  show("   inuse", inuse, N, "\n");
  show("    perm", perm, N, "\n");
  return true; }

int main(int argc, char * argv[])
{ if (argc != 2)
  { cerr << "Put the number of items on the command line\n";
    exit(1); }
  const int n = atol(argv[1]);
  if (n < 0 || n > 26)
  { cerr << "Number of items limited to range 0...26\n";
    exit(1); }
  const string vars = "-abcdefghijklmnopqrstuvwxyz";
  permuter P(n);
  while (P.next())
  { for (int i = 1; i <= n; i += 1)
      cout << " " << vars[P.perm[i]];
    cout << "\n";
    string x;
    cout << "\nready: ";
    getline(cin, x); } }