2

我正在开发一个应用程序，其中我有许多应该放在一条线上的块。即有不同数量的块，每个块都有不同的长度，应该放在线上。块之间至少需要有一个空元素。

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

例如，我有一条长度为 15 的线，想放置 1、6 和 1 大小的块。

顺序很重要，即在我的示例中，1-size 块始终应位于 6-size 块的左侧和右侧。

可能的排列是

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

如何有效地生成高级语言（例如 Java）中所有可能的排列？

4

3 回答 3

3

一种方法是递归地处理它：

  1. 如果存储所有块之间只有一个空格所需的最小总长度超过可用空间，则无法放置块。
  2. 否则，如果你没有要放置的方块，那么放置方块的唯一方法就是让所有方块都空着。
  3. 否则，有两种选择。首先，您可以将第一个块放置在行中的第一个位置，然后在行首留下一个额外的空白空间后，递归地将剩余的块放置在行内的剩余空间中。其次，您可以将行中的第一个空格留空，然后递归地将同一组块放置在该行的剩余空间中。尝试这两个选项并将结果组合在一起应该会给您正在寻找的答案。

将这种递归逻辑转换为实际的 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-03T09:24:08.480 回答
1

对我来说，以另一种方式思考这个问题似乎更容易：

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

线的这个固定部分的长度是：

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-03T09:50:42.897 回答
0

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

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

顺便问一下，这样的任务的目标是什么？我仍然对网格中的图片感兴趣，其中每一行和每一列都有这样的数字，你需要对图片进行解码。有更好的方法来解决此类问题。

于 2013-01-03T09:30:41.813 回答