#include <functional> // std::function
#include <memory> // std::shared_ptr
#include <vector>
#include <iostream>
using namespace std;
// n 取 r 做排列
// 採用逆時旋轉排列法
// 必須 n >= r
class Permutation_nPr
{
// 回報結果
function<void(const shared_ptr<vector<unsigned char> > &, size_t)> m_Report;
// 放置要排列的數字
shared_ptr <vector<unsigned char> > m_Digital_Array;
// 要做排列的數目值
size_t m_r;
void v(size_t n, size_t r)
{
size_t i = n + 1;
while (i--)
{
if (r == 0)
m_Report(m_Digital_Array, m_r);
else
v(n - 1, r - 1);
unsigned char tmp = m_Digital_Array->at(n);
for (size_t j = n; j > 0; --j)
m_Digital_Array->at(j) = m_Digital_Array->at(j - 1);
m_Digital_Array->at(0) = tmp;
}
}
public:
Permutation_nPr(
const function<void(const shared_ptr<vector<unsigned char> > &, size_t)>
&Receive
)
:m_Report(Receive)
{}
void nPr(size_t n, size_t r)
{
m_r = r;
m_Digital_Array =
shared_ptr<vector<unsigned char> >(new vector<unsigned char>(n));
size_t i = n;
while (i--)
{
m_Digital_Array->at(i) = i;
}
v(n - 1, r - 1);
}
};
int N = 1;
void Show(const shared_ptr<vector<unsigned char> > &Digital_Array, size_t r)
{
cout << N << ":\t";
for (size_t i = Digital_Array->size() - 1; r > 0; --i, --r)
cout << (int)Digital_Array->at(i) << ' ';
cout << endl;
++N;
}
int main()
{
Permutation_nPr P(Show);
cout << "4P3 排列:" << endl;
N = 1;
P.nPr(4, 3);
return 0;
}