Jump to content
  • Advertisement
Sign in to follow this  
Desperado

Resort set by a farthes step walkthrough

This topic is 1323 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello,

 

I want to resort a set so that it becomes equal to a walkthrough of the set where every step is position wise as far away as possible from the element already visited. Say for example, I have a sorted set of 5 Elements from A to E:

 

( A, B, C, D, E )

 

The first element I want to visit is A. Then I want to visit the element as far away as possible from the first element, that means E. From A and E, the farthest Element is C which I want to visit next. B and D are equally far away from A, C and E so they are both last. So the resorted set would be:

 

(A, E, C, B, D) or (A, E, C, D, B)

 

The largest possible set size is probably around 100.

 

How can this be done?

 

Regards!

Share this post


Link to post
Share on other sites
Advertisement

It doesn't sound too complicated, you already have your algorithm there, just need to write it down and add some checks.

 

There's one step of initialization, the first 2 values you pick are always the same (first and last of the original list) and, assuming you have more elements, you try to find an element in the middels of the other too.

 

You can have 2 results there, the simples would be to find an element (you have an odd number of elements), so you pick that, and now you have 2 subgroups with the same size, one at the left and one at the right. You now need the element in the middle of each of this groups, so you repeat this steps again and generate more smaller subgroups.

 

The other case would be that you have an even number off elements, so you can't pick the middle one. In this case you just pick one (say, the left) and you got 2 new subgroups. One group has 1 extra element this time.

 

Now, the algorithm store a "section" (start and finish index) and keep the list ordered by size and start. After you pick one element, update the list of sections removing the one you checked and add 2 more (add checks to know when you picked the last element). Keep doing this until the list of sections is empty, and always use the first element in the list (the biggest group).

 

EDIT: An untested idea in JavaScript

function findMiddle(elements,section) {
  return Math.floor(section.end - section.start / 2) + section.start;
}

function splitSection(sectionsList,section,cutIndex) {
  if (cutIndex - section.start > 1)
    sections.push({start: section.start, end: cutIndex})
  if (section.end - cutIndex > 1)
    sections.push({start: cutIndex, end: section.end);

  // sort sections by size (descending) and start index (ascending)
}

elements = [A,B,C...]; //list of elements to "sort"
sortedElements = [];
sections = [];

sortedElements.push(elements[0]);
sortedElements.push(elements[elements.length-1]);

sections.push({start: 0, end: elements.length-1});

while (sections.length > 0) {
  index = findMiddle(elements,sections[0]);
  sortedElements.push(elements[index]);
  splitSection(sections,sections[0],index);
  sections.shift(); //removes the first element of the array
}
Edited by DiegoSLTS

Share this post


Link to post
Share on other sites

I think it would be pretty much equivalent of a conversion from an in-order walk of a corresponding binary search tree converted to a breadth first search but I wonder if there is a fast existing implementation for that.

Edited by Desperado

Share this post


Link to post
Share on other sites

You don't need to do anything to reorder the container; as long as it is random access, you can mimic the traversal pattern of a binary search and end up with a suitable visitation order based on your described criteria.

Share this post


Link to post
Share on other sites

Why do you need to do a BFS? Or an in-order search for that matter?

 

Like I've told you: your algorithm essentially describes a variant of a binary search, where each node you visit gets appended to the "result" list as you visit it. Just implement the visitation using the exact logic you described in the first post, and you're done. There's no breadth-first search necessary, no shuffling containers, no reordering anything.

 

You're making this a hell of a lot more complex than it needs to be :-)

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!