Is Permutation

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

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.