2
$\begingroup$

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 $12-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?

$\endgroup$
3
$\begingroup$

Hint: Let the vertices be the digits $0,\ldots,9$, and let the given integers be the edges.

$\endgroup$
  • $\begingroup$ Hi Yuval, thanks for the help. I didn't quite understand... Obviously you didn't mean to use all the digits as vertices for every input A (only the digits that appear in A), otherwise I'll might end up with a non connected graph, but what about the case where I have $22\in A$ for example? does it mean '2' will appear twice in $V$? and what about the edges? which edges should be connecting which vertices? $\endgroup$ – so.very.tired Dec 11 '13 at 23:46
  • 2
    $\begingroup$ I'm afraid you'll have to sort out these details yourself. You can then answer your own question (here) with all the details, for future generations of students. $\endgroup$ – Yuval Filmus Dec 12 '13 at 0:55
2
$\begingroup$

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$.

$\endgroup$

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.