Project Euler 24
順列とはモノの順番付きの並びのことである. たとえば, 3124は数1, 2, 3, 4の一つの順列である. すべての順列を数の大小でまたは辞書式に並べたものを辞書順と呼ぶ. 0と1と2の順列を辞書順に並べると 012 021 102 120 201 210 になる. 0,1,2,3,4,5,6,7,8,9からなる順列を辞書式に並べたときの100万番目を答えよ。
Mathematica
Permutations[{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}][[1000000]]
この問題も Mathematica の関数とメモリを使った卑怯な解き方です。
C/C++
#include <iostream> using namespace std; void numInit(); int factorial(int); int trueAt(int); const int NUMSIZE = 10; bool num[NUMSIZE]; int main(){ int i = 1000000; numInit(); for(int j=NUMSIZE-1 ; j>=0 ; j--){ int k = (int)(((i-1)%factorial(j+1))/factorial(j)); int p = trueAt(k); cout << p; num[p] = false; } int end; cin >> end; return 0; } // num初期化 void numInit(){ for(int i=0 ; i<NUMSIZE ; i++){ num[i] = true; } } // nの階乗を返す int factorial(int n){ if(n==0 || n==1) return 1; int k=1; for(int i=2 ; i<=n ; i++){ k*=i; } return k; } // num中でn番目のtrueの位置を返す int trueAt(int n){ int pos=0, tgt=0; while(1){ if(num[pos]){ if(n==tgt) break; tgt++; } if(n==tgt-1) break; pos++; } return pos; }
何だこの暗号。
1から探して行く方法ではないやり方でできたのがよかった。けど、1ヶ月後に見て挙動をしっかり把握出来ている自信がゼロ。