Thread Subject:

Secret Santa

I am looking for a Matlab program that will draw the names for a secret santa. The rules of secret santa are pretty straight forward: each member of the group is "santa" (i.e., buys a gift) for another member of the group. Each member of the group must have one and only one santa. Further, you cannot be your own santa. I have a list of email addresses and the corresponding names and would like Matlab to email each person who they are santa for. It seems like there may be an elegant solution to this, I just do not see it yet..

"Daniel " <daniel_shub@yahoo.com> wrote in message <hdr9bq$2im$1@fred.mathworks.com>...
> I am looking for a Matlab program that will draw the names for a secret santa. The rules of secret santa are pretty straight forward: each member of the group is "santa" (i.e., buys a gift) for another member of the group. Each member of the group must have one and only one santa. Further, you cannot be your own santa. I have a list of email addresses and the corresponding names and would like Matlab to email each person who they are santa for. It seems like there may be an elegant solution to this, I just do not see it yet..

This "shuffling" of set members is known as a derangement, a special kind of permutation.

See my RANDPERMFULL for an implementation in ML:
http://www.mathworks.com/matlabcentral/fileexchange/23257-randpermfull

Group = {'A','B','C','D'} ;
Ridx = randpermfull(numel(Group))
Santa = Group(Ridx)

hth
Jos

"Daniel" wrote in message <hdr9bq$2im$1@fred.mathworks.com>...
> I am looking for a Matlab program that will draw the names for a secret santa. The rules of secret santa are pretty straight forward: each member of the group is "santa" (i.e., buys a gift) for another member of the group. Each member of the group must have one and only one santa. Further, you cannot be your own santa. I have a list of email addresses and the corresponding names and would like Matlab to email each person who they are santa for. It seems like there may be an elegant solution to this, I just do not see it yet..

function[out] = secret_santa(N)
%randomises the numbers to give a random list of pairs, where each number (or name)
%is represented once in each list, and no pair has the same numbers (or names).
%Input
%If names are available, then input the list of names (as a cell array),
%and the output will be a list of the original names, and their pair. (As a
%N by 2 cell array)
%If names are not available, input just the number of people (N), and the
%output will be a list of numerical pairs, as a N by 2 numerical matrix.

nc = 0;
if iscell(N)
    names = N;nc = 1;
    N = length(names);
end

out = nan(N,1);
select = 1:N;

for i = 1:N
    i
    check = 0;
    while check == 0
        [b I] = max(rand(length(select),1));
        if select(I) ~= i
            out(i) = select(I);
            select(I) = [];
            check = 1;
        end
    end
end

if nc==1
    out = [names,names(out)];
end

"Ian " <l@l.com> wrote in message
news:k70cm4$572$1@newscl01ah.mathworks.com...
> "Daniel" wrote in message <hdr9bq$2im$1@fred.mathworks.com>...
>> I am looking for a Matlab program that will draw the names for a secret
>> santa. The rules of secret santa are pretty straight forward: each member
>> of the group is "santa" (i.e., buys a gift) for another member of the
>> group. Each member of the group must have one and only one santa.
>> Further, you cannot be your own santa. I have a list of email addresses
>> and the corresponding names and would like Matlab to email each person
>> who they are santa for. It seems like there may be an elegant solution to
>> this, I just do not see it yet..

What you're looking for is a derangement of the numbers 1:N.

http://en.wikipedia.org/wiki/Derangement

While there is pseudocode on the wiki page, I would do something more like
this.

if N is sufficiently large
    Generate a random permutation
    While there are any fixed points
        Generate a new random permutation
    End
else
    List all permutations
    Eliminate any permutation with a fixed point
    Select one of the remaining permutations at random
end

The RANDPERM and PERMS functions will be of use to you.

Once you have your derangement of 1:N, it's easy to use that to index into
your list of names/addresses.

--
Steve Lord
slord@mathworks.com
To contact Technical Support use the Contact Us link on
http://www.mathworks.com