{"id":487,"date":"2012-07-31T10:36:11","date_gmt":"2012-07-31T14:36:11","guid":{"rendered":"http:\/\/www.joshho.com\/blog\/?p=487"},"modified":"2012-09-07T16:15:20","modified_gmt":"2012-09-07T20:15:20","slug":"project-euler-problem-24","status":"publish","type":"post","link":"https:\/\/www.joshho.com\/blog\/2012\/07\/31\/project-euler-problem-24\/","title":{"rendered":"Project Euler &#8211; Problem 24"},"content":{"rendered":"<p>Problem 24: What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?<br \/>\n<!--more--><br \/>\n<a href=\"http:\/\/en.wikipedia.org\/wiki\/Permutation#Generation_in_lexicographic_order\" target=\"_blank\">Wikipedia: Permutation &#8211; Generation_in_lexicographic_order<\/a><br \/>\n<code><\/p>\n<pre lang='java'>\r\nclass runner\r\n{\r\n\tprivate static void swap(char[] arr, int l, int k){\r\n\t\tchar tmp = arr[l];\r\n\t\tarr[l]=arr[k];\r\n\t\tarr[k] = tmp;\r\n\t}\r\n\t\r\n\tpublic static void permutate(char[] arr){\r\n\t\tint k = -1;\r\n\t\tfor(int i=0;i<arr.length-1;i++){\r\n\t\t\tif(arr[i] < arr[i+1] &#038;&#038; ( k == -1 || k < i )) k = i;\/\/(arr[k] < arr[i])\r\n\t\t}\r\n\t\tif(k == -1) return;\r\n\t\tint l = k+1;\r\n\t\tfor(int i=k;i<arr.length;i++){\r\n\t\t\tif(arr[k] < arr[i]){\r\n\t\t\t\tif(arr[l] > arr[i]) l=i;\r\n\t\t\t}\r\n\t\t}\r\n\t\tswap(arr,l,k);\r\n\t\t\r\n\t\tint diff = arr.length - (k+1);\r\n\t\tfor(int i=0; i<diff\/2;i++){\r\n\t\t\tswap(arr,i+(k+1),arr.length-i-1);\r\n\r\n\t\t}\r\n\t}\r\n\t\r\n\tpublic static void main (String[] args) throws java.lang.Exception\r\n\t{\r\n\t\tlong time = System.currentTimeMillis();\r\n\t\tchar[] input = {'0','1','2','3','4','5','6','7','8','9'};\r\n\t\t\r\n\t\tfor(int i=1;i<1000000;i++){ \/\/starts at 1 as input is the first permu\r\n\t\t\tpermutate(input);\r\n\/*\t\t\tfor(char z: input){\r\n\t\t\t\tSystem.out.print(z);\r\n\t\t\t}System.out.println(\" |\");*\/\r\n\t\t}\r\n\t\t\r\n\t\tfor(char i: input){\r\n\t\t\tSystem.out.print(i);\r\n\t\t}System.out.println();\r\n\t\r\n\t\tSystem.out.println(\"time: \"+(System.currentTimeMillis() - time));\r\n\t}\r\n}\r\n<\/pre>\n<p><\/code><\/p>\n<p>Another solution... just dawned on me, after others said there was another way.<br \/>\n<code><\/p>\n<pre lang=\"java\">\r\nimport java.util.HashMap;\r\nimport java.util.Vector;\r\n\r\nclass Factorial{\r\n\tprivate HashMap<Integer, Integer> store = new HashMap<Integer, Integer>();\r\n\tint getFactorial(int n)\r\n\t{\r\n\t\tint result = 1;\r\n\t\tif(n<=0){return result;}\r\n\t\tif(store.containsKey(n)) result = store.get(n);\r\n\t\telse result = getFactorial(n-1);\r\n\t\tstore.put(n, result);\r\n\t\treturn n*result;\r\n\t}\r\n}\r\n\r\nclass runner\r\n{\r\n\t@SuppressWarnings(\"serial\")\r\n\tpublic static void main (String[] args) throws java.lang.Exception\r\n\t{\r\n\t\tlong time = System.currentTimeMillis();\r\n\r\n\t\tint max = 1000000;\r\n\t\tVector<Integer> arr = new Vector<Integer>(){\r\n\t\t\t{\r\n\t\t\t\tadd(0);add(1);add(2);add(3);add(4);add(5);add(6);add(7);add(8);add(9);\r\n\t\t\t}\r\n\t\t};\r\n\t\tVector<Integer> output = new Vector<Integer>();\r\n\t\tFactorial obj = new Factorial();\r\n\t\t\r\n\t\tfor(int i = arr.size(); i>0; i--){\r\n\t\t\tlong split = (long)(obj.getFactorial(i)) \/ (i);\r\n\t\t\tlong j = 0; int count = -1;\r\n\r\n\t\t\tdo{\r\n\t\t\t\tj += split;\r\n\t\t\t\tcount ++;\r\n\t\t\t}while( j < max);\r\n\t\t\t\r\n\t\t\tmax -= split*(count);\r\n\t\t\toutput.add(arr.remove(count));\r\n\t\t}\r\n\t\tSystem.out.println(output.toString());\r\n\t\t\r\n\t\tSystem.out.println(\"time: \"+(System.currentTimeMillis() - time));\r\n\t}\r\n}\r\n<\/pre>\n<p><\/code><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem 24: What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[56],"tags":[],"_links":{"self":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts\/487"}],"collection":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/comments?post=487"}],"version-history":[{"count":0,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts\/487\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/media?parent=487"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/categories?post=487"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/tags?post=487"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}