高效地计算行中给定“块”集合的排列

我正在研究一个应用程序，其中应有一些块应位于一行上。即有不同数量的块，每块有不同的长度，应该放在线上。块之间至少需要有一个空元素。高效地计算行中给定“块”集合的排列

我想有效地获得所有可能的排列在线上的块。

例如，我有一个长度为15的行，并希望放置1,6和1大小的块。

订单很重要，例如，在我的示例中，1尺寸块总是应该在6尺寸块的左侧和右侧。

可能的排列是

X.XXXXXX.X..... 
X..XXXXXX.X.... 
... 
.....X.XXXXXX.X

如何高效地产生更高层次的语言，例如所有可能的排列Java的？要做到这一点

来源

2013-01-03 centic

出于好奇，这是nonograms？ – templatetypedef

是的，我在玩 – centic

一种方法是递归来解决：

如果所需的最小总长度所有的块存储可以精确到一个空间，它们之间超过了可用空间，有没有办法放置块。
否则，如果你没有块放置，那么放置块的唯一方法是让所有的方块都没有填充。
否则，有两种选择。首先，您可以将第一个块放置在该行的第一个位置，然后递归地将剩余的块放置在行的剩余空间中，然后在该行的开始处首先留下一个额外的空白空间。其次，您可以将行中的第一个空格留空，然后递归地将同一组块放入行中的剩余空间。尝试两种选择并将结果合并到一起应该会给你你正在寻找的答案。

将此递归逻辑转换为实际的Java应该不会太困难。下面的代码是专为可读性和可优化的一点：

public List<String> allBlockOrderings(int rowLength, List<Integer> blockSizes) { 
    /* Case 1: Not enough space left. */ 
    if (spaceNeededFor(blockSizes) > rowLength)) return Collections.EMPTY_LIST; 

    List<String> result = new ArrayList<String>(); 

    /* Case 2: Nothing to place. */ 
    if (blockSizes.isEmpty()) { 
     result.add(stringOf('.', rowLength)); 
    } else { 
     /* Case 3a: place the very first block at the beginning of the row. */ 
     List<String> placeFirst = allBlockOrderings(rowLength - blockSizes.get(0) - 1, 
                blockSizes.subList(1, blockSizes.length())); 
     for (String rest: placeFirst) { 
      result.add(stringOf('X', blockSizes.get(0)) + rest); 
     } 

     /* Case 3b: leave the very first spot open. */ 
     List<String> skipFirst = allBlockOrderings(rowLength - 1, blockSizes); 
     for (String rest: skipFirst) { 
      result.add('.' + rest); 
     } 
    } 
    return result; 
}

你需要实现spaceNeededFor方法，它返回那些可能持有块的给定列表最短行的长度，和接收字符和数字的stringOf方法会返回给定字符的许多副本的字符串。

希望这会有所帮助！

来源

2013-01-03 09:24:08 templatetypedef

没有明确得到第三点..请详细说明一下吧 –

@ ShivaKomuravelly-试着想想你要把第一块放在哪里。它要么在第一个地方，要么就离开第一个地方。如果您尝试使用这两个选项（将第一个块放在行的开头，或者在行的开始处打开空间），然后将所有剩余的块递归放置在未使用的空间中，您将生成所有可能的放置位置。另外，如果有帮助，我添加了一些代码。 – templatetypedef

谢谢，我会尝试编码它类似于此，并会报告回来，如果它的工作 – centic

很难确定什么是“高效实现”，因为输出可能非常大，因此即使快速实现也不够快。

我会使用这种任务的动态编程和递归技术。递归函数应该有两个参数 - 未使用的数字列表和行的剩余长度。它内部将是一个简单的循环。你应该存储你已经知道的结果。我相信你可以自己处理细节。编辑：我们的朋友已经为你做了这件事:-)。

顺便说一下，这样的任务的目标是什么？它重新描述了网格中的图片，其中每行和每列都有这样的数字，并且您需要对图片进行解码。有更好的方法来解决这个问题。

来源

2013-01-03 09:30:41 Danstahr

对我来说，似乎更容易想到另一种方式的问题：

我们有固定块在固定的顺序，用点分隔。我们可以通过将剩余的点分布在允许的位置上来创建所有排列。

线的该固定部分的长度是：

fixed_len = length_of_all_blocks + number_of_blocks - 1

其余的点的数目是

free_dots = length_of_line - fixed_len.

打开位置的数量是

pos_count = number_of_blocks + 1

现在我们必须找到如何将free_dots放入pos_count的所有排列组合。

来源

2013-01-03 09:50:42

这里'free_dots'包含那些介于两者之间的点...对吗？ –

我试过了，它不工作 –

@ ShivaKomuravelly-这听起来像是一个很好的解决方案。您的实施中可能存在某个错误。 – templatetypedef

高效地计算行中给定“块”集合的排列

回答

相关问题