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)

Input the Number of participating students and then store them in an Array.
Then form another Array of Integers , size equal to number of participating kids.
Shuffle the Integer Array.
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).

your solution is incorrect. There is a possibility that a person could get matched up with him/herself, which shouldn't happen. — Red Alert
– Red Alert, Commented May 3, 2014 at 1:16

Sergey Kalinichenko · Accepted Answer · 2014-05-03 01:37:17Z

3

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

edited May 3, 2014 at 1:37

answered May 3, 2014 at 1:25

Sergey Kalinichenko

729k85 gold badges1.2k silver badges1.6k bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

user3386109 Over a year ago

I wonder, what are the odds of self-assignment? Do the odds increase or decrease as the number of children increases?

Red Alert Over a year ago

@user3386109 1 person -> 1, 2 people -> 1/2, 3 people -> 1/3 + 2/3(1/2) = 2/3, 4 people -> 1/4 + 3/4(1/3 + 1/3(1/2)) = 1/2 - I think it keeps going down after this.

aschepler Over a year ago

I think the other array in the OP was for storing the names.

David Eisenstat Over a year ago

@user3386109 Asymptotically 1 - 1/e ~ 0.63.

David Eisenstat Over a year ago

@user3386109 The exact fraction of derangements (no self-assignment) is actually the appropriate truncation of the fast-converging series sum_{i = 0}^{\infty} (-1)^i/i! for exp(-1).

|

Collectives™ on Stack Overflow

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

1 Answer 1

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related