問個數(shù)學上的問題

bruceteen

6個數(shù)字的全排列有 6! 種，每一種用一個序號替代（序號為0到719）

假設第一行置為 1 2 3 4 5 6 的可能有 M 個，則最終結(jié)果為 M * 6!

假設第二行到第六行分別是序號a b c d e的排列
若假設 a b c d e 的序號是遞增的情況下有 K 種可能，則最終結(jié)果為 K * 5! * 6!

求K只能使用暴力了，上代碼（結(jié)果寫在代碼的注釋中）

1. #include <iostream>
   
2. #include <bitset>
   
3. #include <vector>
   
4. #include <stack>
   
5. #include <algorithm>
   
6. 
   
7. template<size_t N> struct factorial // 階乘
   
8. {
   
9.     static const size_t val = N * factorial<N-1>::val;
   
10. };
    
11. template<> struct factorial<1>
    
12. {
    
13.     static const size_t val = 1;
    
14. };
    
15. template<> struct factorial<0>
    
16. {
    
17.     static const size_t val = 1;
    
18. };
    
19. 
    
20. template<size_t N> unsigned long long foo( void )
    
21. {
    
22.     const size_t NP = factorial<N>::val;
    
23. 
    
24.     std::vector< std::bitset<NP> > compatible_mash; // 不沖突的，且排在其后的排列的序號mask
    
25.     {
    
26.         struct permutation
    
27.         {
    
28.             char v[N]; // 排列
    
29. 
    
30.             permutation( const char (&v_)[N] )
    
31.             {
    
32.                 std::copy( v_+0, v_+N, v );
    
33.             }
    
34.         };
    
35.         // 全排列
    
36.         std::vector<permutation> all_permutation;
    
37.         all_permutation.reserve( NP );
    
38.         {
    
39.             char v[N];
    
40.             for( size_t i=0; i!=N; ++i )
    
41.                 v[i] = i+1;
    
42.             do {
    
43.                 all_permutation.push_back( v );
    
44.             } while( std::next_permutation(v+0,v+N) );
    
45.         }
    
46. 
    
47.         // 計算不沖突的其他排列序號
    
48.         compatible_mash.resize( NP );
    
49.         for( size_t i=0; i!=NP; ++i )
    
50.         {
    
51.             for( size_t j=i+1; j!=NP; ++j )
    
52.             {
    
53.                 bool compatible = true;
    
54.                 for( size_t k=0; k!=N; ++k )
    
55.                 {
    
56.                     if( all_permutation[i].v[k] == all_permutation[j].v[k] )
    
57.                     {
    
58.                         compatible = false;
    
59.                         break;
    
60.                     }
    
61.                 }
    
62.                 compatible_mash[i].set( j, compatible );
    
63.             }
    
64.         }
    
65.     }
    
66. 
    
67.     unsigned long long num = 0;
    
68.     std::stack< std::pair< std::bitset<NP>, size_t > > mystack;
    
69.     mystack.push( std::make_pair(compatible_mash[0],1) );
    
70.     if( mystack.top().second == N )
    
71.         ++num;
    
72.     while( !mystack.empty() )
    
73.     {
    
74.         std::pair< std::bitset<NP>, size_t > one = mystack.top();
    
75.         mystack.pop();
    
76. 
    
77.         for( size_t i=0; i!=NP; ++i )
    
78.         {
    
79.             if( one.first.test(i) )
    
80.             {
    
81.                 if( one.second == N-1 )
    
82.                 {
    
83.                     ++num;
    
84.                     if( num == 0 )
    
85.                     {
    
86.                         printf( "-------- bad --------\n" );
    
87.                     }
    
88.                     break;
    
89.                 }
    
90.                 std::bitset<NP> result = one.first & compatible_mash[i];
    
91.                 if( result.any() )
    
92.                 {
    
93.                     mystack.push( std::make_pair(result,one.second+1) );
    
94.                 }
    
95.             }
    
96.         }
    
97.     }
    
98. 
    
99.     return num * (NP/N) * NP;
    
100. }
     
101. 
     
102. using namespace std;
     
103. 
     
104. int main()
     
105. {
     
106.     cout << "f(1) = " << foo<1>() << std::endl; // 1              = 1! * 0! * 1
     
107.     cout << "f(2) = " << foo<2>() << std::endl; // 2              = 2! * 1! * 1
     
108.     cout << "f(3) = " << foo<3>() << std::endl; // 12             = 3! * 2! * 1
     
109.     cout << "f(4) = " << foo<4>() << std::endl; // 576            = 4! * 3! * 4
     
110.     cout << "f(5) = " << foo<5>() << std::endl; // 161280         = 5! * 4! * 56
     
111.     cout << "f(6) = " << foo<6>() << std::endl; // 812851200      = 6! * 5! * 9408
     
112.     cout << "f(7) = " << foo<7>() << std::endl; // 61479419904000 = 7! * 6! * 16942080
     
113. 
     
114.     return 0;
     
115. }

復制代碼

bruceteen

優(yōu)化一下代碼，可以將 f(7) 的耗時從860秒降低到53秒�？上б呀�(jīng)下班了，不想了，以后有空再研究

1. #include <iostream>
   
2. #include <bitset>
   
3. #include <vector>
   
4. #include <stack>
   
5. #include <algorithm>
   
6. #include <ctime>
   
7. 
   
8. template<size_t N> struct factorial // 階乘
   
9. {
   
10.     static const size_t val = N * factorial<N-1>::val;
    
11. };
    
12. template<> struct factorial<0>
    
13. {
    
14.     static const size_t val = 1;
    
15. };
    
16. 
    
17. template<size_t N> unsigned long long foo( void )
    
18. {
    
19.     if( N == 1 )
    
20.         return 1;
    
21. 
    
22.     const size_t NP = factorial<N>::val;
    
23. 
    
24.     std::vector< std::bitset<NP> > compatible_mash; // 不沖突的，且排在其后的排列的序號mask
    
25.     {
    
26.         struct permutation
    
27.         {
    
28.             char v[N]; // 排列
    
29. 
    
30.             permutation( const char (&v_)[N] )
    
31.             {
    
32.                 std::copy( v_+0, v_+N, v );
    
33.             }
    
34.         };
    
35.         // 全排列
    
36.         std::vector<permutation> all_permutation;
    
37.         all_permutation.reserve( NP );
    
38.         {
    
39.             char v[N];
    
40.             for( size_t i=0; i!=N; ++i )
    
41.                 v[i] = i+1;
    
42.             do {
    
43.                 all_permutation.push_back( v );
    
44.             } while( std::next_permutation(v+0,v+N) );
    
45.         }
    
46. 
    
47.         // 計算不沖突的其他排列序號
    
48.         compatible_mash.resize( NP );
    
49.         for( size_t i=0; i!=NP; ++i )
    
50.         {
    
51.             for( size_t j=i+1; j!=NP; ++j )
    
52.             {
    
53.                 bool compatible = true;
    
54.                 for( size_t k=0; k!=N; ++k )
    
55.                 {
    
56.                     if( all_permutation[i].v[k] == all_permutation[j].v[k] )
    
57.                     {
    
58.                         compatible = false;
    
59.                         break;
    
60.                     }
    
61.                 }
    
62.                 compatible_mash[i].set( j, compatible );
    
63.             }
    
64.         }
    
65.     }
    
66. 
    
67.     unsigned long long num = 0;
    
68. 
    
69.     std::stack< std::pair< std::bitset<NP>, size_t > > mystack;
    
70.     mystack.push( std::make_pair(compatible_mash[0],1) );
    
71.     while( !mystack.empty() )
    
72.     {
    
73.         std::pair< std::bitset<NP>, size_t > one = mystack.top();
    
74.         mystack.pop();
    
75. 
    
76.         for( size_t i=NP/N*one.second; i!=NP/N*one.second+NP/N; ++i )
    
77.         {
    
78.             if( one.first.test(i) )
    
79.             {
    
80.                 if( one.second == N-1 )
    
81.                 {
    
82.                     ++num;
    
83.                     if( num == 0 )
    
84.                     {
    
85.                         printf( "-------- bad --------\n" );
    
86.                     }
    
87.                     break;
    
88.                 }
    
89.                 std::bitset<NP> result = one.first & compatible_mash[i];
    
90.                 if( result.any() )
    
91.                 {
    
92.                     mystack.push( std::make_pair(result,one.second+1) );
    
93.                 }
    
94.             }
    
95.         }
    
96.     }
    
97. 
    
98.     return num * (NP/N) * NP;
    
99. }
    
100. 
     
101. using namespace std;
     
102. 
     
103. int main()
     
104. {
     
105.     time_t tb = time( NULL );
     
106.     cout << "f(1) = " << foo<1>() << std::endl; // 1              = 1! * 0! * 1
     
107.     cout << "f(2) = " << foo<2>() << std::endl; // 2              = 2! * 1! * 1
     
108.     cout << "f(3) = " << foo<3>() << std::endl; // 12             = 3! * 2! * 1
     
109.     cout << "f(4) = " << foo<4>() << std::endl; // 576            = 4! * 3! * 4
     
110.     cout << "f(5) = " << foo<5>() << std::endl; // 161280         = 5! * 4! * 56
     
111.     cout << "f(6) = " << foo<6>() << std::endl; // 812851200      = 6! * 5! * 9408
     
112.     cout << "f(7) = " << foo<7>() << std::endl; // 61479419904000 = 7! * 6! * 16942080
     
113.     time_t te = time( NULL );
     
114.     cout << "elapsed time: " << (te-tb) << endl; // 53
     
115. 
     
116.     return 0;
     
117. }

復制代碼

bruceteen

這玩意兒叫“拉丁方陣” https://zh.wikipedia.org/wiki/拉丁方陣

n    a(n)
1    1
2    2
3    12
4    576
5    161280
6    812851200
7    61479419904000
8    108776032459082956800
9    5524751496156892842531225600
10   9982437658213039871725064756920320000
11   776966836171770144107444346734230682311065600000

Forif

bruce teenager?
謝了 幫了我不少忙 十分感謝！,-)