bash script to find total number of permuations

Question

I am writing a bash script to find the total no. of permutations (used in mathematics) whose formula is n!/(n-r)!, but the script that I used gives different output value than the expected one. Anyone to figure out my mistake? I am newbie in bash scripting.

echo "Enter no. to find factorial"
read num 
fact=1
while [ $num -gt 0 ]
do
fact=`expr $num \* $fact`
num=`expr $num - 1`
done

echo "Enter value for r"
read num1
num2=$((num-num1))

fact1=1
while [ $num2 -gt 0 ]
 do
fact1=`expr $num2 \* $fact1`
num2=`expr $num2 - 1`
done

echo "Total no. of permutations $((fact/fact1)) "

Answer 1

There is no need to call another program (expr), since Bash is perfectly able to compute integer arithmetics (see ARITHMETIC EVALUATION in man bash). The following snippet might help you:

fact=1     
for ((i=4; i>1; i--)) do
  ((fact*=i))
done
echo $fact

#echo $((4+4))  # Arithmetic Expansion might also be useful

Output

24

Answer 2

I think OP's code and @bgoldst solution can be improved because both will fail when n and r are big due to that the key of the algorithm is the use of factorial, and this, as you already should know, produces huge integer numbers which bash cannot handle. bash arithmetic is limited to 32-bit signed integers.

For instance, let's say n is 49 and r is 2, the @bgoldst's script shows -6 -- the right value is 2352 (49*48). When n is 32 and r is 2, the output is 0 -- the right value is 992 (32*31).

@bgoldst improves the OP's code but he adds no intelligence to the algorithm -- Have you forgotten we are programmers?

Mathematical background

The expression n!/(n-r)! can be re-written this way

  n!      n·(n-1)·(n-2)···(n-r+1) · (n-r)!
------ = --------------------------------- = n·(n-1)·(n-2)···(n-r+1)
(n-r)!              (n-r)!

Pay attention to that the r value is actually the number of factors in the ultimate multiplication.

For example, when n=49 and r=2

   49!       49!      49·48·47!
--------- = ----- = ------------- = 49·48 = 2352
 (49-2)!     47!         47!

My solution

My solution uses the bc tool in order to bypass the constrains of 32-bit fixed-point arithmetic and seq tool to remove any shell loop.

Provided that the n and r values are well formed positive integers:

# Check if n>=r
if   [ "$( bc <<<$n'>='$r 2>/dev/null)" != 1 ]
then
     echo "r cannot be bigger than n"
     exit 1
fi

PERMUTATIONS=$( seq -s '*' $((n-r+1)) "$n" | bc )

echo "Total no. of permutations for n=$n and r=$r is ${PERMUTATIONS:-1}"

notes:

• bc <<<$n'>='$r 2>/dev/null prints either 0 or 1, no matter how big n and r are. In the case when n or r are not well formed integer values, bc command will claim, report an error message and print nothing (NULL string). Pay attention to the fact that, if my code has to admit huge integers which cannot be properly handled by bash, then it cannot contain bash usual arithmetic comparisons such as [ "$n" -ge "$r" ], [[ "$n" >= "$r" ]] or (( n >= r )). That is why bc is used here too.

• seq -s '*' would produce, for instance, 4*5*6*7 which is piped to the bc command.

• When r is zero, no matter n is, the seq command line produces nothing (empty). Therefore, PERMUTATIONS="${PERMUTATIONS:-1}" is necessary to provide a default value (1).

• The bc command (as well as dc) prints the huge numbers in several lines (please read the manual pages); consequently my code will print it as it is.

Answer 3

Your main problem is that you destroy the value of $num in your first factorial loop, but then you try to use it again post-loop. The value of $num always ends up at zero after said loop, so $((num-num1)) will end up being negative and the conditional $num2 -gt 0 will always be false on the first evaluation. You can solve this problem by copying the variable and destroying the copy.

Other recommendations:

• Use single-quoted strings instead of double-quoted when you don't need interpolation, since single-quoted strings disallow interpolation completely. It's safer that way. People get burned on accidental double-quoted interpolation all the time. Here's a good example: Assignment issue with Rscript -e calls.
• It's better to use $[...] for arithmetic evaluation instead of $((...)) because you save two characters.
• Never use `expr ...` for arithmetic evaluation since that requires a fork and complicates parsing (e.g. you had to backslash-escape asterisks, which is undesirable). (And I'm not sure why you sometimes chose that idiom, when you are obviously aware of the $((...)) construct for arithmetic expressions.) I suggest you consistently use $[...] for all arithmetic evaluation.
• It's better to use [[ ... ]] for conditionals, since it's more powerful than [ ... ] and has a cleaner syntax by virtue of being a shell keyword, whereas the single-bracket command is a mere builtin. (If you don't believe me, try running type [ [[.) Even when you don't require the more advanced capabilities of the double-bracket command you should still use it, for consistency in all your code, and, again, for the cleaner syntax.
• Since multiplying by 1 has no effect, you can change the -gt 0 tests to -gt 1.

---

#!/bin/bash

## get n
echo 'Enter no. to find factorial';
read n;

## compute n!
nFact=1;
temp1=$n;
while [[ $temp1 -gt 1 ]]; do
    nFact=$[temp1*nFact];
    temp1=$[temp1-1];
done;

## get r
echo 'Enter value for r';
read r;

## compute (n-r)!
nrFact=1;
temp1=$[n-r];
while [[ $temp1 -gt 1 ]]; do
    nrFact=$[temp1*nrFact];
    temp1=$[temp1-1];
done;

echo "Total no. of permutations $[nFact/nrFact]";