swaping items algo problem

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
wolf
New poster
Posts: 34
Joined: Sun Aug 22, 2004 4:20 am
Location: Poland

swaping items algo problem

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
New poster
Posts: 45
Joined: Sun Jun 26, 2005 6:21 am
Contact:

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 :D

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

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
New poster
Posts: 45
Joined: Sun Jun 26, 2005 6:21 am
Contact:

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 :D
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
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

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
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

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".

Post Reply

Return to “Algorithms”