Projecteuler.net – Problem 24 – Java & Python 3

http://projecteuler.net/problem=24

This problem involves lexicographic permutation. I tried my hand coding it both in Java and Python. The python code is noticeably more compact, but is also really slow. I followed an algorithm on lexicographic permutation found on Wikipedia. Generation in lexicographic order

Java


public class euler24 {	
	public static void main(String[] args) {		
		
		String a = "0123456789";

		for (int y = 0; y < 999999; y++) {
		
			int largestIndexK = -1;			// if this stays negative, we are at last permutation
			int largestIndexL = 0;
			char[] b = a.toCharArray();		// holds the next permutation as we build it
		
			// Find the largest index k such that a[k] < a[k + 1]. 
			// If no such index exists, the permutation is the last permutation.
			for (int k = 0; k < a.length() - 1; k++) {
				if (a.charAt(k) < a.charAt(k + 1)) {
					largestIndexK = k;
				}		
			}
		
			if (largestIndexK == -1) {
				System.out.println("last permutation");
				break;
			} 
		
			// Find the largest index l such that a[k] < a[l]. 
			// Since k + 1 is such an index, l is well defined and satisfies k < l.
			for (int l = 0; l < a.length(); l++) {
				if (a.charAt(largestIndexK) < a.charAt(l)) {
					largestIndexL = l;
				}
			}
						
			// Swap a[k] with a[l]. 
			b[largestIndexK] = a.charAt(largestIndexL);
			b[largestIndexL] = a.charAt(largestIndexK);
				
			// Reverse the sequence from a[k + 1] up to and including the final element a[n].
			String s = new String(b).substring(largestIndexK + 1);		
			int x = 1;
			for (int i=s.length(); i > 0; i--) {
				b[largestIndexK + x] = s.charAt(i - 1);			
				x++;			
			}
		
			a = new String(b);
		}
		System.out.println(a);
		
	}	
}

Python


a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
temp = []

for j in range(999999):

    for k in range(len(a) - 1):
        if a[k] < a[k+1]:
            largest_k = k

    for l in range(len(a)):
        if a[largest_k] < a[l]:
            largest_l = l

    temp = a[:]
    a[largest_l] = temp[largest_k]
    a[largest_k] = temp[largest_l]
    temp = a[:]

    for i in range((len(a)-1) - (largest_k + 1)):
        a[largest_k + 1 + i] = temp[len(a) - 1 - i]
        a[len(a) - 1 - i] = temp[largest_k + 1 + i]

print(a)

This entry was posted in Java, Project Euler, Python. Bookmark the permalink.

Leave a Reply