일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 | 31 |
Tags
- 삼각함수의그래프
- project euler
- 몬테카를로
- 수학탐구
- 큰수의법칙
- python
- 하합
- 제곱근의뜻
- 파이썬
- 리만합
- 시뮬레이션
- 지오지브라
- java
- 알지오매스
- 이항분포
- 프로젝트 오일러
- 상합
- 확률실험
- 정오각형
- counting sunday
- algeomath
- 오일러
- Geogebra
- 작도
- 재귀함수
- 피타고라스 정리
- 구분구적법
- 프랙탈
- 큰 수의 법칙
- 블록코딩
Archives
- Today
- Total
이경수 선생님의 수학실험실
Problem 24(Lexicographic permutations) 본문
Problem 24(Lexicographic permutations)
A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:
012 021 102 120 201 210
What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?
In Python:
import time
def swap(s, i, j):
nList = list(s)
nList[j], nList[i] = nList[i], nList[j]
return ''.join(nList)
def undersort(s, i):
nList = list(s)
nList1 = nList[0: i]
nList2 = nList[i:]
nList2.sort()
nList = nList1 + nList2
return ''.join(nList)
def lexico(nStr):
maxIdx = len(nStr) - 1
for i in range(maxIdx - 1, -1, -1):
for j in range(maxIdx, i, -1):
if int(nStr[i]) < int(nStr[j]):
nStr = swap(nStr, i, j)
nStr = undersort(nStr, i + 1)
return nStr
startTime = time.time()
nStr = '0123456789'
for i in range(pow(10, 6) - 1):
nStr = lexico(nStr)
print(nStr)
print(time.time() - startTime, "seconds")
Run time: 4.184289216995239 seconds
In Java:
//Euler24 Lexicographic permutations
package project_euler21_30;
import java.util.ArrayList;
import java.util.List;
import java.util.Collections;
public class Euler24 {
public static String swap(String s, int i, int j) {
String nStr = "";
String data[];
ArrayList<String> dataList = new ArrayList<String>();
data = s.split("");
for (int k = 0; k < data.length; k++) {
dataList.add(data[k]);
}
Collections.swap(dataList, i, j);
for (int k = 0; k < dataList.size(); k++) {
nStr += dataList.get(k);
}
return nStr;
}
public static String undersort(String s, int i) {
String nStr = "";
String data[];
ArrayList<String> dataList = new ArrayList<String>();
data = s.split("");
for (int k = 0; k < data.length; k++) {
dataList.add(data[k]);
}
List<String> dataList1 = dataList.subList(0, i);
List<String> dataList2 = dataList.subList(i, dataList.size());
Collections.sort(dataList2);
dataList1.addAll(dataList2);
for (int k = 0; k < dataList1.size(); k++) {
nStr += dataList1.get(k);
}
return nStr;
}
public static String lexico(String s) {
String nStr ="";
int maxIdx = s.length() - 1;
for (int i = maxIdx - 1; i > -1; i--) {
for (int j = maxIdx; j > i; j--) {
if (Integer.parseInt("" + s.charAt(i)) < Integer.parseInt("" + s.charAt(j))) {
nStr = swap(s, i, j);
nStr = undersort(nStr, i + 1);
return nStr;
}
}
}
return nStr;
}
public static void main(String[] args) {
long startTime = System.currentTimeMillis();
String nStr = "0123456789";
for (int i = 0; i < Math.pow(10, 6) - 1; i++) {
nStr = lexico(nStr);
}
System.out.println(nStr);
long endTime = System.currentTimeMillis();
System.out.println((double)(endTime - startTime)/(double)1000 + "seconds");
}
}
Run time: 3.929seconds
Solution: 2783915460
'Project Euler' 카테고리의 다른 글
Problem 26(Reciprocal cycles) (0) | 2019.05.11 |
---|---|
Problem 25(1000-digit Fibonacci number) (0) | 2019.05.11 |
Problem 23(Non-abundant sums) (0) | 2019.04.16 |
Problem 22(Names scores) (0) | 2019.04.14 |
Problem 21(Amicable numbers) (0) | 2019.04.14 |
Comments