OJ Board

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.

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

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

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

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