dictionary of key, value from two lists without repeating items from either list-CodePudding

I am learning python and wanted to try and make a little script to handle "pulling names from a hat" to decide who has who for Christmas. I have no doubt that there is a more efficient way than this, but it works for the moment.

My issue is that it's taking a very inconsistent amount of time to complete. I can run this once, and it spits out the results instantly, but then the next time or few times it will just spin and I've let it sit for 5 minutes and it's still not complete.

Looking for some advice on why this is occurring and how to fix to make sure it doesn't take such a long time.

To start, I have two identical lists of the same names and then I shuffle them up:

fam1 = ["name1", "name2", "name3", "name4", "name5", "name6", "name7"]
fam2 = ["name1", "name2", "name3", "name4", "name5", "name6", "name7"]
fam1_shuffled = random.sample(fam1, len(fam1))
fam2_shuffled = random.sample(fam2, len(fam2))

I then have a dictionary of name pairs that are not allowed (so that husband: wife and wife: husband from the same house don't pull each other's names for example):

not_allowed_pairs = {
    "name1": "name4",
    "name4": "name1", 
    "name3": "name6", 
    "name6": "name3"
}

Then I have the function itself:

def pick_names(list1, list2): 
    pairs = {}
    gifters = list1
    used_names = []
    while len(pairs) < len(gifters): 
        for i in range(len(list1)): 
            if ((gifters[i] != list2[i]) & (list2[i] not in used_names)): 
                k = gifters[i]
                v = list2[i]
                if (k, v) not in non_allowed_pairs.items(): 
                    pairs[k] = v
                    used_names.append(v)
    return pairs

Finally, just to separate it out, I have the following function to print out who picked who.

def print_picks(pair_dict):
    for k, v in pair_dict.items():
        print(f"{k} picked: {v}")

CodePudding user response：

My issue is that it's taking a very inconsistent amount of time to complete. I can run this once, and it spits out the results instantly, but then the next time or few times it will just spin and I've let it sit for 5 minutes and it's still not complete.

This is because you end up with nothing but "not allowed" possibilities so, the program can never end.

I gave what you are trying to do a shot, and below is what I came up with. It can still hang, though. About one out of ten times the last value left from each fam results in a double.

import random

fam = ["name1", "name2", "name3", "name4", "name5", "name6", "name7"]


illegal = {
    "name1": "name4",
    "name4": "name1", 
    "name3": "name6",
    "name6": "name3"}
   
   
def make_pairs(fam): 
    #sort the illegal values to the beginning of a shuffled list to be handled first
    #and never shuffle this again
    fam1 = sorted(random.sample(fam, len(fam)), key=lambda n: n in illegal)
    
    #normal order, at first
    fam2 = fam
    
    while fam1:
        #keep shuffling fam2 til something is allowed
        while (fam1[0]==fam2[0]) or illegal.get(fam1[0])==fam2[0]:
            fam2 = random.sample(fam2, len(fam2))
            
        #yield pair
        yield fam1.pop(0), fam2.pop(0)


for k,v in make_pairs(fam):
    print(f'{k} picked {v}')

If you only invite an even number of people to Christmas the doubles problem goes away. You got a weird Uncle or something that you'd have more fun without?

CodePudding user response：

The crucial part of this algorithm is how we pick the receiver. For example, if the gifter is name1 then the receivers list should not contain name1, or name4 (because of the not_allowed_pairs). Here is my code:

import random


def print_picks(pair_dict):
    for k, v in pair_dict.items():
        print(f"{k} picked: {v}")      


def remove(lst, *elements):
    """Return a list with elements removed."""
    reduced_list = [
        element
        for element in lst
        if element not in elements
    ]
    return reduced_list


def pick_names(list1, list2, not_allowed_pairs):
    # Make copy to avoid modification of the original
    list2 = list2.copy()

    pairs = dict()
    for gifter in list1:
        receivers = remove(list2, gifter, not_allowed_pairs.get(gifter))
        receiver = random.choice(receivers)
        pairs[gifter] = receiver
        list2.remove(receiver)
    return pairs


def main():
    fam1 = ["name1", "name2", "name3", "name4", "name5", "name6", "name7", "name8"]
    fam2 = ["name1", "name2", "name3", "name4", "name5", "name6", "name7", "name8"]
    not_allowed_pairs = {
        "name1": "name4",
        "name4": "name1", 
        "name3": "name6", 
        "name6": "name3"
    }

    pairs = pick_names(fam1, fam2, not_allowed_pairs)
    print_picks(pairs)

if __name__ == '__main__':
    main()

Sample output:

name1 picked: name7
name2 picked: name3
name3 picked: name2
name4 picked: name5
name5 picked: name4
name6 picked: name8
name7 picked: name1
name8 picked: name6

Now this algorithm is not perfect: There will be time when we run out of names. For example, given name1, name2, and name3: name1 picked name2, name2 picked name1, then name3 got left over. These are edge cases, and I just run the script again.