1
$\begingroup$

I have a path from node 1 to node n, which I can represent as a set: S = {1, 2, ..., n-1, n}. I want to efficiently generate the set of all subpaths from 1 to n. For instance, for n=5, we have S={1,2,3,4,5}.

So all the subpaths are as follows:

{{1,2},{2,3},{3,4},{4,5}, {1,2},{2,3},{3,4,5}, {1,2},{2,3,4},{4,5}, {1,2},{2,3,4,5}, {1,2,3},{3,4},{4,5}, {1,2,3},{3,4,5}, {1,2,3,4},{4,5}, {1,2,3,4,5}}

$\endgroup$
  • 1
    $\begingroup$ Can you define what a subpath means for you? And, what approaches have you considered? $\endgroup$ – D.W. May 31 '18 at 0:59
  • $\begingroup$ I was considering a depth first enumeration, but I was looking for a different conceptualization. I admit it was late in the day and I was tired. There's a better way to visualize it, as presented further below in this thread. $\endgroup$ – Bruno Repetto May 31 '18 at 17:11
  • $\begingroup$ A path is the enumeration of all nodes in it, from 1 to n. Edges are always of the form $(k,k+1)$. A subpath $\{i,j\}$, for $i<j$ is a collection of edges such that we have a path from i to j where $(i, i+1), \cdots,(j-1,j)$. A collection of subpaths from 1 to n is therefore of the form: $\{a_{1k},a_{2k}\}$ for $k=1,\cdots,p$ where $a_{11}=1$ and $a_{2p}=n$ and $a_{2(k-1)} = a_{1k}$. $\endgroup$ – Bruno Repetto May 31 '18 at 17:13
  • $\begingroup$ Rather than putting additional information or clarifications in the comments, please edit the question so it stands on its own and so people can understand your question without having ot read the comments; incorporate that information into the question. $\endgroup$ – D.W. May 31 '18 at 18:14
2
$\begingroup$

Suppose that the path consists of edges $e_1,\ldots,e_\ell$. The following answer assumes that by "subpath" you mean a partition of $e_1,\ldots,e_\ell$ into intervals. Go over all possible values of $b_1,\ldots,b_{\ell-1} \in \{T,F\}$. If $b_i = T$ then the edge $e_i$ ends an interval. Otherwise it doesn't. Here is how this looks in your case, $\ell=4$: $$ \begin{array}{ccc|c} b_1 & b_2 & b_3 & \text{subpath} \\\hline F & F & F & e_1e_2e_3e_4 \\ F & F & T & e_1e_2e_3;e_4 \\ F & T & F & e_1e_2;e_3e_4 \\ F & T & T & e_1e_2;e_3;e_4 \\ T & F & F & e_1;e_2e_3e_4 \\ T & F & T & e_1;e_2e_3;e_4 \\ T & T & F & e_1;e_2;e_3e_4 \\ T & T & T & e_1;e_2;e_3;e_4 \\ \end{array} $$

$\endgroup$
  • $\begingroup$ Viewed this way it becomes obvious! I'll test this out with the longer paths, but I think it should work correctly. Thanks @Yuval! $\endgroup$ – Bruno Repetto May 31 '18 at 16:53
  • $\begingroup$ This works beatifully! Thanks again @Yuval! $\endgroup$ – Bruno Repetto May 31 '18 at 21:45
0
$\begingroup$

I am storing the nodes in an array and using recursion to generate the combinations of possible subpaths.

The method generateSubPaths(int[] arr, int index) takes an array and an index as input. The array arr[] contains the nodes and the index represents the current node.

We call this method recursively by updating index to index - 1. This will return us an array of strings. Each element of the returned array represents a combination of subpaths up to node index - 1. The number of combinations gets double if we increase the number of nodes by 1.

For n = 2 : Paths =>

     (12)

For n = 3 : Paths =>

     (12)(23)

     (123)

For n = 4 : Paths =>

     (12)(23)(34)

     (123)(34)

     (1234)

     (12)(234)

For generating combinations after adding an extra node, repeat these steps for all existing combinations:

  1. Create a new path between the previous node and current node.

  2. Append new node to the last subpath in the combination.

Example :-

For n = 3 : One of the combinations is (12)(23).

For n = 4 :

  1. Create a new path between node 3 and node 4 i.e. (34). Therefore, the new path is

    (12)(23)(34).

  2. Append node 4 to the last subpath in the combination. Therefore, the new path is

    (12)(234).

Source Code :-

    import java.util.Scanner;

    public class SubPaths {

        public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

    // Input number of nodes (>1)
        System.out.println("Enter number of nodes (>1) :");
        int n = sc.nextInt();
        int[] arr = new int[n];

    // Initialize the array of nodes
        for (int i = 1; i <= n; ++i) {
            arr[i - 1] = i;
        }

        String[] result = generateSubPaths(arr, n);

    // Print each combination in a separate line
       for (String str : result) {
            System.out.println(str);
       }
       sc.close();
    }

    /*
    * This method will return an array of Strings , where each String 
    represents a
    * possible combination of subpaths
    */
    private static String[] generateSubPaths(int[] arr, int index) {
    /*
     * If there are only two nodes, only 1 combination is posssible.
     */
        if (index == 2) {
            String[] result = new String[1];
       // Join node 1   and node 2
            result[0] = "(" + arr[0] + arr[1] + ") "; 
        return result;
        }
    /*
     * smallResult[] stores all the combinations of subpaths where 
     * maximum node is represented by 'index'
     */
       String[] smallResult = generateSubPaths(arr, index - 1);
       int x = smallResult.length;
    /*
     * If one new node is added i.e. the current node, the possible 
     * combinations will be double of the previous ones.
     */
        String[] result = new String[x * 2];
        String temp;
        for (int i = 0; i < x; ++i) {
            temp = smallResult[i];
    // Create a new path between current node and previous node.
            result[i] = temp + "(" + temp.charAt(temp.length() - 2) + 
                    arr[index - 1] + ")";
    // Append current node to the last subpath in the combination
            result[x + i] = temp.substring(0, temp.length() - 1) + 
            arr[index - 1] + ") ";
        }
    return result;
    }
    }
$\endgroup$
  • $\begingroup$ This is not a programming site. There is no reason to include code in an answer. $\endgroup$ – Yuval Filmus May 31 '18 at 13:36
  • $\begingroup$ @YuvalFilmus I do not know much about how to answer a question. Should I remove this code block? $\endgroup$ – user89160 Jun 1 '18 at 5:34
  • $\begingroup$ You can replace it with succinct pseudocode. $\endgroup$ – Yuval Filmus Jun 1 '18 at 5:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.