Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Groups within Matrix - Challenge Exercise

  1. Mar 18, 2013 #1
    Hello, I am writing my first software program (language:python) with the goal of conducting an interesting exercise related to matrices. I've ran into a slightly complex problem. First let me define something that will make my problem easier to communicate. Let an "H group" be a group of cells in matrix A. The group has an order to it, may start anywhere in matrix A and each cell is connected to an adjacent unused cell. No cell can be used twice and call the number of cells in any given H group its length, L. Example:

    Matrix A: 2x2:


    An H group that starts at cell [1], has length 4 and goes clockwise along the perimeter would be : [1], [2], [3], [6]. This H group has 1 turn. Other examples of H groups: [2],[5],[9],[6],[8] and [7],[8],[9],[6],[5],[4],[1],[2],[3] and [3],[5],[6],[2] and [1],[2],[6],[8] but NOT [1],[2],[8].

    My goal is to find and equation to represent the number of H groups with length L>=3 in a pxq matrix. These H groups may have turns (unlike the two equations below)

    Now, I've obtained an equation to find the number of H groups that are directed only Up, Down, Left and Right. Keep in mid this means these H groups have no "turns" in their pattern and the pattern connecting the cells is either purely up, down, left or right. This equation is: sum of up + down + left + right = 2p(q-L+1)+2q(p-L+1). Note, this form of the equation does not hold for H groups with L = 1. Please disregard this.

    I've also obtained a similar equation for the diagonal sum of H groups. Again, no turns allowed. The sum of unidirectional diagonal H groups in any direction (upright, upleft, downright or downleft) is =(p-L+1)*(q-L+1). The sum of all 4 directions is 4*(p-L+1)*(q-L+1). Again ignore the case of L = 1.

    Now I obtained these two equations by picking small pxq matrices, counting the unidirectional H groups and finding a pattern that lead me to the equation. However, the complexity is greatly increased when turns are involved. I could try a brute force approach and start with a 2x2 matrix and find all the H groups by hand. This has so far proven unhelpful...

    The following part may or may not be useful depending on how clearly you interrupt me. I encourage you to ignore it if you do not fully understand...Though I was able to fairly easily predict H groups of length L=4 in a 2x3 matrix by looking at the H groups of length L=3, I have found no reasonable pattern. The approach I've been taking involves looking at unique patterns (aka basic shapes) and rotating these basic shapes.

    For your resource:

    basic shapes of L = 3 in 2x2: 3*4rotations
    basic shapes of L = 4 in 2x2: 3*4rotations
    basic shapes of L = 3 in 2x3: 4*2rotations
    basic shapes of L = 4 in 2x2: 16*2rotations

    **I know I've been unclear, but I encourage you to try this problem yourself and post any questions or solutions you may have. Feel free to email me at abilityinfinity@gmail.com. Sorry for being so long winded. Like I said, this is an exercise for fun so the reasoning is more important than the solution.
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted