For example, for N = 4

1234 --> edge from 123 to 234

1243 --> edge from 124 to 243

It is clear that the result is minimum number of edges needed to add, such that there is Euler path in the graph. However, the added edge is weighted, according to number of matching suffix/prefix of the vertex.

All permutations of size N will transform to a graph with N! edges, with (N-1)! cycle, each of size N. Hence, the problem is to "connect" the cycles.

// Here is my probably wrong assumption.

If we consider only edges with weight 1, the problem to connect the cycles is identical to the original problem of size N-1, hence the recurrence relation. You can check it by drawing for small N. So this technique may be wrong if we need to use edges with weight > 1.]]>

2 Length : 3

3 Length : 9

4 Length : 33

5 Length : 153

6 Length : 873

7 Length : 5913

8 Length : 46233

9 Length : 409113 Code on edit: has a bug, not in determining the order, but on combining the result.

res.append(perm.substring(0,i-1));Should have been :

res.append(next.substring(N-i+1));]]>

-> "123121321" : 9

1234 2341 3412 4123 2314 3142 1423 4231

3124 1243 2431 4312 2134 1342 3421 4213

1324 3241 2413 4132 3214 2143 1432 4321

-> "123412314231243121342132413214321" : 33

Edit: Rearrange to better see the pattern used for greedy.]]>

It seems that your greedy also achieve same results.. anyway I don't know whether it's optimal

EDIT: My technique is briefly as follows. It is based on chinese postman problem. We can construct a graph, such that the result is the minimum edge needs to add to make the graph eulerian, plus current number of edges. With these given strings, we can always reduce the problem to count minimum number of edges to add, as a sub-problem with size n-1. Anyway, that's an upper-bound..]]>

Of course there might be potential bugs there.

Code in the edit.]]>

What you want to do is to find the shortest Hamiltonian path in a graph where vertices correspond to the permutations 1234, ..., 4321 and the length of an edge corresponds to the smallest number of digits we need to add. E.g., the edge 1234 -> 3421 has length 2.

This can be done in any n-vertex graph in O(2^n * poly(n)) -- the state can be represented by the set of visited vertices and the vertex where we are.

For n=24 this should run reasonably fast. And in the answer for N=4 you may be able to find some pattern that can be generalized.]]>

Edit: An approach related to de Bruijn's might be helpful, but nevertheless sclo's statement is true.]]>

output: 312313213

output contains 123,132,213,231,312,321, which are all permutations of 1,2,3. for 4, it must include 1234,1243.....,4321]]>