0
\$\begingroup\$

I have a list of paired integers, every nth integer paired with every nth+1 integer. I'm trying to sort the list such that the pairs form a chain. For example:

Input: {12,72, 38,2, 72,38, 2,12} Output: {38,2, 2,12, 12,72, 72,38}

The trick is that the list may contain several unconnected chains. The chains don't need to be in any sequence, just the pairs within each chain. As per the input, each chain should be a loop unless they chain has only one pair, so any pair in the chain should be a valid first pair.

What I've tried is this (C#):

int a = 0;
int b = 0;
int temp;

while (a < list.Count) {
    b = a + 2;
    while (b < list.Count) {
        if (list[b] == list[a + 1]) {
            temp = list[b];
            list.RemoveAt(b);
            list.Insert(a + 2, temp);

            temp = list[b + 1];
            list.RemoveAt(b + 1);
            list.Insert(a + 3, temp);

            a += 2;
            b = a;
        }
        b += 2;
    }
    a += 2;
}

Which is giving me mostly correct results, but is still leaving the list with some disconnected pairs that should be part of a chain.

I'm not great with sorting algorithms and this has proven to be a difficult problem to google, so I'm hoping someone can point out the flaw in my code or point me in the right direction for research.

\$\endgroup\$
  • \$\begingroup\$ This looks like a general programming problem that doesn't use any game-specific concepts - you might find you get more answers faster by asking this type of question on StackOverflow instead, since they get far more traffic than we do. \$\endgroup\$ – DMGregory Mar 26 at 10:36
  • \$\begingroup\$ I did. Several people told me my question was too general, closed my question, then asked me why I couldn't just decide to need different output. People here have always been very helpful and understanding. StackOverflow, not so much. \$\endgroup\$ – IanLarson Mar 26 at 17:57
1
\$\begingroup\$

Your algorithm only appends links to a chain to the first encountered pair in the chain, but it does not ensure a is the first item in the chain.

The result is that an example like { 1,2, 0,1, 2,3} will sort to {1,2, 2,3, 0,1} instead of {0,1, 1,2, 2,3}, so links might be split up. You could check whether the pair at b comes before the pair at a, but with circular links being legal, you need to check for the case where the whole list is one long circular chain, which could result in infinite loops.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Apologies, I don't yet have enough rep to clarify my assumptions before posting an answer. Hope this helps! \$\endgroup\$ – EricKnowsCodefu Mar 26 at 4:45
  • \$\begingroup\$ Thanks for catching that typo! I think I fixed it. Your assumptions are good, except the second. Circular links are allowed, however, there is no "correct" start or end of a chain. As long as each pair in the chain leads into the next, it's a valid chain. That being said, there should be no need to go backwards, right? Any pair before "a" should have been checked against all other pairs. \$\endgroup\$ – IanLarson Mar 26 at 18:11
  • 1
    \$\begingroup\$ I think I understand what your saying, but I'm not quite seeing it. The incrementing after the swap sets "a" to the pair that was just swapped in. If no match is found to that pair, "a" is still set to that pair. The incrementing in the outer loop then moves it to the next unconnected pair to start a new chain. \$\endgroup\$ – IanLarson Mar 26 at 20:11
  • \$\begingroup\$ Also, I'm realizing in my implementation that all valid chains should be loops. I'm checking the functions that determine the input to make sure, but that seems to be the case, which should preclude the situation you added regarding the ordering of the pairs in the chain. I've edited my post to reflect that. \$\endgroup\$ – IanLarson Mar 26 at 20:16
  • \$\begingroup\$ Yep, that shouldn't be showing up in the input. \$\endgroup\$ – IanLarson Mar 26 at 21:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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