时间戳

首页 > 解决方案 > 组合 0 到 (k-1) 的连通路径来构建 k 的路径

arrays - 组合 0 到 (k-1) 的连通路径来构建 k 的路径

问题描述

假设有一个 6 个顶点的多边形。我必须建立一系列渐进距离的路径。附图是一个例子。

背景：多边形顶点为 0,1,2,3,4,5。从 1 到 4 的路径将具有顶点 1、2、3、4。我需要生成这条路径的不同组合。例如，(1,2,3) + (4) 或 (1,2)+(3,4) 以下链接的图片中给出了一个这样的例子。我首先覆盖 1 个顶点，然后是 1 个边，然后是 2 个边，然后是 3 个，依此类推。这是路径距离。我在所有顶点上以相同的路径距离重复它。因此，如果路径距离为 2，我得到距离为 2 的路径：(0,1), (1,2), (2,3), (3,4), (4,5), (5,0 ）。我将此距离增加到 3，然后生成 (0,1,2), (1,2,3), ..., (5,0,1)。在生成路径时，例如。（1,2,3），我使用之前生成的路径（1,2）和（3）。

我尝试开发算法。尝试在网上寻找更接近的东西。但没有运气！

输入和输出可以在此地址的此图像中找到。为呈现输入/输出的不专业方式道歉。

https://drive.google.com/file/d/1-59Em9q1OsJ-nOASjj72lKPJoWy8H4UC/view?usp=drivesdk

  1. 请注意，每一列都以列号开头。
  2. 边缘情况之一：对于（1,2,3,4,5），如果我们考虑（2,3,4），路径的唯一可能组合是（1）+（2,3,4）+（5 ）。因为 (2,3,4) 在 (1) 和 (5) 的中间。我们不想考虑 (1,2)、(2,3) 或 (3,4)。
  3. 要到达任何顶点，我们需要访问其间的所有顶点。

标签： arraysalgorithm

解决方案

问题归结为决定“链”上的每个边缘是否应该包含在路径中。这意味着路径有 2 个#edges可能性，即 2 #nodes-1。

这可以通过使用循环变量多次迭代来完成，并使用该变量的二进制位来确定是否要包含边。

当包含边时，这意味着下一个顶点将与前一个顶点属于同一个“组”。如果不是，则两个涉及的顶点将属于不同的组。

这是您可以在此处运行的 JavaScript 片段中该算法的实现：

function getPaths(vertices) {
    let pathCount = 1 << (vertices.length - 1); // i.e. 2^(#nodes - 1)
    let paths = [];
    for (let i = 0; i < pathCount; i++) {
        let group = [vertices[0]]; // Group initially only has first vertex
        let path = [group]; // Path has at least one group
        for (let j = 1, bitPattern = i; j < vertices.length; j++, bitPattern >>= 1) {
            if (bitPattern & 1) { // bit is set, so add vertex to existing group
                group.push(vertices[j]);
            } else { // put vertex in a new group
                group = [vertices[j]];
                path.push(group);
            }
        }
        // Add path to array of paths
        paths.push(path);
    }
    return paths;
}

// Demo for 4 vertices:
let results = getPaths([1, 2, 3, 4]);
// Output results:
for (let result of results) console.log(JSON.stringify(result));

这个例子

让我们取顶点 [1, 2, 3, 4]。这条链上有三个边：(1, 2)、(2, 3) 和 (3, 4)。对于每个我们可以决定是否使用它，所以我们得到了这个可能性列表。我故意以相反的顺序列出边缘：

 Use (3, 4)? | Use (2, 3)? | Use (1, 2)? | Resulting path
-------------+-------------+-------------+----------------
    No       |    No       |    No       | [1],[2],[3],[4] (all disconnected)
    No       |    No       |    Yes      | [1,2],[3],[4]
    No       |    Yes      |    No       | [1],[2,3],[4]
    No       |    Yes      |    Yes      | [1,2,3],[4]
    Yes      |    No       |    No       | [1],[2],[3,4]
    Yes      |    No       |    Yes      | [1,2],[3,4]
    Yes      |    Yes      |    No       | [1],[2,3,4]
    Yes      |    Yes      |    Yes      | [1,2,3,4] (all edges used)

这些都是可能的。现在注意这个决策表中的“否”和“是”如何被视为二进制位，其中否 = 0，是 = 1。所以我们实际上可以这样表示：

 Bit Pattern | Resulting path
-------------+-----------------
     000     | [1],[2],[3],[4]
     001     | [1,2],[3],[4]
     010     | [1],[2,3],[4]
     011     | [1,2,3],[4]
     100     | [1],[2],[3,4]
     101     | [1,2],[3,4]
     110     | [1],[2,3,4]
     111     | [1,2,3,4]

此位模式可以解释为整数（当将其作为二进制表示读取时）。因此，从表格的顶部到底部，我们看到了 0、1、2、3、4、5、6 和 7 的二进制表示。

因此，如果我们有一个变量，让我们从 0 递增到 7（包括），然后查看它的二进制表示，我们将得到所有可能性。

现在，当您有一个特定值时，例如 5（二进制中的 0x101），那么您首先查看最低有效位（最右边的位）。它是 1。所以这意味着必须包含边 (1, 2)，或者以其他方式放置：顶点 1 和 2 应该放在同一组中。所以我们有一个部分路径 [1, 2]。

然后我们“移出”最右边的数字。JavaScript 有一个移位运算符 ( >>)，但您也可以只用 2 进行整数除法。无论哪种方式，5>>1 或 5/2 都会得到 2（二进制中的 0x10 - 最右边的 1 被丢弃）。我们重复一遍：我们查看最低有效位。它是 0。这意味着边 (2, 3) 不应该包括在内：顶点 3 应该在一个单独的组中。部分路径现在是 [1, 2],[3]

我们再次移动，现在只剩下一点。它是 1。所以边 (3, 4) 必须包括在内。顶点 4 应与顶点 3 位于同一组中。路径现已完成：[1, 2], [3, 4]。

推荐阅读