算法将一组对象分成一定数量的组？

Question

例如，假设我有一个二维像素数组（换句话说，一个图像），我想将它们排列成组，这样组的数量就会完全合计到一定数量（例如，总数另一个二维像素阵列）。目前，我尝试的是使用比率和像素的组合，但是除了完美的整数比例（例如1：2,1：3,1：4等）以外，这种情况会失败。当它确实失败时，它只是将其缩放为小于它的整数，因此，例如，1：2.93的比例尺将使用1：2的比例尺，同时部分图像被切除。我宁愿不要这样做，那么我可以使用哪些算法不能进入Matrix Multipication？我记得看到类似于我刚才提到的东西，但我找不到它。这是NP型问题吗？

例如，假设我有一个12x12像素的图像，并且我想将其分割成恰好64个大小为n的子图像。通过分析可以看出，我可以将其分解成8个2×2的子图像和56个2×1的子图像，以便获得确切数量的子图像。换句话说，我会用全部4（8）+56（2）= 144像素得到8 + 56 = 64个子图像。同样，如果我有一幅13×13像素的图像，并且我想要81个子图像，我需要把它分成4个2×2子图像，76个子图像，76个子图像，76个子图像，76个子图像2×1的子图像和1×1的子图像以获得所需的子图像的确切数量。换句话说，4（4）+76（2）+1 = 169和4 + 76 + 1 = 81。另外一个例子，如果我想将13×13的图像分割成n×m大小的36个子图像，我需要14个4×2的子图像，7个2×2的子图像， 2个子图像，14个2×1的子图像和1个1×1的子图像。换句话说，8（13）+4（10）+2（12）+1 = 169和13 + 10 + 12 + 1 = 36。

当然，图像不需要是方形的，既不是子图像的数量，也不应该是素数。另外，子图像的数量应该少于图像中的像素数量。我可能想要坚持两个幂的子图像的宽度和高度，以便于将一个较大的子图像转换为多个子图像，但是如果我可以找到一个算法，它不会那么做会更好。这基本上是我试图找到一个算法。

Answer 1

我知道你想将一个给定尺寸的矩形图像分成n矩形子图像。让我们说，你有：

• 尺寸的图像w * h
• ，并要分割成大小n子图像x * y

我认为，你想要的是

R = { (x, y) | x in [1..w], y in [1..h], x * y == (w * h)/n } 

这是一组配对(x, y)使得x * y等于(w * h)/n，w这里/是整数除法。另外，您可能想要采用具有最小周长的x * y矩形，即最小值为x + y。

对于该问题的三个例子：

• 分裂一个12 x 12图像分为64个子图像，你R = {(1,2),(2,1)}，所以你要么64 1 x 2子图像，或64 2 x 1子图像

• 分裂一个13 x 13图像分割成81个子图像，你恼火R = {(1,2),(2,1)}，所以你要么64 1 x 2子图像，或64 2 x 1子图像

• 分裂一个13 x 13图像分为36个子图像，你恼火R = {(1,4),(2,2),(4,1)}，所以你可以使用36 2 x 2子图像（最小周长）

对于每一个例子，你当然可以结合不同大小的矩形。

如果你想做些别的事情，也许平铺您的原始图像，你可能想看看rectangle tiling algorithms

Answer 2

如果你不关心子图像是不同大小的，一个简单的方法来这是否反复分裂两个子图像。每次新的分割都会将子图像的数量增加一个。