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 

Update:

I appreciate that but I need to write it in simple pseudocode with a loop statement 

2 Answers

Relevance
  • rotchm
    Lv 7
    1 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:

    1,2,3,4

    8,7,6,5

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

    1,8,2,3

    7,6,5,4

    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. 

  • Dixon
    Lv 7
    1 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

      

    https://en.wikipedia.org/wiki/Round-robin_tourname...

    Added:

    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)

Still have questions? Get answers by asking now.