Let’s define the requirements for this algorithm. We are given two sets of integers. The idea is to check if the sets are permutations of each other. If they are, return YES; otherwise return NO.
First let’s make sure we agree with the definition of permutation. For the sets to be permutations we must have the same number of elements in both sets. Each set must have the same counts for each entry. For example if the sets are:
1 2 3 4 5 6
6 5 4 3 2 1
Then we would return YES. Both sets have the same length (six in this case) the numbers are the same on both sets, and the count of each number matches (one in this case).
7 6 5 0 9 7
7 6 1 0 9 7
Given that 5 is in the first set, but not in the second and 1 is in the second, but not in the first, these are not permutations of each other so we would return NO.
We will implement the solution in Java 8 using the Visual Studio Code IDE. Of course you can use a different IDE and a different programming language if you so desire.
# **** list the workspace **** C:\Users\John\workspace7>dir 02/25/2020 02:03 PM <DIR> . 02/25/2020 02:03 PM <DIR> .. 01/30/2020 01:32 PM <DIR> .metadata 01/31/2020 09:02 AM <DIR> .vscode 01/05/2020 07:15 AM <DIR> 3DSurfaceArea 01/06/2020 11:52 AM <DIR> AlmostSorted 02/06/2020 07:16 AM <DIR> AndProduct 01/24/2020 12:49 PM <DIR> AStarSearch 12/05/2019 01:23 PM <DIR> BiggerIsGreater 02/25/2020 02:49 PM <DIR> BinaryTreeSum 02/14/2020 03:00 PM <DIR> Cipher 12/22/2019 08:35 AM <DIR> DeterminingDNAHealth 01/08/2020 07:07 AM <DIR> EmasSupercomputer 02/12/2020 02:46 PM <DIR> FirstDuplicate 02/03/2020 09:07 AM <DIR> FlippingBits 02/20/2020 08:14 AM <DIR> FullCountingSort 02/16/2020 09:09 AM <DIR> GitHubTest 01/31/2020 02:57 PM <DIR> guava-mini 01/31/2020 10:44 AM <DIR> HelloMaven 02/17/2020 10:43 AM 2,339,925 ij.jar 02/17/2020 10:52 AM <DIR> ImageJ 02/22/2020 07:45 AM <DIR> JavaStreams 02/04/2020 02:04 PM <DIR> JumpingOnTheClouds 01/23/2020 08:05 AM <DIR> LarrysArray 12/03/2019 04:26 PM <DIR> MatrixLayerRotation 02/03/2020 10:42 AM <DIR> MiniMaxSum 01/25/2020 08:07 AM <DIR> PriorityQ 01/30/2020 01:42 PM <DIR> rtree2 02/03/2020 01:44 PM <DIR> SansaXOR 01/19/2020 09:16 AM <DIR> StacksReverseOrder 02/19/2020 08:08 AM <DIR> SumOfTwo 01/04/2020 07:51 AM <DIR> TheGridSearch 12/11/2019 10:09 AM <DIR> ToTrieOrNotToTrie # **** clone the GitHub repo **** C:\Users\John\workspace7>git clone https://github.com/JohnCanessa/IsPermutation.git Cloning into 'IsPermutation'... remote: Enumerating objects: 3, done. remote: Counting objects: 100% (3/3), done. remote: Compressing objects: 100% (2/2), done. remote: Total 3 (delta 0), reused 0 (delta 0), pack-reused 0 Unpacking objects: 100% (3/3), done. # **** list folders **** C:\Users\John\workspace7>dir 02/26/2020 10:20 AM <DIR> . 02/26/2020 10:20 AM <DIR> .. 01/30/2020 01:32 PM <DIR> .metadata 01/31/2020 09:02 AM <DIR> .vscode 01/05/2020 07:15 AM <DIR> 3DSurfaceArea 01/06/2020 11:52 AM <DIR> AlmostSorted 02/06/2020 07:16 AM <DIR> AndProduct 01/24/2020 12:49 PM <DIR> AStarSearch 12/05/2019 01:23 PM <DIR> BiggerIsGreater 02/25/2020 02:49 PM <DIR> BinaryTreeSum 02/14/2020 03:00 PM <DIR> Cipher 12/22/2019 08:35 AM <DIR> DeterminingDNAHealth 01/08/2020 07:07 AM <DIR> EmasSupercomputer 02/12/2020 02:46 PM <DIR> FirstDuplicate 02/03/2020 09:07 AM <DIR> FlippingBits 02/20/2020 08:14 AM <DIR> FullCountingSort 02/16/2020 09:09 AM <DIR> GitHubTest 01/31/2020 02:57 PM <DIR> guava-mini 01/31/2020 10:44 AM <DIR> HelloMaven 02/17/2020 10:43 AM 2,339,925 ij.jar 02/17/2020 10:52 AM <DIR> ImageJ 02/26/2020 10:20 AM <DIR> IsPermutation 02/22/2020 07:45 AM <DIR> JavaStreams 02/04/2020 02:04 PM <DIR> JumpingOnTheClouds 01/23/2020 08:05 AM <DIR> LarrysArray 12/03/2019 04:26 PM <DIR> MatrixLayerRotation 02/03/2020 10:42 AM <DIR> MiniMaxSum 01/25/2020 08:07 AM <DIR> PriorityQ 01/30/2020 01:42 PM <DIR> rtree2 02/03/2020 01:44 PM <DIR> SansaXOR 01/19/2020 09:16 AM <DIR> StacksReverseOrder 02/19/2020 08:08 AM <DIR> SumOfTwo 01/04/2020 07:51 AM <DIR> TheGridSearch 12/11/2019 10:09 AM <DIR> ToTrieOrNotToTrie # **** change directory to the folder of interest **** C:\Users\John\workspace7>cd IsPermutation # **** display the contents **** C:\Users\John\workspace7\IsPermutation>dir /A 02/26/2020 10:20 AM <DIR> . 02/26/2020 10:20 AM <DIR> .. 02/26/2020 10:20 AM <DIR> .git 02/26/2020 10:20 AM 162 README.md
I went to GitHub and created the IsPermutation repository. I just created a simple README.md file. When done will edit the README.md file and add the link to this post.
Once we had the README.md file I cloned the repository. We are now ready to open the VSCode IDE, point it to the newly created folder in my workspace and write some Java code.
1 2 3 4 5 6 7 1 4 2 7 5 3 6 isPermutationA: true main <<< a1: [1, 2, 3, 4, 5, 6, 7] main <<< a2: [1, 2, 3, 4, 5, 6, 7] isPermutationH: true main <<< a1: [1, 2, 3, 4, 5, 6, 7] main <<< a2: [1, 4, 2, 7, 5, 3, 6] isPermutationE: false main <<< a1: [1, 2, 3, 4, 5, 6, 7] main <<< a2: [1, 4, 2, 7, 5, 3, 6] 7 8 9 1 3 5 2 1 2 7 8 9 1 3 5 2 1 3 isPermutationA: false main <<< a1: [1, 1, 2, 2, 3, 5, 7, 8, 9] main <<< a2: [1, 1, 2, 3, 3, 5, 7, 8, 9] isPermutationH: false main <<< a1: [7, 8, 9, 1, 3, 5, 2, 1, 2] main <<< a2: [7, 8, 9, 1, 3, 5, 2, 1, 3] isPermutationE: false main <<< a1: [7, 8, 9, 1, 3, 5, 2, 1, 2] main <<< a2: [7, 8, 9, 1, 3, 5, 2, 1, 3] -1 -2 0 1 2 -2 -1 0 2 1 isPermutationA: true main <<< a1: [-2, -1, 0, 1, 2] main <<< a2: [-2, -1, 0, 1, 2] isPermutationH: true main <<< a1: [-1, -2, 0, 1, 2] main <<< a2: [-2, -1, 0, 2, 1] isPermutationE: false main <<< a1: [-1, -2, 0, 1, 2] main <<< a2: [-2, -1, 0, 2, 1]
We tested the solution using several examples. Some of they might be redundant. We can tell we are using three different methods.
/**
* Test scaffolding.
*
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open a buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read the first set of numbers ****
int[] arr1 = Arrays.stream(br.readLine().split(" "))
.mapToInt(Integer::parseInt)
.toArray();
// **** read the second set of numbers ****
int[] arr2 = Arrays.stream(br.readLine().split(" "))
.mapToInt(Integer::parseInt)
.toArray();
// **** make a copy of the arrays because they could have been altered by a previous method ****
int[] a1 = arr1.clone();
int[] a2 = arr2.clone();
// **** determine if the sets of integers are permutations of each other (using Arrays class) ****
System.out.println("isPermutationA: " + isPermutationA(a1, a2));
// ???? ????
System.out.println("main <<< a1: " + Arrays.toString(a1));
System.out.println("main <<< a2: " + Arrays.toString(a2));
// **** make a copy of the arrays because they could have been altered by a previous method ****
a1 = arr1.clone();
a2 = arr2.clone();
// **** determine if the sets are permutations of each other (using a hash map) ****
System.out.println("isPermutationH: " + isPermutationH(a1, a2));
// ???? ????
System.out.println("main <<< a1: " + Arrays.toString(a1));
System.out.println("main <<< a2: " + Arrays.toString(a2));
// **** make a copy of the arrays because they could have been altered by a previous method ****
a1 = arr1.clone();
a2 = arr2.clone();
// **** determine if the sets are permutations of each other (using Arrays class) ****
System.out.println("isPermutationE: " + isPermutationE(a1, a2));
// ???? ????
System.out.println("main <<< a1: " + Arrays.toString(a1));
System.out.println("main <<< a2: " + Arrays.toString(a2));
// **** close the buffered reader ****
br.close();
}
We open a buffered reader and read the values for the first array of integers. Then repeat for the second set of values.
We then call three methods. The complexity varies.
/**
* Determine if these arrays contain a permutation of each other.
* Use the arrays O(n log(n))
*/
static boolean isPermutationA(int[] arr1, int[] arr2) {
// **** check array dimensions -> O(1) ****
if (arr1.length != arr2.length) {
return false;
}
// **** sort the arrays (Quicksort: Ω(n log(n)) to O(n^2)) ****
Arrays.sort(arr1);
Arrays.sort(arr2);
// **** traverse the arrays checking if they do not match O(n) ****
for (int i = 0; i < arr1.length; i++) {
if (arr1[i] != arr2[i]) {
return false;
}
}
// **** these are permutations ****
return true;
}
For simplicity we check the sizes of the arrays. If they are different then we are done.
We sort both arrays. Note that each call is O(n log(n)). We now need to traverse the arrays stopping when array elements do not match.
/**
* Determine if these arrays contain a permutation of each other.
* Use a hash map O(n)
*/
static boolean isPermutationH(int[] arr1, int[] arr2) {
// **** check array dimensions -> O(1) ****
if (arr1.length != arr2.length) {
return false;
}
// **** hash map with key counts ****
HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
// **** load hash map from first array -> O(n) ****
for (int i = 0; i < arr1.length; i++) { if (hm.get(arr1[i]) == null) { hm.put(arr1[i], 1); } else { int value = hm.get(arr1[i]); hm.put(arr1[i], ++value); } } // **** traverse second array removing elements from the hashmap -> O(n) ****
for (int i = 0; i < arr2.length; i++) {
// **** check if key is in the hash map ****
if (hm.containsKey(arr2[i])) {
int value = hm.get(arr2[i]);
if (value == 1) {
hm.remove(arr2[i]);
} else {
value -= 1;
hm.put(arr2[i], value);
}
} else {
return false;
}
}
// **** these are permutations ****
return true;
}
In this method we do the array size check. We then push all elements of the first array into a hash map. We then remove the elements from the hash map while traversing the elements of the second array. If the values and counts do not match we do not have a permutation. This is the same concept we used in the previous method. In other words the values and the counts must match in order for the sets of integers to be permutations. Let’s keep that concept in our minds before we visit the next and final method.
/**
* Determine if these arrays contain a permutation of each other.
* Use Arrays class O(n).
* This approach may or may not work if the original set of arrays is used.
* The reason is that previous method calls may sort the arrays.
* The issue is not in this method, it is in the test scaffolding!!!
*/
static boolean isPermutationE(int[] arr1, int[] arr2) {
return Arrays.equals(arr1, arr2);
}
In this method we simply call the Arrays.equals() method. That method does exactly what we needed in O(1).
Now we should be done because the last method is as fast as we can get it. As a matter of fact, we should just call the Arrays.equals() method from main() to avoid the call to the isPermutationE() method.
Now we should commit and push our code to the GitHub repository.
# **** check status ****
C:\Users\John\workspace7\IsPermutation>git status
On branch master
Your branch is up to date with 'origin/master'.
Untracked files:
(use "git add <file>..." to include in what will be committed)
Solution.java
nothing added to commit but untracked files present (use "git add" to track)
# **** add the file to the next commit ****
C:\Users\John\workspace7\IsPermutation>git add Solution.java
# **** check status ****
C:\Users\John\workspace7\IsPermutation>git status
On branch master
Your branch is up to date with 'origin/master'.
Changes to be committed:
(use "git reset HEAD <file>..." to unstage)
new file: Solution.java
# **** commit our changes ****
C:\Users\John\workspace7\IsPermutation>git commit -m "first version of the code"
[master 432a74d] first version of the code
1 file changed, 127 insertions(+)
create mode 100644 Solution.java
# **** get status ****
C:\Users\John\workspace7\IsPermutation>git status
On branch master
Your branch is ahead of 'origin/master' by 1 commit.
(use "git push" to publish your local commits)
nothing to commit, working tree clean
# **** push changes to GitHub ****
C:\Users\John\workspace7\IsPermutation>git push origin master
Enumerating objects: 4, done.
Counting objects: 100% (4/4), done.
Delta compression using up to 8 threads
Compressing objects: 100% (3/3), done.
Writing objects: 100% (3/3), 1.31 KiB | 669.00 KiB/s, done.
Total 3 (delta 0), reused 0 (delta 0)
To https://github.com/JohnCanessa/IsPermutation.git
4f2fb4a..432a74d master -> master
# **** get status ****
C:\Users\John\workspace7\IsPermutation>git status
On branch master
Your branch is up to date with 'origin/master'.
nothing to commit, working tree clean
# **** check the log ****
C:\Users\John\workspace7\IsPermutation>git log master
commit 432a74d692db58bbec61dce1ca1f72db728af43a (HEAD -> master, origin/master, origin/HEAD)
Author: JohnCanessa <john.canessa@gmail.com>
Date: Wed Feb 26 14:26:23 2020 -0600
first version of the code
commit 4f2fb4a62fc3ee40fbd8ccf603a6254c330afed9
Author: John Canessa <8019504+JohnCanessa@users.noreply.github.com>
Date: Wed Feb 26 10:19:09 2020 -0600
Create README.md
We commit our changes and push them to GitHub. We then check that all worked by looking at the log. In addition we take a look at the GitHub repository. The Solution.java file has been uploaded.
I now need to generate the post in WordPress and post it. Then I will edit the README.md file to include the URL to the post.
The entire code for this project can be found in my GitHub repository.
UPDATE
Earlier today I decided to make a change to this post due to the fact that there were two issues. The first that was that in my code I had had accidentally changed the final return value in the isPermutationH() method from true to false. I then realized that I had done that later in my copy of the code. All was and continues to be fine.
The second item was an issue with the test scaffolding. The arrays can be altered inside the methods. This would affect the results of the isPermutationE() method. If we use the Arrays.equals() method the arrays need to be sorted. Since the arrays are not sorted, the function should properly return false. To make it work, we first need to sort both arrays. That puts us back in the same boat as the isPermutationE() method. You can experiment with the code and leave it as is or add sorting the two arrays and not cloning the arrays in the test scaffolding. It is your choice.
/**
* Returns <tt>true</tt> if the two specified arrays of ints are
* <i>equal</i> to one another. Two arrays are considered equal if both
* arrays contain the same number of elements, and all corresponding pairs
* of elements in the two arrays are equal. In other words, two arrays
* are equal if they contain the same elements in the same order. Also,
* two array references are considered equal if both are <tt>null</tt>.
*
* @param a one array to be tested for equality
* @param a2 the other array to be tested for equality
* @return <tt>true</tt> if the two arrays are equal
*/
public static boolean equals(int[] a, int[] a2) {
if (a==a2)
return true;
if (a==null || a2==null)
return false;
int length = a.length;
if (a2.length != length)
return false;
for (int i=0; i<length; i++)
if (a[i] != a2[i])
return false;
return true;
}
You can see that the arrays need to be sorted before comparing them.
# **** ****
C:\Users\John\workspace7>git clone https://github.com/JohnCanessa/IsPermutation.git
Cloning into 'IsPermutation'...
remote: Enumerating objects: 9, done.
remote: Counting objects: 100% (9/9), done.
remote: Compressing objects: 100% (8/8), done.
remote: Total 9 (delta 1), reused 3 (delta 0), pack-reused 0
Unpacking objects: 100% (9/9), done.
# **** ****
C:\Users\John\workspace7>cd IsPermutation
# **** ****
C:\Users\John\workspace7\IsPermutation>git status
On branch master
Your branch is up to date with 'origin/master'.
Changes not staged for commit:
(use "git add <file>..." to update what will be committed)
(use "git checkout -- <file>..." to discard changes in working directory)
modified: Solution.java
no changes added to commit (use "git add" and/or "git commit -a")
# **** ****
C:\Users\John\workspace7\IsPermutation>git add Solution.java
# **** ****
C:\Users\John\workspace7\IsPermutation>git status
On branch master
Your branch is up to date with 'origin/master'.
Changes to be committed:
(use "git reset HEAD <file>..." to unstage)
modified: Solution.java
# **** ****
C:\Users\John\workspace7\IsPermutation>git commit -m "reduced test cases and fix test scaffolding"
[master 3ee3b9a] reduced test cases and fix test scaffolding
1 file changed, 40 insertions(+), 15 deletions(-)
# **** ****
C:\Users\John\workspace7\IsPermutation>git push origin master
Enumerating objects: 5, done.
Counting objects: 100% (5/5), done.
Delta compression using up to 8 threads
Compressing objects: 100% (3/3), done.
Writing objects: 100% (3/3), 753 bytes | 376.00 KiB/s, done.
Total 3 (delta 1), reused 0 (delta 0)
remote: Resolving deltas: 100% (1/1), completed with 1 local object.
To https://github.com/JohnCanessa/IsPermutation.git
1a6da2a..3ee3b9a master -> master
One more thing I wanted to mention. When you are working with O() notation it is very easy to make mistakes when stating the order for one method. The following image should help:
In interested you can read more about O() notation in the “Know Thy Complexities!” web page. Albert Einstein was attributed to a quote referring that you do not need to memorize things when you can easily find them. Note that he said that when there was no internet and all references had to be from notes or books. Today you can just do a web search and have at your fingertips what ever information you need.
I deleted my local folder for the project and clone it back to make the changes. When the changes were completed I updated 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 serve of assistance 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 message using the following address: john.canessa@gmail.com. I will reply as soon as possible.
Keep on reading and experimenting. It is the best way to learn, refresh your knowledge and enhance your developer toolset!
One last thing, thanks to all 328 subscribers to my blog!!!
John
Twitter: @john_canessa