Good morning! It is an average winter Sunday morning in the Twin Cities of Minneapolis and St. Paul. In about an hour my wife and I will be heading out to go shopping for groceries at the St. Paul Trader Joe’s store.
Yesterday my wife and I made a couple Neapolitan pizzas that were quite close to the original ones. I am not going to go into the ingredients at this time. The technique resides in how the pizza is cooked. In general, in the USA we do not have pizza ovens in our backyards. A pizza brick oven heats up north of 600F which is not possible to achieve in a regular home oven. In addition, the initial transfer of heat, due to the size of the oven, is not possible. So, by reading and watching videos, we ended up with the following set of steps:
1. Preheat oven to 550F (takes about 15 minutes in our convection Thermador oven) 2. Add some olive oil to a large (14 to 15 inch cast iron pan) 3. Carefully place the dough on the cast iron pan 4. Turn on your largest gas burner on your range (we have a Viking with high heating capacity) 5. The first pizza will take about 7 minutes to cook (the following ones will take about 5) 6. Carefully move the pan into the oven 7. Finish cooking the pizza in about 7 to 8 minutes 8. Carefully remove the pan from the oven 9. Move the pizza from the pan to a tray and let it rest for 5 minutes (if you can) 10. Use a cutting wheel to cut 6 slices 11. Enjoy!!!
If you try this cooking technique, please share the experience with others. In general I enjoy reading and experimenting, not only with technical topics and subjects, but in general to improve on life.
I am ready to continue with introductory comments, but time flies when you are having fun and I would like to finish this post in the next 30 minutes if possible.
The main subject for this post is LeetCode 31 Next Permutation problem. If interested take a look at the site and decide if you wish to try it.
Implement next permutation, which rearranges numbers into the "lexicographically next greater permutation" of numbers. If such an arrangement is not possible, it must rearrange it as the lowest possible order (i.e., sorted in ascending order). The replacement must be in place and use only constant extra memory. Constraints: 1 <= nums.length <= 100 0 <= nums[i] <= 100
First, we need to make sure to understand the definition of a lexicographically ordered set of permutations is. There are different ways to generate permutations, but not all result in an ordered set. For this problem we do not need to generate the entire set of permutations for the associated number of elements, look up the one we are given and then select the next one. We could but that will be a O(n^2) process which would probably not be accepted as a solution.
What we will require is to look at the pattern, and figure out how to generate the next permutation.
I spent some time with a pen and paper. I tried some code but needed a hint. I found the following article in Wikipedia. After reading it several times and writing the associated code, I cleaned it and was able to get a solution that was accepted.
The signature for the function / method we need to generate is:
public void nextPermutation(int[] nums) {
}
I will be using Java on a Windows 10 computer and the VSCode IDE to solve this problem. The simplest way is to attempt it in the IDE provided by LeetCode. Since I am using a machine at home, I will have to develop a test scaffolding. The output of several test cases follows:
1,2,3 main <<< nums: [1, 2, 3] main <<< output: [1, 3, 2] 3,2,1 main <<< nums: [3, 2, 1] main <<< output: [1, 2, 3] 1,1,5 main <<< nums: [1, 1, 5] main <<< output: [1, 5, 1] 1,5,1 main <<< nums: [1, 5, 1] main <<< output: [5, 1, 1] 4,3,2,1 main <<< nums: [4, 3, 2, 1] main <<< output: [1, 2, 3, 4] 1,2,5,8,7 main <<< nums: [1, 2, 5, 8, 7] main <<< output: [1, 2, 7, 5, 8] 15,8,4,7,6,5,3,1 main <<< nums: [15, 8, 4, 7, 6, 5, 3, 1] main <<< output: [15, 8, 5, 1, 3, 4, 6, 7] 1,2,3,4 main <<< nums: [1, 2, 3, 4] main <<< output: [1, 2, 4, 3] 1,3,2 main <<< nums: [1, 3, 2] main <<< output: [2, 1, 3] 2,3,1,3,3 main <<< nums: [2, 3, 1, 3, 3] main <<< output: [2, 3, 3, 1, 3]
Each test case takes three lines. The input line is read. The values are placed in an array and it is displayed as a sanity check. They seem to match in all the cases. The test code seems to call the function / method to generate the solution. The resulting array is then displayed.
The first three or four test cases provided by LeetCode are included. The others were generated by me or copied from the LeetCode site from a failed attempt.
The first test case represents the first lexicographical permutation of three numbers with the specified values. It needs to generate the second permutation. The code seems to return the correct result.
In the second test case, the last lexicographical permutation of three numbers with the specified values is presented. Our answer need to be the first permutation which is the input value for the first test case.
I was not able to finish this post on Sunday. The clock indicated 09:25 AM and that is the time we need to start leaving home in order to be on our way to Trader Joe’s by 09:30 AM. Today is early Monday morning and I am ready to finish the post.
/**
* Test scafolding.
* !!! NOT PART OF THE SOLUTION !!!
*
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// ???? test reverse function / method ????
// int[] arr = new int[]{1,2,3,4};
// System.out.println("main <<< arr: " + Arrays.toString(arr));
// reverse(arr, 3, arr.length - 1);
// System.out.println("main <<< arr: " + Arrays.toString(arr));
// System.exit(-1);
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read data and populate nums[] ****
int[] nums = Arrays.stream(br.readLine().trim().split(","))
.mapToInt(Integer::parseInt)
.toArray();
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< nums: " + Arrays.toString(nums));
// ???? ????
// int[] arr = nums.clone();
// heapPermutations(arr, arr.length, arr.length);
// permute(arr, 0, arr.length - 1);
// System.out.println("main <<< arr: " + Arrays.toString(arr));
// System.out.println("main <<< nums: " + Arrays.toString(nums));
// **** generate next permutation ****
nextPermutation(nums);
// **** display result ****
System.out.println("main <<< output: " + Arrays.toString(nums));
}
Since I develop the code for the solution on my computer, I need to generate some test code that will read the input line, prepare the argument(s) for the function / method in question, invoke the function / method and display the results. Such code is NOT PART OF THE SOLUTION!
I really liked this problem. I knew that I needed at least two separate utility functions / methods. One is intended to reverse the contents of a set of elements in an array (e.g., 1 , 2, 3 to 3, 2, 1). The test code has been commented out. The function / method of interest is reverse() which we will look at shortly. The other function / method is swap() which will swap two locations in the specified array.
Back to the code, we read the input line and generate an int[] with the input integer values. We display the array to verify all is well so far.
The next set of lines generates permutations using different approaches. None of this function / methods produces an ordered list of permutations. At this time I will leave that as a bonus task. You can always sort the array in a lexicographical order.
We make a call to the nextPermutation() method which should generate the solution in the same nums[] array. The contents of the nums[] array is then displayed.
/**
* Rearranges the numbers in nums[] into the "lexicographically next greater
* permutation" of such numbers.
*
* The following algorithm generates the next permutation lexicographically
* after a given permutation. It changes the given permutation in-place.
*
* Permutation
* https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order
*
* 1) Find the largest index k such that a[k] < a[k + 1].
* If no such index exists, the permutation is the last permutation.
* 2) Find the largest index l greater than k such that a[k] < a[l].
* 3) Swap the value of a[k] with that of a[l].
* 4) Reverse the sequence from a[k + 1] up to and including the final element a[n].
*
* Better description for the same approach:
*
* 1) from right to left find adjacent values such that nums[i] < nums[i + 1]
* 2) from right to left find j such that nums[j] <= nums[i]
* 3) swap nums[i] with nums[j]
* 4) reverse nums [i + 1 : n - 1]
*
* Runtime: 0 ms, faster than 100.00% of Java online submissions.
* Memory Usage: 38.9 MB, less than 85.80% of Java online submissions.
*/
static void nextPermutation(int[] nums) {
// **** sanity check ****
if (nums.length <= 1)
return;
// **** initialization ****
int n = nums.length;
int i = n - 2;
int j = n - 1;
// **** 1) from right to left find adjacent values such that nums[i] < nums[i + 1] ****
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
// **** check if not not the largest permutation ****
if (i >= 0) {
// **** 2) from right to left find j such that nums[j] <= nums[i]
while (j > i && nums[j] <= nums[i])
j--;
// **** 3) swap nums[i] with nums[j] ****
swap(nums, i, j);
}
// **** 4) reverse nums [i + 1 : n - 1] ****
reverse(nums, i + 1, n - 1);
}
As I mentioned earlier, after spending some time with the problem, I needed a hint. I found the Wikipedia article that not only describes what a lexicographically next greater permutation is, but provides the steps to follow to generate one. That is condensed in the comments section of this function.
I found it very confusing. After additional coding and searching I wrote the same steps that seem to be simpler to understand. You be the judge.
We start by performing a sanity check. The initialization step follows. Please note that the simplicity is the result of multiple passes.
The first step is to traverse the array from right to left until the condition is found. We are looking for the lowest digit that we can swap. The result indicates the “next permutation”.
Note that if we cannot find such condition, we have the highest possible permutation. We need to just reverse it which will produce the lowest permutation of the set of numbers.
If we find a suitable index (i >= 0), we perform step 2. This is the other number we need to swap in the array. We swap the nums[i] with the nums[j] values and we are ready to perform the fourth step.
We need to reverse the rest of the values in order to order them in the proper sequence.
The algorithm works. Just take a few moments to try different examples with three, four and perhaps five elements. All should fall in place.
/**
* Swap array values.
* Time complexity: O(2)
*/
static void swap(int[] nums, int i, int j) {
// **** sanity checks ****
if (i < 0 || j < 0)
return;
if (i >= nums.length || j >= nums.length)
return;
// **** swap array values ****
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
This is the implementatio0n of the swap() function / method. Given that we are using it in a very controlled scenario we could have eliminated the sanity checks. In production code, you cannot second guess how the function would be called. It is much better to be safe than sorry.
/**
* Reverse nums[] in the specified range.
* Time complexity: O(n / 2)
*/
static void reverse(int[] nums, int l, int r) {
// **** sanity checks ****
if (i < 0 || j < 0)
return;
if (i >= nums.length || j >= nums.length)
return;
// **** initialization ***
//int tmp;
// **** swap end elements (left -> mid <- right) ****
while (l < r) {
// **** swap elements ****
//tmp = nums[l];
//nums[l] = nums[r];
//nums[r] = tmp;
swap(tmp, l, r);
// **** update indices ****
l++;
r--;
}
}
The reverse() function / method (OK, I am tired of writing function / method. From now on I will refer to such pieces of code as methods in this and in future posts. I fully understand the differences but such is life) is used to reverse a range of entries in the specified array indicated by the I and j arguments.
After the sanity checks (which are not needed in this case) we initialize the tmp variable which will be used to swap two elements in the array. We should have use the swap() method instead. Using an existing method that hopefully has been fully tested is safer than reinventing the wheel. Of course, to check performance, you might try writing the three (actually four) lines of code we used in the swap() method.
We also need to love the right index to the left index to the right and the right index to the left.
As you can see this is a nice problem that ends with is solved using elegant code. I really enjoyed working on this problem. I learn a thing or two.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to help out with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private e-mail message. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.
One last thing, many thanks to all 6,121 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy. I believe we can all see the light at the end of the tunnel.
Regards;
John
john.canessa@gmail.com