[Solved]: Finding valid permutation using a graph

Problem Detail: 

Let $A$ be a set of integers: $A=\left \{ x_1, x_2...x_n \mid 10<x_i<100\right \}$

A valid permutation $x_{i_1}x_{i_2}...x_{i_n}$ is a permutation that holds the following property:

For every adjacent numbers $x_{i_j}x_{i_{j+1}}$, the unit's digit of $x_{i_j}$ is equal to the ten's digit of $x_{i_{j+1}}$.

For example, if $A=\left\{ 24,87,48,12 \right \}$ then $92-24-48-87$ is a valid permutation, whereas if $A=\left\{ 46,83,58 \right \}$, there is no valid permutation of $A$.

Now, given such a set $A$, I need to find an algorithm that prints a valid permutation if such exist, otherwise, it returns that there is no valid permutation of $A$.

I need to solve it using a graph, with a reasonable complexity, and I've been instructed to use some of the Eulerian path's properties, so it might play some role in getting the solution to that problem.

This is what I have in mind so far:

Setting a directed graph $G=(V,E)$ with: $V=\left\{ x_1, x_2...x_n\right \}$, and $E$ will contain all the arcs $(x_{i_j}, x_{i_{j+1}})$ s.t. $x_{i_j} x_{i_{j+1}}$ is valid (i.e the unit's digit of $x_{i_j}$ is equal to the ten's digit of $x_{i_{j+1}}$).

Now, if a valid permutation of $A$ exist, there is a path in $G$ that travel through every vertex only once.

There are two things that troubles me with this thought. First of all, it has nothing to do with Eulerian path, or Eulerian graph, or Eulerian anything, which makes me believe I'm way off target here. Second, the complexity of such algorithm is a nightmare: creating $G$ alone is $O(|V|^2)$, but that's nothing compared to finding some path in $G$ that traverse through all vertices only once, considering that I can't determine at which vertex to start the search.

Does anyone have an idea on how to approach this problem? Are there any observations I fail to see? Maybe searching the graph differently, or maybe even setting the graph in some other configuration?

Asked By : so.very.tired

Answered By : so.very.tired

Suppose $A$ is the input set.

Let $A=\left\{d_{11}d_{21},d_{12}d_{22},...,d_{1n}d_{2n}\right\}$ s.t. for every $d_{1i}d_{2i}\in A$: $d_{1i}$ is the ten's digit, and $d_{2i}$ is the unit's digit.

Construct a directed graph $G=(V,E)$ s.t: $$V=\left \{1\leq x\leq 9 \mid \exists d_{1i}d_{2i}\in D,x=d_{1i}\vee x=d_{2i} \right\}$$ $$E=\left \{(u,v)\in V\times V \mid \exists d_{1i}d_{2i}\in D,u=d_{1i}\wedge v=d_{2i} \right\}$$ Now, the constructed graph has an Eulerian path\circle in it iff $A$ has a valid permutation.

Moreover, I'll write some of the observations I made, that help finding the Eulerian path: if the given set $A$ has a "cyclic" valid permutation (a valid permutation $x_1x_2...x_n$ where $x_jx_{j+1}...x_nx_1...x_{j-1}$ is also valid, for every $1\leq j\leq n$), then for every $v\in V$: $\deg^+(v)=\deg^-(v)\neq 0$ (meaning in-degree equals out-degree), and finally the search for the Eulerian path can start at any arbitrary vertex in V.

On the other hand, if $A$ has a valid permutation that isn't cyclic, then there exist $v\in V$ s.t. $\deg^+(v)=deg^-(v)+1$, and there exist $u\in V$ s.t. $\deg^-(u)=\deg^+(u)+1$, and for every other $w\in V$: $\deg^+(w)=\deg^-(w)\neq 0$, and consequencly, the search for the Eulerian path must start at $v$ in this case (and should end at $u$).

In any other case (where neither of these two conditions are met), $G$ does not have an Eulerian path\circle in it, therefore there is no valid permutation of $A$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/18883

3.2K people like this

 Download Related Notes/Documents