[Permutation.h]

// ----------------------------------------------------------------------------
//
// Permutation Template Class Library
//
// http://www.gilgil.net
//
// Copyright (c) Gilbert Lee All rights reserved
//
// ----------------------------------------------------------------------------

#ifndef __PERMUTATION_H__
#define __PERMUTATION_H__

#include <vector>

// ----------------------------------------------------------------------------
// Permutation
// ----------------------------------------------------------------------------
template <class T>
class Permutation
{
protected:
  int factorial(int n)
  {
    int res = 1;
    for (int i = 2; i <= n; i++)
      res *= i;
    return res;
  }

public:
    std::vector<T> m_org;

public:
  Permutation()
  {
  }
  virtual ~Permutation()
  {
    m_org.clear();
  }
  int count()
  {
    return factorial((int)m_org.size());
  }
  std::vector<T> get(int index)
  {
    std::vector<T> org = m_org;
    std::vector<T> res;

    int count = (int)org.size();
    for (int n = count; n > 0; n--)
    {
      int divider = factorial(n - 1);
      int quot    = index / divider;
      int rem     = index % divider;

      res.push_back(org[quot]);
      org.erase(org.begin() + quot);
      index = rem;
    }

    return res;
  }
};

#endif // __PERMUTATION_H__

[Test]

#include <iostream>
#include "Permutation.h"

int main()
{
  Permutation<char> per;

  per.m_org.push_back('1');
  per.m_org.push_back('2');
  per.m_org.push_back('3');
  per.m_org.push_back('4');

  int count = per.count();
  for (int i = 0; i < count; i++)
  {
    std::vector<char> s = per.get(i);
    for (size_t j = 0; j < s.size(); j++)
      std::cout << s[j];
    std::cout << std::endl;
  }
}

[Result]

1234

1243

1324

1342

1423

1432

2134

2143

2314

2341

2413

2431

3124

3142

3214

3241

3412

3421

4123

4132

4213

4231

4312

4321

[Download]

Permutation.zip