Search

lundi 20 février 2017

Pascal's triangle

Context

Pascal's triangle is a triangular array of binomial coefficients: cell k of row n indicates how many combinations exist of n things taken k at a time.
Pascal's triangle looks like
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
...
One can prove that a given cell  is the sum of 2 cells from previous row: the one just above and the one on top left.
Given that, let's see how we can generate the Nth row of Pascal's triangle

Initial state


  • Memory: N 0 0 0
  • Cursor: on third cell
  • Input: any

Process

  • First, let's initialize the first row of the triangle
    • Set third cell to 1
  • Then, while our counter N is not null
    • Decrease counter
    • Generate next row
      • Go to array's last cell
      • Move current cell twice on the right (next 2 cells)
      • Go to previous cell and loop
    • This will generate next row. Actually, move is a "decrease here / increase there" process, so the first moves will transform 
      • ... A B C 0 into ... A B 0 C C
      • then into ... A 0 B (B+C) C
      • then into ... 0 A (A+B) (B+C) C
    • Finally, move the whole new row one cell to the left (because of an extra 0 introduced by steps above)
    • Go back to counter

Code - try it

initialize first row
>>+<<
[
  decrease counter
  -
  go to last cell
  >>[>]<
  [
    move twice
    [->+>+<<]
    go to previous cell
    <
  ]
  move whole array to the left
  >>[[-<+>]>]
  back to counter
  <<[<]<
]

Final state


  • Memory: 0 0 Nth row of Pascal's triangle
  • Cursor: first cell
  • Input: unchanged
  • Output: unchanged 
Note: because of cell size limitation, the row is computed modulo 256.
And because of that and 'one-cell' array implementation, this algorithm will fail as soon as one cell equals 0 modulo 256.
Anyway, this should not occur until counter = 256, meaning that it would overflow the cell limit for counter itself.
Any triangle row generated through this algorithm is therefore valid as long as it can be generated.

Aucun commentaire:

Enregistrer un commentaire