Combinations

Hello gals and guys! It seems that during the COVID-19 pandemic time goes faster. It is Saturday and the work week went by in the blink of an eye.

This post was motivated by a HackerRank problem which I am getting ready to tackle. I decided to experiment with combinations and factorials to make sure that a brute approach to the actual problem would be futile. In my next post will tackle the basis for a better approach.

As usual let’s start with some chitchat.

Last week I watched the YouTube video “Will JavaScript Take Over the World? | Brian Kernighan and Lex Fridman”. The video is under 4 minutes. Through the years I have read articles and books by Brian Kernighan and of course have a copy of “The C Programming Language” by Brian W. Kernighan and Dennis M. Ritchie. Out of curiosity I looked up the book at amazon.com and it is currently selling for $198.89. Through the years and today I still develop large amount of software using the C language. In general the resulting executable tends to run faster than when implementing the same algorithms using higher level and object programming languages (i.e., Java and JavaScript).

Lex Fridman asks Brian what he thinks of JavaScript. If interested in the response I urge you to watch the short YouTube video. By the way, I agree with Brian’s response. I have been using JavaScript for many years. Mostly I have used it with MongoDB. In the past few weeks I have been working with React. A work of advice for those of you if you that are starting with React. Make sure you use .gitignore and add the folder node_modules to it. A simple React application using defaults tends to include a huge number of JavaScript files.

Summer is quickly coming to an end. Kids and young adults are about to start attending in-person classes at K-12, colleges and universities. I want to make it clear that the USA and all countries in the world need to find a new normal until COVID-19 is defeated. As part of that new normal we need to get back to work, school, shopping and recreation. The issue is that we all need to do so while making COVID-19 transmissions as low as possible. The problem is how to get there. My profession is to develop the best possible software solution for the problem at hand. I am not a physician or an immunologist. That said, in general I like to base my professional and personal decisions on data, experience and logic.

I am going to mention something regarding to K-12 schools. In Israel kids continued to attend classes in person until schools had to be closed due to COVID-19 cases. Later they decided to check body temperature and symptoms. That was strike two. The latest plan for the next school year approaching rapidly is to have kids K-5 to attend classes in person. The number of students per class will be reduced to 10. By having younger kids attend class in person parents are freed to go to work. The rest of the kids ages 12 to 18 will attend on-line classes from home. Suck kids do not need much supervision. The plan is not perfect, but is one of the best approaches I have read about so far. Perhaps, here in the USA we should look into such approach and perhaps with some tweaks here and there we can handle the 2020-2021 school year and one or both parents will be free to go to work in person.

On a completely separate note, you probably have read about the riots still

Schoolchildren have lunch at the Korshoejskolen Public school in Randers, Denmark. Denmark began reopening schools on April 15.

going on in some cities in our country. I live in a suburb of the Twin Cities of Minneapolis and St. Paul in Minnesota. The wave of unrest started in Minneapolis when a black male under police custody died. Without having access to the associated data, I am not able to reach a conclusion if excessive force was used by police officers. Hopefully the data during the trial will shed needed light in this case. In my opinion two things need to happen to solve (not use a palliative) the problem. One has to do with the distribution of wealth (Capitalism) and the other with rights (Democracy). I do not have enough time to discuss both topics at this time.

I live in a city in a suburb of the Twin Cities. A neighboring city in the same county is where the events I will in a short describe occurred. Note that my wife and I lived in two houses at different times in such city. A presidential candidate lived in the same city when he was the city mayor and then moved up to governor of the state.

About three days ago, a couple that we know and lives in the current neighborhood a block from us, was in their business getting it ready for reopening. The business is well known in this area. It has bowling alleys, volleyball courts and restaurant. While growing up, our sons used to bowl in that establishment. My wife and I used to stop by now and then (pre COVID-19) for burgers, fries and drinks. Across the property is a large outlet. The prices are not that great because it is within the metropolitan area of the Twin Cities. Across you can also find a bus stop with indoor and outdoor parking. New to the property there are a few other restaurants.

The events started around 03:00 PM on a workday. The husband was out fixing some plants and fence. His car was parked next to him and was with the trunk open. He had tools and materials used for the work at hand. A black male approach him walking on the sidewalk. He asked if the person working on the fence liked his car. He responded that it was fine. The person then asked for the car keys. He responded that he did not have the keys with him. The black male pulled out a gun and demanded the keys. The car owner searched is pockets and gave the key to the black male who got in the car and drove away.

The police was called. A report was written. Three days later the car was found in north Minneapolis. The ceiling was cut in order to disable the GPS tracking system. The car was in pieces. Luckily no one was hurt. Our friend had to buy a replacement car and change the locks at home. I know the couple as a monitored security home system. Most homes in our neighborhood, including ours, do.

I hope you or any other person experiences what this person did. Things could have gone differently. The police might have passed by and try to stop the criminal. This was a case of armed robbery. It can quickly escalate and get out of control. Think about it if you or your family would be in the same situation.

This past week I had trouble interacting with the mouse in a computer I purchased last year. I decided to get on Amazon.com two 3M mouse pads and two Logitech mice. One mouse it attached to a KVM so it services multiple computers. The other one is directly attached to my newest computer. All seems to be working fine at this time.

A week or so ago I received a java update. After the update a few days went by until I decided to use Java for this post. As soon as I started VSCode or attempted to run the code I would get the following message on a pop-up:

Sorry, something went wrong activating IntelliCode support for Java. 
Please check the "Language Support for Java" and "VS IntelliCode" output windows for details.

I removed Java and installed from scratch Java from Red Hat. No matter what configuration setting I changed, the problem persisted. I am sure there is a way to get VSCode working with Red Hat Java, but I decided to switch to Open JDK. You can get a copy here.

C:\Users\johnc>java -version
openjdk version "11.0.8" 2020-07-14
OpenJDK Runtime Environment AdoptOpenJDK (build 11.0.8+10)
OpenJDK 64-Bit Server VM AdoptOpenJDK (build 11.0.8+10, mixed mode)

C:\Users\johnc>javac -version
javac 11.0.8

C:\Users\johnc>echo %JAVA_HOME%
C:\Program Files\AdoptOpenJDK\jdk-11.0.8.10-hotspot\

After just leaving in my machine Open JDK 11 and making some few configuration changes, all appears to be well. From now on, on my Windows 10 computers, I will stick to Open JDK.

5
3
1 2 3 4 5
main <<<   n: 5
main <<<   r: 3
main <<< arr: [1, 2, 3, 4, 5]

main <<< 5!: 120
main <<< 3!: 6

main <<< combinations:
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5

main <<< computeCount(): 10
main <<<     getCount(): 10

The output of the code I developed uses as input the first three lines. The first represents the number of integers (n) that we have available to choose from to generate a combination. The second represents the number of elements in each combination (r) and the third line holds the elements that we will use to generate the actual combinations.

6
3
1 2 3 4 5 6

main <<< n: 6
main <<< r: 3
main <<< arr: [1, 2, 3, 4, 5, 6]

main <<< 6!: 720
main <<< 3!: 6

[1, 2, 3]
[1, 2, 4]
[1, 2, 5]
[1, 2, 6]
[1, 3, 4]
[1, 3, 5]
[1, 3, 6]
[1, 4, 5]
[1, 4, 6]
[1, 5, 6]
[2, 3, 4]
[2, 3, 5]
[2, 3, 6]
[2, 4, 5]
[2, 4, 6]
[2, 5, 6]
[3, 4, 5]
[3, 4, 6]
[3, 5, 6]
[4, 5, 6]

main <<< computeCount(): 20
main <<<     getCount(): 20

This second example uses different arguments and displays the actual combinations in a different way. I was just experimenting to see which method was more eye pleasing.

Based on the comments I have made so far, the code for this post was written in Java using the VSCode IDE on a Windows 10 machine.


    /**
     * Test scaffolding 
     */
    public static void main(String[] args) {
        
        // **** open scanner ****
        Scanner sc = new Scanner(System.in);

        // **** get the number of elements for the integer array ****
        int n = sc.nextInt();

        // ???? ????
        System.out.println("main <<<   n: " + n);

        // **** read r ****
        int r = sc.nextInt();

        // ???? ????
        System.out.println("main <<<   r: " + r);

        // **** ****
        int arr[] = new int[n];

        // **** read the values ****
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        // ???? ????
        System.out.println("main <<< arr: " + Arrays.toString(arr));
        System.out.println();

        // **** close scanner ****
        sc.close();

        // **** ****
        Factorial fact = new Factorial();
        System.out.println("main <<< " + n + "!: " + fact.factorial(n));
        System.out.println("main <<< " + r + "!: " + fact.factorial(r));
        System.out.println();

        // **** generate all combinations ****
        Combinations combinations = new Combinations(arr, n, r);

        // **** display all combinations ****
        System.out.println("main <<< combinations:\n" + combinations.toString());

        // **** ****
        System.out.println("main <<< computeCount(): " + combinations.computeCount(n, r));
        System.out.println("main <<<     getCount(): " + combinations.getCount());

    }

I tend to spend some time with the test scaffolding. As a matter of fact, this is the first part of any code I write. The scaffolding may change depending on what I wish to experiment with while developing the required code. Note that in this case, there were no requirements. I just wanted to experiment in preparation for a HackerRank problem which happens to have defined a set of requirements.

I started by opening a scanner for input. Note that the scanner is closed after we are done reading in data. We read the number of elements (n) followed by the number of elements per combination (r). We then read the actual elements. Note that we could have kept the elements as strings (not converting them to integers). If we would have followed such approach, we could use any string for elements.

There is a formula for computing the number of combinations from n elements taken r at a time.

+- -+
| n |          n!
|   | = ---------------
| r |    r! * (n - r)! 
+- -+

Basically the number of combinations is factorial of n divided by the product of factorial of r multiplied by the factorial on n minus r. By counting the combinations our code generate and then comparing with what the proper number should be based on the formula, we can verify if our code works.

/**
 * Factorial
 */
class Factorial {

    /**
     * Constructor.
     */
    Factorial() {
    }

    /**
     * Compute the factorial of the specified number.
     * Recursive call.
     */
    public long factorial(long n) {

        // **** check if we are done ****
        if (n == 1)
            return 1;

        // **** recurse ****
        return n * factorial(n - 1);
    }

    /**
     * Compute n * (n - 1) * ... * (r - 1)
     */
    public long multNtoR(long n, long r) {
        return multUtil(n, r);
    }

    /**
     * Recursive call.
     */
    private long multUtil(long n, long r) {

        // **** check if we are done ****
        if (n <= r)
            return 1;

        // **** recurse ****
        return n * multUtil(n - 1, r);
    }
}

I wrote a simple class and named it Factorial. The constructor does nothing so we could have used the default. The factorial recursive function is called with an integer value. It the checks if the value is 1 and returns. Keep in mind that a factorial is defined as the product of:  n * (n – 1) * (n – 2) * … * 2 * 1. Perhaps we should modify the check to be if (n <= 1) return 1; We could also have checked if the initial n is >= 1. I will leave such exercise for bonus points.

The multNtoR and the multUtil methods are used to simplify the generation of the number of combinations. We will see that later in the code.

/**
 * Generate combinations.
 */
public class Combinations {

    // **** ****
    private long data[];
    private long comb[][];
    private int count;
	
:::: :::: ::::

We define a class named Combinations. It was three members. The actual methods will be in separate code snippets.

    /**
     * Get the generated number of combination.
     * We keep track of this count to verify our calculation.
     */
    public int getCount() {
        return this.count;
    }

I got ambitious and decided to generate getters and setters for the class members. I then decided that it was not worth the effort. The getCount method returns the actual count of combinations generated by the code. We can then check it against our calculation.

    /**
     * Return a string with all the generated combinations.
     */
    @Override
    public String toString() {

        // **** ****
        StringBuilder sb = new StringBuilder();

        // **** ****
        for (int i = 0; i < this.comb.length; i++) {
            for (int j = 0; j < this.comb[i].length; j++)
                sb.append(this.comb[i][j] + " ");
            sb.append("\n");
        }

        // **** ****
        return sb.toString();
    }

We could just make a call to Arrays.toString or Arrays.deepToString to get a rough output of each combination, but decided to make a more elegant toString implementation which could be easily altered if we decided to make changes to the type and contents of our set of combinations held in the arr class member.

    /**
     * Computes the count of combinations.
     * 
     *                n!          n * (n - 1) ... (r - 1) * r!     n * (n - 1) ... (r - 1)
     * count = --------------- = ------------------------------ = -------------------------
     *          r! * (n - r)!           r! * (n - r)!                    (n - r)!
     */
    public int computeCount(long n, long r) {

        // **** value to return ****
        long count = 0;

        // **** ****
        Factorial fact = new Factorial();

        // **** brute force ****
        count = fact.factorial(n);
        count /= fact.factorial(r);
        count /= fact.factorial(n - r);

        // **** better approach ****
        count = fact.multNtoR(n, r);
        count /= fact.factorial(n - r);

        // **** return the computed count ****
        return (int)count;
	}

We need to compute the count of combinations. We can do it in three steps or in two. I left in the code the three and two step approach. Perhaps there is a one step approach, but I do not mean to cramp three or two lines into one.

    /**
     * Recursive method.
     */
    private void combinationUtil(int arr[], int start, int end, int index, int r) {

        // **** determine if we have a complete combination ****
        if (index == r) {

            // **** copy data to array of combinations ****
            this.comb[this.count] = Arrays.copyOf(this.data, this.data.length);

            // **** increment the count ****
            count++;

            // **** nothing else to do ****
            return;
        }

        // **** ****
        for (int i = start; (i <= end) && (end - i + 1) >= (r - index); i++) {
            this.data[index] = arr[i];
            combinationUtil(arr, i + 1, end, index + 1, r);
        }
    }

The combinationUtil method is recursive. As you can see each time we reach r we copy the data array which holds the current combination to the array that holds all the combinations. If we are not done with a combination, we enter a recursive loop until the next combination is generated. Of course we need to update the arguments. I will leave the update of the arguments as a bonus exercise. Please take the time to understand how the arguments are used. Without that understanding there is no thought behind this method.

    /**
     * Constructor
     */
    Combinations(int arr[], int n, int r) {

        // **** ****
        this.data = new long[r];
        this.count = 0;

        // **** compute the number of combinations ****
        int count = computeCount(n, r);

        // **** allocate an array to hold the combinations ****
        this.comb = new long[count][r];

        // **** generate all combinations ****
        combinationUtil(arr, 0, n - 1, 0, r);
    }

The constructor for the Combinations class initializes the class members, computes the number of combinations, allocates space in the comb array and then starts generating the actual combinations. Note that if our calculation is short the code will throw an exception. Of course we could always generate more space than needed so we should check the numbers and perhaps check the results with an external source.

10
5
1 2 3 4 5 6 7 8 9 10
main <<<   n: 10
main <<<   r: 5
main <<< arr: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

main <<< 10!: 3628800
main <<< 5!: 120

main <<< computeCount(): 252
main <<<     getCount(): 252

This is the output (without generating the actual combinations) of 10 elements taken 5 at a time. We end up with 252 combinations.

20
10
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

main <<<   n: 20
main <<<   r: 10
main <<< arr: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]       

main <<< 20!: 2432902008176640000
main <<< 10!: 3628800

main <<< computeCount(): 184756
main <<<     getCount(): 184756

We repeat the exercise with different values. Note that the number of combinations is considerably larger.

30
15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

main <<<   n: 30
main <<<   r: 15
main <<< arr: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]

main <<< 30!: -8764578968847253504
main <<< 15!: 1307674368000

Exception in thread "main" java.lang.NegativeArraySizeException: -54279
        at Combinations.<init>(Combinations.java:156)
        at Combinations.main(Combinations.java:204)

Seems like we are using relatively small numbers for n and r, but in this case our code generated an exception. We ran into an overflow.

Please note that the object of this post is not to generate combinations but to get a feeling that with relatively low number of values our results can grow quickly. We need to think about better mechanisms to validate the combinations we actually need than to generate them and then go one by one testing if they meet our needs. Such approach is typically called a brute force approach. We will get to that in the next couple posts.

By the way, please do not confuse the concept of testing combinations for some purpose with generating the number or the actual combinations. Some time ago I wrote a post in which I developed the count for large number of combinations. If interested please take a look at the Extra Long Factorials post that I wrote over three years ago.

You can also use the Combinations Calculator web site to generate the number of combinations. I used it to double check my code. For example, the number of combinations for n objects taken 15 at a time (which crashed our program) is 155117520. Of course if you use BitInteger as a data type, your factorials will work fine.

I thought I was done with this post, but I need to push the code to GitHub.

I first created an empty repository and named it JohnCanessa/Combinations. Will add a README.md file after the code is pushed into the repo.

# **** open new console on Windows 10 system ****
Microsoft Windows [Version 10.0.18363.959]
(c) 2019 Microsoft Corporation. All rights reserved.

# **** move to our workspace ****
C:\Users\johnc>cd workspace1

# **** looking for Combinations folder (found it) ****
C:\Users\johnc\workspace1>dir
07/21/2020  11:06 AM    <DIR>          .
07/21/2020  11:06 AM    <DIR>          ..
07/08/2020  07:44 AM    <DIR>          base-syntax
07/22/2020  04:36 PM    <DIR>          Combinations
07/01/2020  08:58 AM    <DIR>          HospitalsHillClimbing
07/23/2020  10:15 AM    <DIR>          KittysCalculations
06/22/2020  11:34 AM    <DIR>          learnangular5
07/09/2020  02:21 PM    <DIR>          lists-conditionals
07/02/2020  08:48 AM    <DIR>          react-complete-guide
07/22/2020  08:03 AM    <DIR>          styling-components-elements
07/11/2020  10:18 AM    <DIR>          TheMasseuse
07/22/2020  04:36 PM    <DIR>          TreePreorderTraversal

# **** move to the Combinations folder ****
C:\Users\johnc\workspace1>cd Combinations

# **** list what is in this directory ****
C:\Users\johnc\workspace1\Combinations>dir
07/22/2020  04:36 PM    <DIR>          .
07/22/2020  04:36 PM    <DIR>          ..
07/22/2020  04:36 PM    <DIR>          .vscode
07/27/2020  08:46 AM             5,389 Combinations.java

# **** initialize git ****
C:\Users\johnc\workspace1\Combinations>git init
Initialized empty Git repository in C:/Users/johnc/workspace1/Combinations/.git/

# **** check the state of affairs ****
C:\Users\johnc\workspace1\Combinations>git status
On branch master

No commits yet

Untracked files:
  (use "git add <file>..." to include in what will be committed)
        .vscode/
        Combinations.java

nothing added to commit but untracked files present (use "git add" to track)

# **** add the only file we have generated ****
C:\Users\johnc\workspace1\Combinations>git add Combinations.java

# **** check status ****
C:\Users\johnc\workspace1\Combinations>git status
On branch master

No commits yet

Changes to be committed:
  (use "git rm --cached <file>..." to unstage)
        new file:   Combinations.java

Untracked files:
  (use "git add <file>..." to include in what will be committed)
        .vscode/

# **** make our first commit ****
C:\Users\johnc\workspace1\Combinations>git commit -m "initial code"
[master (root-commit) 460b026] initial code
 1 file changed, 213 insertions(+)
 create mode 100644 Combinations.java

# **** check what is going on ****
C:\Users\johnc\workspace1\Combinations>git status
On branch master
Untracked files:
  (use "git add <file>..." to include in what will be committed)
        .vscode/

nothing added to commit but untracked files present (use "git add" to track)

# **** after creating an empty repo on GitHub
#      set it as our remote repository ****
C:\Users\johnc\workspace1\Combinations>git remote add origin https://github.com/JohnCanessa/Combinations.git

# **** check status ****
C:\Users\johnc\workspace1\Combinations>git status
On branch master
Untracked files:
  (use "git add <file>..." to include in what will be committed)
        .vscode/

nothing added to commit but untracked files present (use "git add" to track)

# **** check current remote repo ****
C:\Users\johnc\workspace1\Combinations>git remote -v
origin  https://github.com/JohnCanessa/Combinations.git (fetch)
origin  https://github.com/JohnCanessa/Combinations.git (push)

# **** push our code to the remote repo ****
C:\Users\johnc\workspace1\Combinations>git push origin master
Enumerating objects: 3, done.
Counting objects: 100% (3/3), done.
Delta compression using up to 12 threads
Compressing objects: 100% (2/2), done.
Writing objects: 100% (3/3), 1.54 KiB | 524.00 KiB/s, done.
Total 3 (delta 0), reused 0 (delta 0), pack-reused 0
To https://github.com/JohnCanessa/Combinations.git
 * [new branch]      master -> master

# **** check status ***
C:\Users\johnc\workspace1\Combinations>git status
On branch master
Untracked files:
  (use "git add <file>..." to include in what will be committed)
        .vscode/

nothing added to commit but untracked files present (use "git add" to track)

# **** check our log file ****
C:\Users\johnc\workspace1\Combinations>git log
commit 460b02622eadf9894d130a00064d435e45ab1b87 (HEAD -> master, origin/master)
Author: JohnCanessa <john.canessa@gmail.com>
Date:   Mon Jul 27 08:52:33 2020 -0500

    initial code

OK, will add the text for this post to my WordPress blog. Then I will add the link to it in the README.md file.

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 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, become proficient, refresh your knowledge and enhance your developer toolset!

One last thing, many thanks to all 1,494 subscribers to my blog!!!

Keep safe during the COVID-19 pandemic and help restart the world economy.

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.