Arrange pairs of numbers so that members of adjacent pairs are equal

Question

I would like to arrange the following items, forming the longest chain possible starting with 12-8 and matching the numbers end to end.

My items are 7-4, 11-8, 11-11, 1-0, 4-2, 7-5, 10-8, 7-3, 10-5, 7-2, 9-8, 12-8, 0-0, 11-10

The longest possible chain is 12-8, 8-11, 11-11, 11-10, 10-5, 5-7, 7-4, 4-2, 2-7, 7-3

I tried iterating over the array of items and taking the first value that matches the number I'm looking for but it doesn't result in the longest chain. My method gets me: 12-8, 8-11, 11-11, 11-10, 10-8, 8-9

How can I write a proper sorting algorithm for this task?

Answer 1

you need recursion, but it might not work on a bigger data set: something like this.

DISCLAIMER: This is probably not the most optimized solution (complexity O(N!)) but it is very simple to implement if you are allowed to use recursion

(this is not objective-c code, it's an algorithm, translate it yourself, sorry i don't know objective-c)

list function sortTupleList(list a, list b) //b is the current list
  list biggest = newlist()
  int target = b.last()[1]
  for(tuple k in a)
    if (k[0] == target)
      list n = sortTupleList(a.remove(k), b.add(k))
      if(n.size > biggest.size())
        biggest = n
      end if
    end if
  end for
  if (biggest == emptylist)
    return b
  else
    return biggest
end function


list function caller(list a)
  list b = newlist()
  b.add(12-8)
  a.remove(12-8)
  return sortTupleList(a,b)
end function

This function will test every single pattern starting from 12-8 and compare their size

Answer 2

Depending on the size of your problem ( n number of the tiles ) you can choose either of the following methods:

1- Bruteforce: You can check all the possible configurations of tiles using backtrack that would result in an algorithm of O(n!) complexity.

2- Bitmask Dynamic Programming: You can use dynamic programming with the help of bitmask to reduce your search space. This approach will result in algorithm of O(2^n * n).

Answer 3

I've looked at the problem in a graph-theoretic perspective, which gives some insights about the problem, and provides some heuristics that may be used to solve the problem efficiently.

First, construct a graph such that every item you are given corresponds to an edge of the graph. For example, if your input given as: 1-2, 2-3; you construct a graph with nodes: 1, 2, 3; and edges (1, 2), (2, 3).

Thereafter, you can see that your problem is identical to finding the longest trail, i.e., the longest path that does not contain any edge more than one. Unfortunately, this problem is known to be NP-hard, as discussed in this question. So, we cannot hope to find a polynomial algorithm to solve this problem.

However, this problem is actually very similar to the problem of Eularian Path. However, in an Eularian path you traverse all edges. And it has a very simple solution:

An undirected graph has an Eulerian path if and only if exactly zero or two vertices have odd degree, and if all of its vertices with nonzero degree belong to a single connected component.

So in order to solve your problem, you take the connected component of the graph that contains the item you want to start with. You cannot possibly reach the items that are not in this connected component. Therefore, you can forget about all of the remaining edges of the graph.

Then, you simply count the degrees of each node, and check if that graph has an Eulerian path by the preceding definition. If it has, then you're lucky. Because you can't possibly have a chain longer than this path.

And you can compute this chain easily by Fleury's Algorithm.

However, if this component does not have an Eualirian path, then you at least know that there does not exist a chain of the size of the edges of this component or more.

Handshaking Lemma tells us:

Every undirected graph has an even number of vertices with odd degree.

If there does not exists an Eulerian path, then we know that we have 2k nodes with odd degrees where k > 1. So we need to remove minimum number of edges edges so that we have k = 1. However, you need to take into account that when you remove some of the edges, remaining edges may not be connected.

So the best heuristic that comes to my mind is to find edges such that both of its vertices have odd degrees, and removing it doesn't tear the connected component apart. If we can find such k - 1 vertices, then when we remove them we will stil have a connected component and we will have only 2 vertices with odd degrees. Therefore we can find the longest chain easily, again by finding an Eulerian path using Fleury's algorithm.

Answer 4

Think of the numbers as vertices and the pairs as edges of a graph (so there may be some multi-edges). Now your problem is reduced to finding the longest path in the graph where vertices (but not edges) may be repeated.