swaping items algo problem

wolf · Post by **wolf** » Mon Dec 04, 2006 12:32 pm

Hi all.

I have a problem like this:

There is a collection of some objects and an array of integers (the same size as collection size). The objects in the collection have to be sorted in order given in the array of integers, but and it has to be assumed that the only operation allowed on the collection is swaping positions of two objects.

I can't figure out any solution for this problem. Can someone give me a hint ? I'll be greatful.

Best regards,
Wolf.

marcadian · Post by **marcadian** » Mon Dec 04, 2006 2:23 pm

I think it can be done with simulate it, if it not in it's position, "carry" it to it's position and carry the one that occuppy the position before until all item in it's position
example:
1 2 4 5 3 << you want to be 1 2 3 4 5
1 << in position next
2 << next
4 <<not in position, carry to it's position, 4
become 1 2 5 4 3 << 5 not in position
carry to position 5
1 2 3 4 5
4 in position
4 in position
done

Darko · Post by **Darko** » Tue Dec 05, 2006 1:06 am

I don't think that your "carry" operation can be counted as "swapping two objects"?

It only restricts operations on the collection? Why not sort the array and every time you swap two elements of the array, you swap two objects at those positions? I am not sure that I understand the problem.

marcadian · Post by **marcadian** » Sat Dec 09, 2006 7:42 am

marcadian wrote:I think it can be done with simulate it, if it not in it's position, "carry" it to it's position and carry the one that occuppy the position before until all item in it's position
example:
1 2 4 5 3 << you want to be 1 2 3 4 5
1 << in position next
2 << next
4 <<not in position, carry to it's position, 4
become 1 2 5 4 3 << 5 not in position
carry to position 5
1 2 3 4 5
4 in position
4 in position
done

1 2 4 5 3 become 1 2 5 4 3 << you swap 4 with 5 right?? and then swap again 5 with 3.that's all

misof · Post by **misof** » Mon Dec 11, 2006 3:41 pm

"The objects in the collection have to be sorted in order given in the array of integers"
The array mentioned above is a permutation. Find its cycles. How does one swap operation change how the cycles look like? How can it change their count? What is the final state you want to achieve, in terms of permutations? And how many cycles does it have?

misof · Post by **misof** » Mon Dec 11, 2006 4:09 pm

Darko: I'm guessing that the missing part of the problem statement is "minimize the number of swaps".