0

this is the array:

[[1,0], [3,4], [2,1], [4,5], [0,2], [5,3]]

Become like this:

[[1,0], [0,2], [2,1]]

[[3,4], [4,5], [5,3]]

I want to write a program, and I want to know if there are clever ways and logic to do it.

EDIT: The above example contains two "chains" (10 02 21 and 34 45 53). In all “chains”, each number pair can only appear once.

1 Answers1

0

You don't say that you want minimal or maximal chains (length or count), so I don't consider that here.

For each number appearing in your pairs, create a vertex in a directed graph. For each pair [a,b], insert the directed edge from $a$ to $b$.

You ask for a decomposition of this graph into a collection of Eulerian paths or possibly cycles. You don't say that the first element of the first member of a chain must match the second element of the last element of a chain, but your example does this. If this is intentional, you want decomposition into Eulerian cycles. If the first and last numbers need not match, then decomposition into Eulerian paths.

Veblen's theorem states that a connected (undirected) graph is Eulerian if and only if the graph has a decomposition into cycles. See Veblen's theorem for digraphs for adjusting Veblen's theorem for directed graphs.

So separate your graph into (strongly) connected pieces. (If you don't need Eulerian cycles, you can weaken this slightly to allow each piece to have up to one vertex with out-degree one and up to one vertex with in-degree one that must be the ends of the Eulerian path in that component. It may be that no assignment of such "dangling vertices" can be used to make an Eulerian path in the component, which would obstruct a solution.) There is a solution if each edge is in one of these connected components. Then apply directed Veblen to each strongly connected component (accounting for starting and stopping vertices if any are present in this component).

Eric Towers
  • 67,037