2
\$\begingroup\$

Previous question:

Java application for finding permutations efficiently>

I have changed quite a bit of code, and need some more reviews.

class Permutations {

    static long factorial(int num){
        long factorial = num;
        for (int forBlockvar = num; forBlockvar > 1; forBlockvar--) {
            factorial = factorial * forBlockvar;
        }
        return factorial / num;
    }

    public static void main(String[] args){
        long FactNmR;
        int n = 8;
        int num = n;
        int r = 6;
        int nMr = n - r;

        long FactN = factorial(num);

        if (nMr == 2) {
            FactNmR = 2;
        }
        else if (nMr <= 1){
            FactNmR = 1;
        }
        else if (nMr >= 2) {
            num = nMr;
            FactNmR = factorial(num);
        }

        long permutations = FactN;

        permutations = permutations / FactNmR;

        System.out.println(permutations);
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Are you sure that you pasted it well? It's not compiling, I think the return statement of the factorial method is in a wrong place. \$\endgroup\$ – palacsint Dec 21 '11 at 17:17
  • \$\begingroup\$ Yeah, I figured out that the return statement has to be outside of the brackets of the factorial method. Thank you anyways. \$\endgroup\$ – fr00ty_l00ps Dec 21 '11 at 17:19
2
\$\begingroup\$

Code comment:

static long factorial(int num){
    long factorial = num;
    for (int forBlockvar = num; forBlockvar > 1; forBlockvar--) {
        factorial = factorial * forBlockvar;
    }
    return factorial / num;
}

You are starting your factorial = num, then multiplying it by num in the first iteration of the loop, then dividing by num at the end. Starting with factorial = 1, or starting forBlockvar = num - 1 (I prefer the second) will remove the need to divide at the end. You can also return 1 if the input is less than 2.

static long factorial(int num){
    if(num < 2) {
        return 1;
    }
    long factorial = num;
    for (int forBlockvar = num - 1; forBlockvar > 1; forBlockvar--) {
        factorial = factorial * forBlockvar;
    }
    return factorial;
}

You could also implement this function recursively.

static long factorial(int num){
    if(num < 2) {
        return 1;
    }
    return num * factorial(num - 1);
}

General:

What do you mean by finding the permutations of 2 numbers? There are 2 permutations of 2 numbers [x, y]: [x, y] and [y, x].

EDIT

I think I know what you are trying to do now... You want to know how many permutations are available by selecting r objects out of a total of n.

The basic formula for that is n! / (n-r)!. However, this means calculating the factorial of (n-r) twice (in our example, we have 8*7*6*5*4*3*2*1 / 2*1, but with a lower r the overlap will be greater).

Instead of calculating the complete factorial for both numerator and denominator, there is a way to calculate the value of the numerator such that the denominator is always going to be 1. That means we eliminate one factorial calculation, and reduce the other. I'm going to let you think about it a bit before just giving the answer.

EDIT 2

Since you have figured out what I was hinting at, I'll explain it further.

n! can be represented as n*(n-1)*(n-2)*(n-3)...(2)*(1). When r is less than n and greater than 0, n! can be then be represented as n*(n-1)*(n-2)...(n-r+1)*(n-r)*(n-r-1)*(n-r-2)...(2)*(1).

(n-r)! is (n-r)*(n-r-1)*(n-r-2)...(2)*(1).

Therefore, our numerator is n*(n-1)*(n-2)...(n-r+1)*(n-r)*(n-r-1)*(n-r-2)...(2)*(1), and our denominator is (n-r)*(n-r-1)*(n-r-2)...(2)*(1). Cancelling like terms, we have n!/(n-r)! = n*(n-1)*(n-2)...(n-r+1).

static long permute(int totalItems, int numToPick) {
    long permutations = totalItems;
    while (--numToPick > 0) {
        permutations *= --totalItems;
    }
    return permutations;
}

You should ensure that 0 < numToPick <= totalItems, and totalItems > 0.

\$\endgroup\$
  • 1
    \$\begingroup\$ +1. Please note that the second (forBlockvar = num - 1) gives result 0 for input 0 (instead of 1, 0! = 1). \$\endgroup\$ – palacsint Dec 21 '11 at 18:05
  • \$\begingroup\$ @palacsint good point. Updated answer. \$\endgroup\$ – Chris Marasti-Georg Dec 21 '11 at 18:08
  • \$\begingroup\$ So, @ChrisMarasti-Georg, what you are meaning is canceling similar terms, right? \$\endgroup\$ – fr00ty_l00ps Dec 21 '11 at 19:29
  • \$\begingroup\$ @CodeAdmiral Yes, exactly. \$\endgroup\$ – Chris Marasti-Georg Dec 21 '11 at 19:36
  • \$\begingroup\$ Otay, that helps a bunch. \$\endgroup\$ – fr00ty_l00ps Dec 21 '11 at 19:38
2
\$\begingroup\$

CodeAdmiral,

I think I would find the program most readable like this:

The straightforward way:

class Permutations {

    static long factorial(int n) {
        long f = 1;
        while (n > 0) f *= n--;
        return f;
    }

    public static void main(String[] args){
        int n = 8, k = 6;
        long permutations = factorial(n) / factorial(n-k);
        System.out.println(permutations);
    }
}

Of course, this method is less efficient -- and also more prone to overflow -- than the more direct method of computing the result without wasted operations. So, a cleaner way would be like this:

The more efficient way:

class Permutations {

    static long permutations(int n, int k) {
        long p = 1;
        while (k-- > 0) p *= n--;
        return p;
    }

    public static void main(String[] args){
        int n = 8, k = 6;
        System.out.println(permutations(n, k));
    }
}

Tying it all together with a version that also computes n choose k (combinations) gives the following:

Computing both permutations and combinations:

class Permutations {

    static long factorial(int n) {
        long f = 1;
        while (n > 0) f *= n--;
        return f;
    }

    static long permutations(int n, int k) {
        long p = 1;
        while (k-- > 0) p *= n--;
        return p;
    }

    static long combinations(int n, int k) {
        long a = 1, b = 1;
        while (k > 0) { a *= n--; b *= k--; }
        return a / b;
    }

    public static void main(String[] args){
        int n = 8, k = 6;
        System.out.println(
            "Permutations: " + permutations(n, k) + " = " +
            factorial(n) / factorial(n-k));
        System.out.println(
            "Combinations: " + combinations(n, k) + " = " +
            factorial(n) / factorial(k) / factorial(n-k));
    }
}

Hope this helps!

\$\endgroup\$
  • \$\begingroup\$ Thank you! Not meaning to be a hater or anything, but for the math, I want to fully understand how to reach the solution. Your answer was amazing. +1 \$\endgroup\$ – fr00ty_l00ps Dec 22 '11 at 15:12
1
\$\begingroup\$

It looks much better and it's more easier to read than the previous post. Some small notes below.

In the factorial method you should assign 1 to the factorial variable in the first line, so you don't have to divide it with num in the last line.

    static long factorial(int num) {
        long factorial = 1;
        ...
        return factorial;
    }

It would result more simple and easier to read code and it gives proper result for 0.

After that you should reduce the if-else if-else-if structure since the factorial method now gives proper result for 2, 1 and 0.


You could call the factorial method with nMr in this part:

num = nMr;
FactNmR = factorial(num);

Based on the classic

P(n, k) = n! / ((n - k)!)

formula, I'd create one variable for only one thing with these names:

  • n, k for the input values,
  • diff would be the result of n - k,
  • dividend would be the result of n!,
  • divisor would be the result of dividend!.

The n and k are the most important. Anyway, put the formula in a comment with the used variable names. It would help the readers a lot.

\$\endgroup\$
  • \$\begingroup\$ Yes, I have since fixed this, thank you so much. +1 \$\endgroup\$ – fr00ty_l00ps Dec 21 '11 at 19:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.