Massive Algorithms: Secret Santa

Secret Santa is NP-Complete - Steve Rowe's Blog - Site Home - MSDN Blogs
TODO: Read the comments.
The current one does something naive like:

Pick a person
Choose a match at random
If there is a conflict with that person, slide to the next one on the list.
Once a match is found, remove those people from the relative lists and pick a new person.
If a match cannot be made, start the process over.

P, NP

In theoretical computer science, they don't use real computers. Rather, they use formal models called Turing Machines.

There is a class of problems called P or Polynomial-time which represent those problems that can be solved by a Turing machine in a time which is a polynomial of the input length. That is, O(n^2), O(n^3), ... , O(n^k). These are generally thought of as those problems that computers can efficiently solve.

There is another class of problems called NP or Nondeterministic-Polynomial-time. These represent those problems that can be solved by a nondeterministic Turing machine in polynomial time. A nondeterministic Turing machine is bascially one that can do more than one thing at once. When it comes to a fork in the algorithm, it can take both forks simultaneously.

It is assumed that NP describes a bigger universe of problems than P. That is, P !=NP. What takes nondeterministic Turing machines polynomial time takes regular Turing machinesexponential time. That is, they take something like O(2^n) time.

There is a well-known NP-class problem which involves finding a Hamiltonian circuit. A Hamiltonian circuit is a path that traverses an entire graph by visting each node exactly one time. It turns out that this is exactly the problem I was trying to solve. Imagine my Secret Santa problem as a graph where each person is a node and there are edges between all nodes that are not blacklisted. In this view of the problem, I'm trying to find a path around the graph, visting each node once. In theoretical computer science this is known as a reduction.

Random Derangement Of An Array

Generate all Derangements
https://gist.github.com/Jimexist/6474223
public static <T> List<List<T>> derangement(List<T> elements) {
List<List<T>> list = new ArrayList<>();
if (elements.size() == 0) {
list.add(new ArrayList<T>());
} else {
backtrack(elements, new int[elements.size()], 0, new BitSet(elements.size()), list);
}
return list;
}

private static <T> void backtrack(final List<T> elements,
final int[] buffer,
int k,
BitSet bs,
List<List<T>> result) {
if (k == elements.size()) {
List<T> range = new ArrayList<>();
for (int i : buffer) {
range.add(elements.get(i));
}
result.add(range);
} else {
for (int i=0; i<elements.size(); ++i) {
if (!bs.get(i) && i != k) {
bs.set(i);
buffer[k] = i;
backtrack(elements, buffer, k+1, bs, result);
bs.set(i, false);
}
}
}

}

Generate on Derangement Brute Force:
https://gist.github.com/anujku/f46852d71843db040160

public String[] generateAssignments(String[] names) {
// for string array name is null then return null
if (names == null) return null;
// for string array name length is zero then return an empty string array
if (names.length == 0) return new String[0];
// for single element in the array return the same array
if (names.length == 1) return names;

int nameslength = names.length;

Boolean[] chosen = new Boolean[nameslength];
Boolean[] santa = new Boolean[nameslength];

// initialize arrays with false
Arrays.fill(chosen, false);
Arrays.fill(santa, false);

Random rand = new Random();
// final result array
String[] result = new String[names.length];
int position = 0;

while (true) {
int randomInt1 = rand.nextInt(nameslength);
int randomInt2 = rand.nextInt(nameslength);

// get random person
String person1 = names[randomInt1];
String person2 = names[randomInt2];

if (person1 == person2) {
// do nothing
}
// if two person name are not same
if ((!person1.equals(person2)) && (santa[randomInt1] == false)
&& (chosen[randomInt2] == false)) {

if (!person1.equals(names[position])) {
result[position] = person1;
position++;

santa[randomInt1] = true;
chosen[randomInt2] = true;

if (isArrCompleted(santa) && isArrCompleted(chosen)) break;
}

}
}
return result;
}
private boolean isArrCompleted(Boolean[] arr) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == false) {
return false;
}
}
return true;

}
https://github.com/stevedreed/Secret-Santa/blob/master/SecretSanta.java
https://www.nealgroothuis.name/2007/12/a-somewhat-more-efficient-gift-giving-algorithm/

def swapElements(i, j, l):
    l[i], l[j] = l[j], l[i]
    return l

def randomDerangement(n):
    if n==2:
        return [1, 0]
    else:
        k=int(random.random()*(n-1))
        return swapElements(k, n-1, randomDerangement(n-1)+[n-1])

http://www.careercup.com/question?id=5352828797190144
Secret Santa should mean shuffle the contents of an array where if the index of element represent a person the content would represent the person who is assigned [for gifting] to him.

Input would : 0 , 1, 2, 3, 4 ...n
Output should be : shuffled contents such that a[i] != i

Iterate over elements of the array:
copy the content to next cell
copy the content of last cell to first cell.

The approach can be randomized by picking the shift distance randomly instead of 1.
http://stackoverflow.com/questions/7279895/shuffle-list-ensuring-that-no-item-remains-in-same-position
Read full article from Secret Santa is NP-Complete - Steve Rowe's Blog - Site Home - MSDN Blogs

Secret Santa

Labels

Popular Posts