algorithm - 有效地计算一行中给定的一组 "blocks"的排列

Question

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

我想高效地获取线上所有可能的 block 排列。

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

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

可能的排列是

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

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

Answer 1

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

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

将这种递归逻辑翻译成实际的 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 方法，该方法返回可能包含给定 block 列表的最短行的长度，以及 stringOf 方法，它接受一个字符和一个数字，然后返回一个由给定字符的多个副本组成的字符串。

希望这对您有所帮助!