Best way to generate Pascal Triangle
-
28-06-2021 - |
سؤال
I am using the concept of level order traversal to generate Pascal Triangle.
Here is the code snippet:
void printPascalTriangle(int n)
{
int line=1,Q[50]={0},f=-1,r=-1,prev,t;
Enqueue(Q,&f,&r,1);
Enqueue(Q,&f,&r,0);
prev=0;
while(line!=n)
{
t = Dequeue(Q,&f,&r);
if( !t )
{
line++;
prev = 0;
Enqueue(Q,&f,&r,1);
if(!isEmpty(&r))
Enqueue(Q,&f,&r,0);
printf("\n");
}
else
{
printf("%d ", t);
Enqueue(Q,&f,&r,prev+t);
prev = t;
}
}
}
The complete code is here:
The advantage with this approach is that its space complexity is O(N) where N is the number of lines.
Is there any better way of doing the same?
المحلول
Since your only concern is space-complexity, and you're using int
(as opposed to some sort of big-integer type of potentially unbounded size), you can actually achieve space complexity of O(1) by using these two facts:
- C(n, 0) = 1 for 0 ≤ n
- C(n, k+1) = C(n, k) × (n − k) / (k + 1) for 0 ≤ k < n
These two facts mean that you can compute each element using only the previous element of the same row, so you never have to save more than one element at a time.
(By C(n, k) I mean the element in row n, position k of Pascal's triangle, assuming that rows and positions are numbered starting from 0.)
نصائح أخرى
I take it you wanted code, not an equation? Here are two JavaScript implementations, one with factorial calculation and one without it. I'm undecided on which one I prefer:
//1. non-factorial option
function GenerateTriangle1(rows) {
var pascalsTriangle = [];
for (var r = 0; r < rows; r++) {
var elements = r + 1;
var level = [];
for (var i = 0; i < elements; i++) {
if (i === 0 || i === elements - 1 || r === 1)
level[i] = 1;
else {
var prevRow = pascalsTriangle[r - 1];
level[i] = prevRow[i - 1] + prevRow[i];
}
}
pascalsTriangle[r] = level;
}
return pascalsTriangle;
}
//2. Factorial option
function GenerateTriangle2(rows) {
var pascalsTriangle = [];
for (var r = 0; r < rows; r++) {
var elements = r + 1;
var level = [];
for (var i = 0; i < elements; i++) {
level[i] = CalculateTerm(r, i);
}
pascalsTriangle[r] = level;
}
return pascalsTriangle;
}
function CalculateTerm(row, term) {
var divisor = Factorial(term) * Factorial(row - term);
return divisor > 0 ? Factorial(row) / divisor : 1;
}
function Factorial(n) {
return n > 1 ? n * Factorial(n - 1) : n;
}
console.log(GenerateTriangle1(4))
console.log(GenerateTriangle1(5))