News for hackers. Stuff that matters.
Re:The 892 unique ways to partition a 3 x 4 grid by btilly on Friday May 25, 2012 @01:38AM (#4022092)
Really? They have a patent on this??

This simply does not seem like a hard problem to solve. Certainly easier than, say, many Project Euler problems.

Re:The 892 unique ways to partition a 3 x 4 grid by joejohnson on Friday May 25, 2012 @02:38AM (#4022234)
It's too bad they don't post the MATLAB program used to generate these partitions. It is not known whether there exists a polynomial-time algorithm for finding orbits. I wonder what the largest grid size (n×m) is for which they've enumerated all possible partions.
Re:The 892 unique ways to partition a 3 x 4 grid by lloeki on Friday May 25, 2012 @08:04AM (#4023116)
Out of the blue (I did not look into the paper) I would have taken a stab at it like so:

I would start from the 12 case then remove one internal edge, which makes for all the 11 cases, then removing two edges (or one more edge if we're building a tree), and so on down to 1. We'll have to evaluate a few constraints on edges so as to ensure to only retain forms when they are rectangles.

After that (or at each step if you don't want the full list) we look for duplicates through rotation and symmetry. A possible implementation of the latter would be to model each case by numbering edges, and absence/presence of edges will set that bit/power of two, thus each case is a bitfield/integer, upon which we could apply a rotation function that tilts the bits, and then merely compare the resulting integers.

I guess this would be very close to a worst case in terms of complexity since it's essentially brute-force. Well, there are 17 edges to consider so that's 217 possibilities.

Re:The 892 unique ways to partition a 3 x 4 grid by sparknlaunch12 on Friday May 25, 2012 @01:50AM (#4022116)
Really great image however I was confused by one comment on the page suggesting there are more than 892 variations.

"I was confused at first because so many partitions are not on the poster. I see that this poster has culled horizontal and vertical symmetries, but the entry is titled “the 892 unique ways to partition a 3×4 grid.” Given this, I think a poster with all 3,164 partitions would have been (counter intuitively) more elegant. Or if the poster had just been titled “892 unique ways to partition a 3×4 grid.”

Re:The 892 unique ways to partition a 3 x 4 grid by joejohnson on Friday May 25, 2012 @02:09AM (#4022156)
There are 892 unique arrangements of unit rectangles in a 3x4 grid when you consider two arrangement which are rotations or mirror images of one another to be the same arrangement. When you count each arrangement and any rotations/mirror-images of that arrangement, there are 3,164 partitions.

Example: This partition:

  +-+---+-+
  | |   | |
  | |   +-+
  | |     |
  | |     |
  +-+-----+
...is just a rotation of this partition:

  +-+---+-+
  |     | |
  |     | |
  +-+   | |
  | |   | |
  +-+---+-+
There are 3,164 partitions if we say the above figures are distinct; if we call the above figures the same partition (but shown in two different orientations) then there are only 892 partitions.
Re:The 892 unique ways to partition a 3 x 4 grid by sparknlaunch12 on Friday May 25, 2012 @06:08AM (#4022818)
That makes sense. Thanks for the explanation.
Re:The 892 unique ways to partition a 3 x 4 grid by robinhouston on Friday May 25, 2012 @05:11AM (#4022680)
I love this sort of grid.

Along similar lines, last year I made a grid of all the possible 3x3 weave mazes. I think it would make a cool poster. https://github.com/robinhouston/maze-experiments/blob/master...

(The classification is not difficult, in this case: https://github.com/robinhouston/maze-experiments/tree/master...)

Re:The 892 unique ways to partition a 3 x 4 grid by datr on Friday May 25, 2012 @06:31AM (#4022872)
It would be a cool poster but I'd change the colours. The swastika and very similar shapes appear a few times in it (which is understandable) but you're also using two out of the three colours from the nazi flag. I could see this potentially leading to awkward and hurried explanations.
Re:The 892 unique ways to partition a 3 x 4 grid by LaRakel on Friday May 25, 2012 @06:37AM (#4022893)
When there's obviously no neonazi intentions there's nothing wrong with swastikas. Red black and white are pretty basic colours, you can't suggest that either.

There's something wrong with the people who'd make such conclusion, and not self-censoring will help get rid of connotations.

Re:The 892 unique ways to partition a 3 x 4 grid by dsirijus on Friday May 25, 2012 @08:03AM (#4023114)
I don't follow. What are they exactly patenting here (i.e. what doesn't one want to do not to get his behind sued)?

Partioning a grid? An algorithm for efficiently partitioning it?

In effect, what? Windows 8 gets sued? http://blog.docstoc.com/wp-content/uploads/2012/03/windows-8...