## swaping items algo problem

Moderator: Board moderators

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

### swaping items algo problem

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.

New poster
Posts: 45
Joined: Sun Jun 26, 2005 6:21 am
Contact:
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
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 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.

New poster
Posts: 45
Joined: Sun Jun 26, 2005 6:21 am
Contact:
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
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 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
Darko: I'm guessing that the missing part of the problem statement is "minimize the number of swaps".