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