在不显式迭代的情况下找到满足某个条件的最大矩形块 [英] Find the largest rectangular block satisfying some condition without iterating explicitly

问题描述

我有一些大型二维数组，例如:

I have a few large 2D arrays like:

   1   2  3  4  5
   --------------
1 | 0  1  1  1  0
2 | 0  1  1  1  0
3 | 0  1  0  1  1
4 | 0  1  0  1  1

因此，满足 ==1 的最大矩形块(按面积)从 (1,2) 开始，其尺寸为 (2,3).

So, the largest rectangular block (by area) satisfying ==1 starts at (1,2) and its dimensions are (2,3).

如何在不显式迭代的情况下使用 Mathematica 找到它?

How to find it with Mathematica without iterating explicitly?

注意:

为了简化您的测试，这里是我的示例之一:

Just to ease your testing here is one of my samples:

matrix = ImageData@Binarize@Import@"http://i.stack.imgur.com/ux7tA.png"

推荐答案

这是我使用 BitAnd

maxBlock[mat_] := Block[{table, maxSeq, pos},

  maxSeq[list_] := 
   Max[Length[#] & /@ Append[Cases[Split[list], {1 ..}], {}]];

  table = 
   Flatten[Table[
     MapIndexed[{#2[[1]], maxSeq[#1]} &, 
      FoldList[BitAnd[#1, #2] &, mat[[k]], Drop[mat, k]]], {k, 1, 
      Length[mat]}], 1];

  pos = Ordering[(Times @@@ table), -1][[1]];

  {Times[##], {##}} & @@ table[[pos]]]

贝利撒留照片的结果:

Timing[maxBlock[Unitize[matrix, 1.]]]

(* {1.13253, {23433, {219, 107}}} *)

从好的方面来说，这段代码似乎比 David 和 Sjoerd 的代码快，但由于某种原因，它返回一个矩形，该矩形在两个维度上都比结果小一.由于差异恰好是一个，我怀疑某处存在计数错误，但目前我找不到它.

On the plus side this code seems faster than David's and Sjoerd's code, but for some reason it returns a rectangle which is one smaller in both dimensions than their result. Since the difference is exactly one I suspect a counting error somewhere but I can't find it at the moment.

这篇关于在不显式迭代的情况下找到满足某个条件的最大矩形块的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！