For every element in an array select a random element in the array

Question

I have been given programming assignment on which I have got stuck. Its Description is as follows:

There is a game named Secret Santa (who gives them gifts) where number of kids participate. For Every participating kid there is a Secret Santa friend from the participating kids. I have to write a program that selects a Secret Santa friend for every participating kid.

Example: IF Bob, Alice , John and George are participating kids, After random selection the
output may look like

   Kid            Secret Santa 

   Bob ---------- John
   Alice--------- Bob
   George-------- Alice
   John---------- George

Two consecutive runs of the program with same inputs should not have same results.

My idea is: (C based implementation)

1. Input the Number of participating students and then store them in an Array.
2. Then form another Array of Integers , size equal to number of participating kids.
3. Shuffle the Integer Array.
4. Then iterate through both the Arrays to find them the match.

Would this be the right way to do? it will waste an extra space of the Integer Array. Can Anyone help me find a more efficient solution (minimize space utilization).

Answer 1

You do not need two arrays - you need one. The formal name of what you are trying to find is Random Permutation. There are multiple well-known algorithms for it - for example, Fisher–Yates shuffle.

The algorithm for your problem is as follows:

• Input the number of kids, N
• Make an array of N items
• Fill it with numbers zero through N-1, inclusive
• Run Fisher–Yates shuffle
• Check that there are no self-assignments (i.e. no member of the permutation at position i is set to i)
• If there are self-assignments, run Fisher–Yates shuffle again, until you get a result that is free of self assignments
• Use the generated permutation to decide what child is who's Secret Santa.

For example, if N is four the permutation is 1, 3, 0, 2, then the assignment is as follows:

0. Bob  ---------- Alice  .1
1. Alice --------- John   .3
2. George -------- Bob    .0
3. John ---------- George .2