By optimizing the permutation formula
In permutations, n!/(n-r)! can be expressed as the product of the first ‘r’ numbers subtracted from ‘n’, i.e., n * (n-1) * (n-2) * … * (n-r+1). Expressing permutations as the product of the first ‘r’ numbers subtracted from ‘n’ avoids computing factorials, reducing computational overhead and memory usage.
Approach:
- Initialize a variable ‘ans’ to store the answer.
- Iterate through a loop from ‘n’ down to (n-r+1), multiplying each number by ‘ans’.
- Update ‘ans’ with each multiplication.
- Print ‘ans’ as the result.
Example: The below code implements the optimized form of the permutation formula to calculate permutations in which n people can occupy r seats.
function calculatePermutations(n, r) {
let ans = 1;
for (let i = n; i >= (n - r + 1); i--) {
ans *= i;
}
return ans;
}
const n = 5;
const r = 3;
const totalArrangements =
calculatePermutations(n, r);
console.log(
`Total arrangements: ${totalArrangements}`);
Output
Total arrangements: 60
Time complexity: O(r), where r is the difference between n and (n-r+1).
Space complexity: O(1)
Permutations in which n People can Occupy r Seats in a Classroom using JavaScript
In this article, we’ll explore how to calculate permutations in JavaScript, specifically focusing on scenarios where ‘n’ people need to occupy ‘r’ seats in a classroom. Permutations, which determine the number of ways people can be arranged, are essential in various settings like event planning.
Examples:
Input: n = 5, r = 3
Output: 60
Explanation: 5 people can sit on 3 seats in 60 ways.
Input: n = 6, r = 4
Output: 360
Explanation: 6 people can sit on 4 seats in 360 ways.
Table of Content
- Using permutation formula
- By optimizing the permutation formula