A teacher needs to arrange 2n children in n pairs. Design an algorithm for this task so that for 2n-1 days no pair would be the same.?
I need to write this in simple pseudocode and draw it in a flowchart
I appreciate that but I need to write it in simple pseudocode with a loop statement
- rotchmLv 71 month ago
Hint: Lets work with n=4. **Ignore my original answer, it doesn't work.*** :
1,2,3,4 --> fixed in position.
5,6,7,8 --> & shift [making 4 combos].
Then repeat with a different initial config, like:
***this won't work since some pairs will repeat. We need to modify a little our approach.***
Thinking a little more, we realize that the max # of days is 2n-1. This is why your questions asks for 2n-1 days.
A (similar) procedure that works is keep only #1 fixed, say. Shift all the others CW, say, to get
Reiterate. Since there are 2n-1 persons (#1 fixed) that can "move" (shifted), you have 2n-1 different configs.
And yes, this is a round-robin procedure.
- DixonLv 71 month ago
2n things can make 2n(2n - 1)/2 = n(2n - 1) unique pairs.
Since the task is for (2n - 1) days there are n pairs available for each day - which is OK - and then we are using every possible pair.
This is the same idea as a Round Robin tournament, where there are a series of rounds over which every player plays against every other player. Rather than me describe the algorithm here, I suggest you read about it on Wikipedia
The linked section describes the algorithm, which is basically an array A of elements 1 to 2n, where every turn the lower half of the array is paired against the upper half. Then after each pairing (each day) every A(x) moves to A(x + 1), apart from A(1) which stays put and A(2n) goes to A(2)