0
$\begingroup$

For a list which contains a set of elements I have two starting positions pos1and pos2 that are selected randomly. Next, I check if I can swap these elements. If the swap is not possible I want to look at the next pair of elements closest to the two starting positions.

list = |9|1|2|3|5|4|6|7|8|10|

Lets say my start positions are startPos1 = 2and startPos2 = 6. If the two values from these positions (2and 6) cannot be swapped I want to move on to the next closest pair. Now lets say I increment pos1 by one and find that the two elements in positions 3 and 6 cannot be swapped, too. If this is the case I want to look at the pair of elements in pos1 = 2 and pos2 = 5. That is, I would like to implement some kine of loop that gives me a sequence like this:

pos1 = 2
pos2 = 6
---------
pos1 = 2
pos2 = 5
---------
pos1 = 2
pos2 = 7
---------
pos1 = 3
pos2 = 6
---------
pos1 = 1
pos2 = 6
---------

If the elements in pos1 = 2 and pos2 = 7 can be swapped I terminate and otherwise I have to move on to the next pair of elements.

One can observe that the pairs listed above have a total deviation of 1 from the start values of the positions startPos1 = 2and startPos2 = 6. The next closest pair would have a total deviation of 2 and I think I can use this somehow but I haven't figured out how exactly.

Can anyone give me a hint how to implement this concept?

$\endgroup$
  • $\begingroup$ 1. What specifically are you uncertain about? What approaches have you considered? Have you tried writing some pseudocode? 2. What is the definition of "next closest pair"? It's not clear to me what distance metric you want to use. 3. This might be irrelevant, but: What would prevent you from swapping two elements? How do you know whether two elements can be swapped? Is there any structure to the set of pairs that can't be swapped? Or should I just assume you have some external, black-box subroutine that tells you whether a pair can be swapped or not? $\endgroup$ – D.W. Jan 6 '16 at 19:50
  • $\begingroup$ 1. My original idea was to use two loops each of which increments one of the positions. However, since I have to increment and decrement this did not work. I will work on some pseudocode and provide it asap. 2. The next closest pair would be the pair with the lowest total deviation from the starting positions. 3. Precedence relations exist between the elements. I have subroutine that checks if a swap is feasible. Does this somehow help? $\endgroup$ – Christoph Jan 6 '16 at 19:56
  • $\begingroup$ Thanks. 2. Can you give a definition of what you mean by "deviation" and "total deviation"? 3. If there was some structure to the set of pairs that can be swapped, it might be possible to use this to speed up the search for the next closest pair of elements. Or, maybe not. I don't know if it's relevant or not -- it might not be. $\endgroup$ – D.W. Jan 6 '16 at 19:59
  • $\begingroup$ 2. For both positions I would like to get the closest element. For instance, if I start with pos1 = 1 I want to get position 2 and after that position 0. Usually, if I iterate I would take position 2 and then 3. However, the deviation of position 3 from the starting position is 2 whereas it is only 1 for position 0. Does that make more sense? $\endgroup$ – Christoph Jan 6 '16 at 20:41
  • $\begingroup$ It's still not clear to me what counts as closest, or how you want to measure the distance from one pair to another pair. Let's say your starting position is the pair (2,6). So which is closer: the pair (4,8), or the pair (3,9)? Is (4,8) closer than (3,10)? How do you want to calculate "distance"? Do you want L1 distance? L2 distance? something else? You'll need to define this precisely for your question to be answerable. One or two examples aren't enough, and talking about the distance for a single index won't be enough to tell what counts as the distance when we talk about pairs. $\endgroup$ – D.W. Jan 6 '16 at 21:14

Your Answer

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

Browse other questions tagged or ask your own question.