1 int a[N] //默认排序 2 void find_next() // 产生下一个字典序 3 { 4 int pos; 5 for (int i=n-1;i>=1;i--) 6 if (a[i]<a[i+1]) { 7 pos=i; 8 break; 9 } 10 11 int tmp=100; 12 int k_p; 13 // cout<<pos<<endl; 14 for (int i=n;i>=pos+1;i--) 15 if (a[i]>a[pos]) 16 if (a[i]<tmp) { 17 tmp=a[i]; 18 k_p=i; 19 } 20 21 swap (a[pos],a[k_p]); 22 reverse (a+pos+1,a+n+1); 23 return ; 24 }
我发现一个有趣的现象。。。。（暴力发现的； 233）
对于一个置换 (x1,x2,x3......xn)
定义： f(x) =a[x]
例如 【2，1，3，4】 f(2)=a[2]=1;
定义： f^2(x)=f(f(x))
那么f^n(x)=x （！ 当且仅当f^n(x)=x）置换的数目为（n-1）！
好像记得离散数学有讲，以后有空证明一下。233
暴力发现的代码
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int N=107; 4 int a[N]; 5 int n; 6 int sum; 7 bool isok () { 8 for (int i=1;i<=n;i++) { 9 int tmp=a[i]; 10 for (int j=1;j<n;j++) { 11 tmp=a[tmp]; 12 if (tmp==a[i]) return 0; 13 } 14 } 15 return 1; 16 } 17 void find_next() // ²úÉúÏÂÒ»¸ö×ÖµäÐò 18 { 19 int pos; 20 for (int i=n-1;i>=1;i--) 21 if (a[i]<a[i+1]) { 22 pos=i; 23 break; 24 } 25 int tmp=100; 26 int k_p; 27 for (int i=n;i>=pos+1;i--) 28 if (a[i]>a[pos]) 29 if (a[i]<tmp) { 30 tmp=a[i]; 31 k_p=i; 32 } 33 34 swap (a[pos],a[k_p]); 35 reverse (a+pos+1,a+n+1); 36 return ; 37 } 38 int main () 39 { 40 while (cin>>n) { 41 sum=0; int m=1; 42 for (int i=1;i<=n;i++) { a[i]=i; m*=i; } 43 if ( isok () ) sum++; 44 for (int i=1;i<m;i++) { 45 find_next(); 46 if ( isok () ) sum++; 47 } 48 cout<<sum<<endl; 49 } 50 return 0; 51 }