学步园

  全排列的hash函数，可以利用N位变进制，一般做法是用逆序数，但时间复杂度比较大。

 

 

  设n位变进制数M，+i位逢i+1进一，显然M可表示的数的范围为[0, n!)共n!个

  要生成n个数的排列，可以先从n个数挑一个，再从剩下的n-1个数挑一下，如此反复n次。

  若最初的n个数是 0,1,2 ... n-1，第一次挑选的数是t，则可以将t放入到M的n-1位，
  若第二次挑选的数是m，则 0 <= r <= n-1 且 r != t，当r等于n-1时，
  不能将r放入到M的n-2位（可以放的最大数为n-2），但是注意到r值不可能为t，
  该情况下将它的值改为t，得到的新r值肯定小等于n-2，因而可放入到M的n-2位。

  重复上面的处理，最终得到的M值与排列是一一对应的。

 

 

#include<algorithm>
#include<cstdio>
#include<cassert>
//template<int n> 
//struct Factorial { enum { v = Factorial<n - 1>::v * n}; };
//
//template<> struct Factorial<0> { enum { v = 1}; };
//
//static const int Max_n = 12; 
//static const int factorial[Max_n] = {  //0! 1! 2! .. 11!   12!= 4.8e8
//  Factorial<0>::v, Factorial<1>::v, Factorial<2>::v,
//  Factorial<3>::v, Factorial<4>::v, Factorial<5>::v,
//  Factorial<6>::v, Factorial<7>::v, Factorial<8>::v,
//  Factorial<9>::v, Factorial<10>::v, Factorial<11>::v,  
//};

static inline bool init_factorial(int arr[], int len) 
{
  for (int i = 0, k = 1; i < len; k *= ++i) arr[i] = k; //arr[i]为i!
  return true;
}
int hash_permutation(int arr[], const int len)
{
  static const int Max_n = 12;      // 12!= 4.8e8
  static int factorial[Max_n];
  static bool tmp = init_factorial(factorial, Max_n);
  (void)tmp;
  assert(len >= 1 && len <= Max_n);
  //mapped[i]记录数i最终被映射到哪个数字，index[i]记录数i在mapped数组中的位置
  int mapped[Max_n], index[Max_n];
  for (int i = 0; i < len; ++i) mapped[i] = index[i] = i;
  
  int ret = 0;
  //设变进制数M的+i位为（i+1）进制。从高位到低位放入数字
  for (int i = len - 1; i > 0; --i) { 
    assert(arr[i] >= 0 && arr[i] < len);  
    int k = mapped[arr[i]];     //mapped数组中所有的数是0,1, 2, ... i的一个排列，
    ret += k * factorial[i];    //因而可以将数字k放到变进制数M的+i位
    
    int idx = index[i];         //将k从mapped数组中删除，删除k前                 
    mapped[idx] = k;            //先将mapped数组中最大的数（也就是i）映射到k，
    index[k] = idx;             //保证删除k后剩下的数恰好是0,1,2 ... i-1的一个排列
  }
  return ret;
}
int main()
{
  const int N = 4;
  int arr[N];
  for (int i = 0; i < N; ++i) arr[i] = i;
  int count = 0;
  do {
    printf(" %3d:  ", ++count);
    for (int i = 0; i < N; ++i) printf(" %2d", arr[i]);
    printf("  %6d\n", hash_permutation(arr, N));
  } while(std::next_permutation(arr, arr + N));
}