어떤 대상을 순서에 따라 배열한 것을 순열이라고 합니다. 예를 들어 3124는 숫자 1, 2, 3, 4로 만들 수 있는 순열 중 하나입니다.
이렇게 만들 수 있는 모든 순열을 숫자나 문자 순으로 늘어놓은 것을 사전식(lexicographic) 순서라고 합니다.
0, 1, 2로 만들 수 있는 사전식 순열은 다음과 같습니다.012 021 102 120 201 210
0, 1, 2, 3, 4, 5, 6, 7, 8, 9로 만들 수 있는 사전식 순열에서 1,000,000번째는 무엇입니까?
f는 팩토리얼, g는 자리수 구하기
내가짰지만 좀 복잡한 듯…
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
#!/usr/bin/env perl use 5.010; use strict; use warnings; my @a = (0..9); my $b = 0; my $r = ""; $r .= g() for (0..9); say $r; sub g { for my $i (0..$#a+1) { if (($b + f($#a+1)*$i / ($#a+1)) <= 1000000 and $b + f($#a+1)*($i+1) / ($#a+1) >= 1000000) { $b = $b + f($#a+1)*$i / ($#a+1); my $r = $a[$i]; splice (@a, $i, 1); return $r; } } } sub f { my $r = 1; for my $i (1..$_[0]) { $r *= $i; } return $r; } |