Situation:
The following components exist for this problem:
- Two-dimensional, rectangular grid ("r" rows by "c" columns)
- One or more shapes: here a shape is defined as a straight line that is one segment by "L" adjacent segments in length. Each segment is equivalent in size to one cell of the grid.
Objective:
Algebraically calculate the total number of unique ways (permutations) that all shapes may be arranged on the grid simultaneously.
Ultimately, I will be using this function in either R or JavaScript; however, this is primarily a math/algebra question. I am comfortable converting any solutions provided into the appropriate language, as long as I understand how the solution works. All thoughts/languages are welcome and appreciated.
Criteria:
- All shapes must fit on the grid at once (and entirely).
- Shapes may not over lap. Only one segment may occupy a grid cell at a time.
- Shapes may be positioned vertically.
- Shapes may be positioned horizontally.
- Shapes may NOT be positioned diagonally.
- Shapes must remain intact (i.e., a 2-segment shape may not be split into two, one-segment shapes)
Background:
If each shape has a single segment (i.e., occupies only one cell of the grid) then factorials may be used:
Let x = r * c (the number of cells in the grid)
Let n = the number of single-segment shapes to fit on the grid
P(x,n) = x! / (x-n)!
Therefore, the permutations for two, single-segment shapes on a grid of three rows and three columns may be calculated as:
P((3*3),2) = 9!/(9-2)! = 72
Relatively simple and elegant.
Calculating permutations for a single shape having a length of L >=1 (requiring L <= r and L <= c) the process is somewhat less elegant but still relatively simple:
P(r,c,L) = r*(c-(L-1)) + c*(r-(L-1))
[I realize this can likely be simplified algebraically but it is clearer for me to illustrate the process this way]
Therefore, the permutations for a single, two-segment shape on a grid of three rows and three columns may be calculated as:
P(3,3,2) = 3*(3-(2-1)) + 3*(3-(2-1)) = 12
The next step is to introduce additional shapes of varying lengths into the equation.
For example, how many permutations exist for positioning a two-segment shape and a three-segment shape simultaneously on a grid of four rows and four columns? This is where I am stuck and feel I may be searching for an algebraic solution that does not exist or that is not possible.
(Incidentally, for testing purposes, I physically tested the example above and found 251 possible unique positions)
Graphic illustration of the problem:
Question:
Can this problem be solved algebraically, or does the problem require iterative functions to actually find all possible positions before providing a count of the number of permutations?
If the problem is solvable algebraically, can anyone provide direction on how this would be accomplished, or recommend a publicly accessible resource that I could use to learn how to solve this problem.