13
$\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

5 Answers 5

13
$\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, 2023 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, 2023 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, 2023 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, 2023 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, 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$

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$
3
$\begingroup$

Simple version

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

A modification of @Roman answer: which I have voted for (using RelationGraph):

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}};
g = RelationGraph[#1[[2]] == #2[[1]] &, list, VertexLabels -> "Name"]
FindHamiltonianPath[g]

enter image description here

{{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}}
$\endgroup$

Your Answer

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

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