0
$\begingroup$

I have n nodes, and I want to find the (non duplicate) number of possible ways in which these nodes can be combined in series and parallel, and also enumerate all the solutions. For example, for n=3, there are 19 possible combinations.

 0 (0, 1, 2)
 1 (0, 2, 1)
 2 (1, 2, 0)
 3 (1, 0, 2)
 4 (2, 0, 1)
 5 (2, 1, 0)
 6 [0, 1, 2]
 7 [0, (1, 2)]
 8 [0, (2, 1)]
 9 (0, [1, 2])
10 ([1, 2], 0)
11 [1, (0, 2)]
12 [1, (2, 0)]
13 (1, [0, 2])
14 ([0, 2], 1)
15 [2, (0, 1)]
16 [2, (1, 0)]
17 (2, [0, 1])
18 ([0, 1], 2)

In the notation above, a series combination is denoted by (..) and a parallel combination is denoted by [..]. Duplicates are removed, for example [0,1,2] is the same as [1,2,0] since all of them are happening in parallel so the order does not matter here.

Can you give me an algorithm for this, or if any such algorithm already exists, then point me to it?

(I tried googling for a solution, but did not hit any relevant answer, maybe I was entering the wrong keywords.)

Note: for a sequential-only solution, the answer is easy, it is n!, and the enumeration of the solutions is also easy. But when parallelism (especially non duplicates) is added to the problem, it gets very complex.

$\endgroup$
  • 1
    $\begingroup$ Is [[1,2],[3,4]] considered the same as [1,2,3,4]? Although it might be laborious, it will be useful if you can list all different solutions up to 5 nodes. If they are too long, publish it somewhere such as github or pastebin. $\endgroup$ – John L. Aug 1 at 16:52
  • 1
    $\begingroup$ Yes, both are same. It helps to think of the problem as electrical serial and parallel, to understand which are duplicates. I don't yet have an enumeration of 5, it is too big and I am trying to write a code to generate it myself. $\endgroup$ – R71 Aug 1 at 17:11
  • $\begingroup$ Explaining it is not exciting, so I'll be brief. To compute the number of ways you can use dynamic programming. You should compute functions $p(n)$ and $s(n)$: the number of ways to arrange $n$ nodes so that on the top level we have a parallel (or sequential) connection. For sequential it's straightforward: you select $k$ nodes which will form a parallel connection and use the rest for the rest for either sequential or parallel connection. So the number of ways is ${n \choose k} p(k) (p(n-k) + s(n-k))$. $\endgroup$ – Dmitry Aug 1 at 18:31
  • $\begingroup$ A parallel connection is a bit more tricky since the order of groups doesn't matter. The idea is to assign the first node to the first group (for the uniqueness of representation), and to decide elements which go to the same group. Connect the group sequentially, and the rest in parallel, the same way. $\endgroup$ – Dmitry Aug 1 at 18:36
  • $\begingroup$ Enumerating them is simple: for sequential connection, you can select the first parallel group, and consider its parallel enumerations as well as sequential enumerations of the rest of the items. For parallel connection, assign the first node to the first sequential group, and do the same. $\endgroup$ – Dmitry Aug 1 at 18:42

Your Answer

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

Browse other questions tagged or ask your own question.