Ordering of index pairs

Question

In a list of index-pairs every index occurs twice

list={{15, 16}, {13, 14}, {7, 11}, {6, 7}, {12, 13}, {1, 2}, {5, 6}, {18,19},
{16, 17}, {14, 15}, {20, 21}, {19, 20}, {2, 3}, {4, 5}, {3,4}, {9, 8}, {8, 1}, 
{21, 10},{10, 9}, {11, 12}, {17, 18}}

My question:

I'm looking for an easy way to rearrange the pairs in such a way that neighboring indices are equal?

I would expect a result in the form

{{15, 16},{16, 17}, {17, 18}, {18,19}, {19, 20}, {20, 21}, 
{21, 10},..., {13, 14},{14, 15}}

Thanks!

Answer 1

You are looking for a Hamiltonian cycle:

FindHamiltonianCycle[list]
(*    {{1—2, 2—3, 3—4, 4—5, 5—6, 6—7, 7—11, 11—12, 12—13, 13—14,
        14—15, 15—16, 16—17, 17—18, 18—19, 19—20, 20—21, 21—10,
        10—9, 9—8, 8—1}}    *)

Converted back to lists:

List @@@ First[FindHamiltonianCycle[list]]
(*    {{1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 6}, {6, 7}, {7, 11},
       {11, 12}, {12, 13}, {13, 14}, {14, 15}, {15, 16}, {16, 17},
       {17, 18}, {18, 19}, {19, 20}, {20, 21}, {21, 10},
       {10, 9}, {9, 8}, {8, 1}}    *)

Answer 2

Work for the case when the list is not a Hamilton cycle and also not necessary be a list of number.

• The original list.

cycles = FindPermutation @@ Reverse[Transpose@list]
list[[#]] & /@ cycles[[1]]

Cycles[{{1, 9, 21, 8, 12, 11, 18, 19, 16, 17, 6, 13, 15, 14, 7, 4, 3, 20, 5, 2, 10}}]

{{{15, 16}, {16, 17}, {17, 18}, {18, 19}, {19, 20}, {20, 21}, {21, 10}, {10, 9}, {9, 8}, {8, 1}, {1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 6}, {6, 7}, {7, 11}, {11, 12}, {12, 13}, {13, 14}, {14, 15}}}

• The list contain another objects.

Clear[list2, cycles2];
list2 = {{15, 16}, {13, 14}, {7, 11}, {6, 7}, {12, 13}, {1, 2}, {5, 
    6}, {18, 19}, {16, 17}, {14, a}, {20, 21}, {19, 20}, {2, 3}, {4, 
    5}, {3, 4}, {9, 8}, {8, 1}, {21, 10}, {10, 9}, {11, 12}, {17, 
    18}, {a, b}, {c, d}, {b, c}, {d, 15}, {q, r}, {r, p}, {p, q}};
cycles2 = Apply[FindPermutation]@*Reverse@Transpose@list2
list2[[#]] & /@ cycles2[[1]]
% // Length

Answer 3

Simple version

NestList[FirstCase[list, {Last[#], _}] &, {15, 16}, Length[list]]

Answer 4

Since your data forms a CycleGraph, graph algorithms are a great place to look as @Roman showed. As we know it's a cycle, we don't have to look for it, just pick a vertex (here we picked 1) and find all the vertices it leads to (VertexOutComponent). It's a little faster than FindCycle.

Block[{temp},
 temp = VertexOutComponent[DirectedEdge @@@ list, {1}];
 Append[Partition[temp, 2, 1], temp[[{-1, 1}]]]
 ]

(* Out: {{1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 6}, {6, 7}, {7, 11}, {11, 12}
  , {12, 13}, {13, 14}, {14, 15}, {15, 16}, {16, 17}, {17, 18}
  , {18, 19}, {19, 20}, {20, 21}, {21, 10}, {10, 9}, {9, 8}, {8, 1}} *)

Since VertexOutComponent doesn't include the last pair, connecting the last item to the first, we added it manually.

The only assumption here is each index is used twice in a form of {{i, _}, ..., {_, i}} otherwise DirectedEdge will invalidate the result.