11
$\begingroup$

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!

$\endgroup$
1

4 Answers 4

11
$\begingroup$

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}}    *)
$\endgroup$
4
  • 2
    $\begingroup$ Thanks, how easy it is ... Didn't know Hamilton cycle $\endgroup$ Apr 8 at 15:52
  • 2
    $\begingroup$ (+1) Great and concise answer. Is there a reason for choosing FindHamiltonianCycle over FindCycle in this case? $\endgroup$
    – Ben Izd
    Apr 8 at 18:07
  • 2
    $\begingroup$ @BenIzd you're right, there's only one cycle and no need to insist on its Hamiltonian property. So FindCycle works just as well. FindCycle is also much faster than FindHamiltonianCycle, and so should be preferred. $\endgroup$
    – Roman
    Apr 8 at 19:31
  • 3
    $\begingroup$ @user1066 FindShortestTour[list] interprets the number-pairs as two-dimensional coordinates $\{x,y\}$, not as an abstract graph, and so its answer is wholly different from what is asked here: it solves the travelling-salesman problem. $\endgroup$
    – Roman
    Apr 8 at 19:57
6
$\begingroup$

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

enter image description here

$\endgroup$
3
$\begingroup$

Simple version

NestList[FirstCase[list, {Last[#], _}] &, {15, 16}, Length[list]]
$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.