0

Context : I'm a IT student who is trying to implement a small application for my family. Every year, we offer each other gifts. Each one of us pick a name of a family member in a hat, and have to offer him a gift. The problem is, we always have some problem doing it:

Problem 1: When we pick, sometimes someone pick his own name and we have to start all over.

Problem 2 : Some people offers for two (or three) years consecutive to the same person

Algorithm

I'm looking for a way in which I can resolve the problem mentioned above. I was thinking the principle is to organize points in a cycle. But it would consider its historic to avoid repetition of pattern.

A -> B -> C -> D -> E -> A ...

I want to avoid A to be the direct child of D again, and B from A etc.. for example next result will be

B -> A -> D -> C  -> E -> B

(no point is the direct parent of last cycle)

The third time, i want A to avoid to be the direct child of E (first cycle) and B (second cycle) etc...

A -> E -> C -> B -> D -> A 

The points don't have to form a single cycle, as long as the problems described above are guaranteed to not happen.

5
  • 3
    I haven't downvoted, but I honestly can't figure out what you're asking for, which might be why. Do you have a graph you want to rearrange somehow? A list of letters you want to remove duplicates from? If a graph, are you removing edges or redirecting them? Perhaps more directly: what exactly does the third sequence you've given have to do with the first two?
    – Ixrec
    Dec 29, 2015 at 16:12
  • 2
    Consider if you got the answer "the algorithm is named Foo" - what would you do with that information? What problem are you trying to solve with this information you are trying to get? Why is this useful information?
    – user40980
    Dec 29, 2015 at 16:31
  • "avoid A to be child of D" doesn't really make sense since in the cycle everything is a child of something as one could just write out the cycle twice and see that everyone is a descendant of another. Is there a cleaner way to state what your point is there?
    – JB King
    Dec 29, 2015 at 17:17
  • After your edit, I think I see what you're getting at. But before I can make an additional edit to clean everything up and vote to reopen, one last clarification: You mention "cycle" several times, which originally looked like part of the problem, but now it looks like cycles have nothing to do with the problem and you simply thought they might be part of the solution. Is that correct? Or do you actually want the gift assignments to always form a single cycle (in addition to your other two constraints)?
    – Ixrec
    Dec 30, 2015 at 12:41
  • True, it is my own way of thinking it, and could be wrong, how do you think I should represent it? Thanks for your time :]
    – goto
    Dec 30, 2015 at 14:11

1 Answer 1

1

In essence you're performing a verification that the giving->receiving array is a so-called Costas array (i.e. a matrix of binary values where each column and each row holds exactly one 1 value).

Assuming the same set of family members year-on-year, you can build a binary-valued array (row=giver, column=reciever) of the disallowed combinations. You also want to disallow the diagonal self-self combination. Inverting the array gives you the allowed combinations (1=allowed).

Using the array of allowed combinations, you have a few choices:

  1. Enumerate the all possible values of the free bits defining the allowed combinations. Check if the resulting array is a Costas array. If so, the combination is allowed.

  2. Queue the gift givers, and a single array of gift receivers. For each giver, pick an allowed receiver (from the matrix). To help this process the order of gift givers should be from the smallest number of possible receivers to the largest.

In both of the above approaches, you may find that you don't actually have a solution, in which case you will want to relax some of the previous criteria (e.g. remove ban on least recent year) whilst retaining others (i.e. someone can't be given themselves.).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.