Combination of connected paths of 0 to (k-1) to build path of k

Question

Suppose there is a polygon of 6 vertices. I have to build an array of paths of progressive distances. The attached image is an example.

Background: Polygon vertices are 0,1,2,3,4,5. A path from 1 to 4 will have vertices 1,2,3,4. I need to generate different combinations of this path. For example, (1,2,3) + (4) or (1,2)+(3,4) One such example is given in the image on the link below. I start by covering 1 vertex, then 1 edge, then 2 edges, then 3 and so on. This is the path distance. I repeat it with the same path distance on all the vertices. So if path distance is 2, I get the paths of distance 2 as: (0,1), (1,2), (2,3), (3,4), (4,5), (5,0). I increase this distance to 3 and then generate (0,1,2), (1,2,3), ..., (5,0,1). While generating a path, ex. (1,2,3), I use the path (1,2) and (3) which are generated previously.

I tried developing the algorithm. Tried looking online for something closer. But no luck!

The input and output can be found in this image on this address. Apologies for the not professional way of presenting the input/output.

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

1. Notice that each column starts with the column number.
2. One of the Edge case : For (1,2,3,4,5), if we consider (2,3,4), only possible combination of path is (1) + (2,3,4) + (5). Because (2,3,4) is in the middle of (1) and (5). We don't want to consider (1,2),(2,3) or (3,4).
3. To reach any vertex, we need to visit all the vertices in between.

Answer 1

The problem comes down to deciding for each edge on the "chain" whether it should be included in the path or not. This means there are 2^#edges possibilities for the path, which is 2^#nodes-1.

This can be done by iterating that many times with a loop variable, and use the binary bits of that variable to determine whether the edge is to be included or not.

When the edge is included, this means the next vertex will belong to the same "group" as the previous vertex. If not, the two involved vertices will belong to distinct groups.

Here is an implementation of that algorithm in a JavaScript snippet you can run here:

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));

The example

Let's take vertices [1, 2, 3, 4]. There are three edges on this chain: (1, 2), (2, 3) and (3, 4). For each we can decide to use it, or not, so we get this list of possibilities. I intentionally list the edges in reversed order:

 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)

These are all the possibilities. Now note how the "No" and "Yes" in this decision table can be seen as binary bits, where No = 0, and Yes = 1. So we actually can represent it that way:

 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]

This bit pattern can be interpreted as an integer number (when reading it as its binary representation). So from the top to the bottom of the table we see the binary representation of 0, 1, 2, 3, 4, 5, 6, and 7.

So if we would have a variable that we let increment from 0 to 7 (inclusive), and then look at its binary representation, we will get all possibilities.

Now when you have a specific value, like for instance 5 (which is 0x101 in binary), then you first look at the least significant bit (the rightmost one). It is 1. So that means edge (1, 2) must be included, or otherwise put: vertices 1 and 2 should be put in the same group. So we have a partial path [1, 2].

Then we "shift out" that rightmost digit. JavaScript has a shift operator (>>) for this, but you could also just do an integer division by 2. Either way, 5>>1 or 5/2, will give 2 (0x10 in binary - the rightmost 1 was dropped off). And we repeat: we look at the least significant bit. It is 0. That means edge (2, 3) should not be included: vertex 3 should be in a separate group. The partial path is now [1, 2],[3]

We shift again, and now only one bit remains. It is 1. So edge (3, 4) must be included. Vertex 4 should be in the same group as vertex 3. The path is now complete: [1, 2], [3, 4].