Page 1 of 2 12 Last
  • Jump to page:
    #1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    13
    Rep Power
    0

    Decision (algorithm) problem


    Hi everyone!

    I've got the following problem: Given a file like:
    Lara Monday Tuesday
    Lucas Saturday Sunday
    Monica Sunday Monday
    Carlo Saturday Tuesday
    Franco Monday Thursday
    Lea Tuesday Wednesday
    Chris Friday Saturday

    The entries after the name are the days, on which the persons prefer to work.

    I should read the file in a dictionary. I did this with the following code:
    Code:
    import codecs
    from collections import defaultdict
    
    data = defaultdict(list)
    
    def readFile():
      print "Enter name of file which you want to read."
      filename = raw_input("filename: ")
      infile = codecs.open(filename, 'r')
      for line in infile:
        temp = line.split()
        data[temp[0]].append(temp[1])
        data[temp[0]].append(temp[2])
      print data

    I hope this is ok?
    Now, i've a question: How could a possible algorithm look like, which gives every person one of the preferred day s.t. as few persons as possible are unhappy (they don't receive any of the preferred days) and as many persons are happy.
    Let's say, we can offer 1 place on Monday, 2 on Tuesday, 4 on Saturday and 2 on Sunday. [only an exemple ]

    Thanks for any propositions
  2. #2
  3. Commie Mutant Traitor
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Jun 2004
    Location
    Alpharetta, GA
    Posts
    1,806
    Rep Power
    1570
    A quick test of the readFile() function does show that it seems to work:
    Code:
    defaultdict(<class 'list'>, {'Carlo': ['Saturday', 'Tuesday'], 'Franco': ['Monday', 'Thursday'], 'Lara': ['Monday', 'Tuesday'], 'Lea': ['Tuesday', 'Wednesday'], 'Monica': ['Sunday', 'Monday'], 'Chris': ['Friday', 'Saturday'], 'Lucas': ['Saturday', 'Sunday']})
    (The order is changed because of how the defaultdict() class hashes the keys.) Your next step presumably is to work out the algorithm for setting the days.
    Rev First Speaker Schol-R-LEA;2 JAM LCF ELF KoR KCO BiWM TGIF
    #define KINSEY (rand() % 7) λ Scheme is the Red Pill
    Scheme in Short Understanding the C/C++ Preprocessor
    Taming Python A Highly Opinionated Review of Programming Languages for the Novice, v1.1

    FOR SALE: One ShapeSystem 2300 CMD, extensively modified for human use. Includes s/w for anthro, transgender, sex-appeal enhance, & Gillian Anderson and Jason D. Poit clone forms. Some wear. $4500 obo. tverres@et.ins.gov
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    13
    Rep Power
    0
    Thanks for your reply.
    Well, in natural language, i'd propose following:
    "
    1. chek how many preferred mondays, tuesdays etc... there are
    2. if there is one day which is preferred more than the offered ones, I would check the other preferred day of the persons which have the same first preferred day. If the second choice is ok (i.e. the second choice is offered sufficiently often), we'll take the second choice. If the second choice of this person isn't offered sufficiently enough, we skip to the other persons and check the same.
    3.) If every person has its day or if there are no offered days left, we're finish.
    "
    This is what I elaborated. Do you think it's ok, logically?
    However; I still didn't get the implementation.
    Is it possible to help me?
  6. #4
  7. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,850
    Rep Power
    481
    I'd assign "satisfaction" weights to each person each day.
    0 is best through 6 worst.
    Then I'd call on an integer optimization function to find the happiest work force.
    Or, you might be able to adapt the genetic algorithm in this recent thread.
    Or, if the problem is small enough (I think your sample data set is small enough) you could try every possibility and that way certainly determine the global optimal solution.
    [code]Code tags[/code] are essential for python code and Makefiles!
  8. #5
  9. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    13
    Rep Power
    0
    Thanks for your reply.
    Your propositions sounds very interesting. How are these satisfaction weights implemented? (or: how would you do that?) And how would you then distribute the days? [a beginning would last...it's just that I see how it should work and how the code should look like]
    The thing is: my sample data is really small, so I'm not allowed to use predefined functions or algorithm...
  10. #6
  11. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,850
    Rep Power
    481
    I wrote my thoughts apparently while you wrote your natural language description. And the ideas are the same.

    Lara prefers Monday, but Tuesday would be okay.
    Code:
    #day     staff   weight
    #Mon     Lara    0
    #Tue     Lara    1
    #Wed     Lara    2
    #Thu     Lara    2
    #...
    
    weights = {(0,'Lucas'):1, # lucas (the name) 2nd preference (the 1) is Sunday (the 0)
    #...
    }
    for name_order in itertools.permutations(names):
        score = sum(weights[key] for key in enumerate(name_order))
        # do something smart with score and the particular assignments
    [code]Code tags[/code] are essential for python code and Makefiles!
  12. #7
  13. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    13
    Rep Power
    0
    Thank you very much for your help!
    ..I've a really stupid question: isn't it possible to assign the weights "automatically"?
    Because I read the data from a file and then, I have the data in the following form:
    Code:
     defaultdict(<class 'list'>, {'Carlo': ['Saturday', 'Tuesday'], 'Franco': ['Monday', 'Thursday'], 'Lara': ['Monday', 'Tuesday'], 'Lea': ['Tuesday', 'Wednesday'], 'Monica': ['Sunday', 'Monday'], 'Chris': ['Friday', 'Saturday'], 'Lucas': ['Saturday', 'Sunday']})
  14. #8
  15. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,850
    Rep Power
    481
    Sure, your (my) code can figure out that

    data['Carlo'][1] stores 'Tuesday' and that 'Tuesday' represents the 2nd day of the week.
    [code]Code tags[/code] are essential for python code and Makefiles!
  16. #9
  17. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    13
    Rep Power
    0
    Is there a way to store the values of all the keys in a dictionary?
    I.e. I want to save the values from the first person (without typing 'lucas' or whatever) in the dict; like: days = data.get_values(0)[0] += 1
    [this doesn't work - but is there a way without typing the person's name by hand?)
  18. #10
  19. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,850
    Rep Power
    481
    Does this help?
    Code:
    >>> D=dict(a=1,b=2,c=3)
    >>> (names,preferences) = tuple(zip(*D.items()))
    >>> names
    ('a', 'c', 'b')
    >>> preferences
    (1, 3, 2)
    >>>
    [code]Code tags[/code] are essential for python code and Makefiles!
  20. #11
  21. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    13
    Rep Power
    0
    Honestly, it doesn't help very much...
    Maybe I misunderstood something... So I show you what I've got until now.

    A defaultdict called data:
    data = defaultdict(<class 'list'>, {'Carlo': ['Saturday', 'Tuesday'], 'Franco': ['Monday', 'Thursday'], 'Lara': ['Monday', 'Tuesday'], 'Lea': ['Tuesday', 'Wednesday'], 'Monica': ['Sunday', 'Monday'], 'Chris': ['Friday', 'Saturday'], 'Lucas': ['Saturday', 'Sunday']})

    Now, I want to implement the function weights:
    Code:
    def weights():
      days = {}
     #...
    Here, I want to count how many persons wanna work on monday, tuesday, ...
    So far so good. But if there are too many preferences for the same day, I have to check if a person's second preference should/can be considered.
    And there's the point: I didn't get it yet how to implement this problem, the weights etc...

    So, every help is appreciated
    Thank you very much.
  22. #12
  23. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,850
    Rep Power
    481
    In my algorithm I intended weights as a dictionary. Of course you're supposed to use your algorithm, not mine. None the less, this is how I'd construct it:
    Code:
    $ python
    Python 2.7.3 (default, Sep 26 2012, 21:51:14) 
    [GCC 4.7.2] on linux2
    Type "help", "copyright", "credits" or "license" for more information.
    >>> data = {'Carlo': ['Saturday', 'Tuesday'], 'Franco': ['Monday', 'Thursday'], 'Lara': ['Monday', 'Tuesday'], 'Lea': ['Tuesday', 'Wednesday'], 'Monica': ['Sunday', 'Monday'], 'Chris': ['Friday', 'Saturday'], 'Lucas': ['Saturday', 'Sunday']}
    >>> days = 'Sunday Monday Tuesday Wednesday Thursday Friday Saturday'.split()
    >>> weights = dict()
    >>> for (key,value) in data.items():
    ...     name = key
    ...     preferences = value
    ...     for day in days:
    ...         if day == value[0]:               # best
    ...             w = 0
    ...         elif day == value[1]:             # 2nd choice
    ...             w = 1
    ...         else:                             # yuck!
    ...             w = 2
    ...         weights[(name,day)] = w
    ... 
    >>> import pprint
    >>> pprint.pprint(weights)
    {('Carlo', 'Friday'): 2,
     ('Carlo', 'Monday'): 2,
     ('Carlo', 'Saturday'): 0,
     ('Carlo', 'Sunday'): 2,
     ('Carlo', 'Thursday'): 2,
     ('Carlo', 'Tuesday'): 1,
     ('Carlo', 'Wednesday'): 2,
     ('Chris', 'Friday'): 0,
     ('Chris', 'Monday'): 2,
     ('Chris', 'Saturday'): 1,
     ('Chris', 'Sunday'): 2,
     ('Chris', 'Thursday'): 2,
     ('Chris', 'Tuesday'): 2,
     ('Chris', 'Wednesday'): 2,
     ('Franco', 'Friday'): 2,
     ('Franco', 'Monday'): 0,
     ('Franco', 'Saturday'): 2,
     ('Franco', 'Sunday'): 2,
     ('Franco', 'Thursday'): 1,
     ('Franco', 'Tuesday'): 2,
     ('Franco', 'Wednesday'): 2,
     ('Lara', 'Friday'): 2,
     ('Lara', 'Monday'): 0,
     ('Lara', 'Saturday'): 2,
     ('Lara', 'Sunday'): 2,
     ('Lara', 'Thursday'): 2,
     ('Lara', 'Tuesday'): 1,
     ('Lara', 'Wednesday'): 2,
     ('Lea', 'Friday'): 2,
     ('Lea', 'Monday'): 2,
     ('Lea', 'Saturday'): 2,
     ('Lea', 'Sunday'): 2,
     ('Lea', 'Thursday'): 2,
     ('Lea', 'Tuesday'): 0,
     ('Lea', 'Wednesday'): 1,
     ('Lucas', 'Friday'): 2,
     ('Lucas', 'Monday'): 2,
     ('Lucas', 'Saturday'): 0,
     ('Lucas', 'Sunday'): 1,
     ('Lucas', 'Thursday'): 2,
     ('Lucas', 'Tuesday'): 2,
     ('Lucas', 'Wednesday'): 2,
     ('Monica', 'Friday'): 2,
     ('Monica', 'Monday'): 1,
     ('Monica', 'Saturday'): 2,
     ('Monica', 'Sunday'): 0,
     ('Monica', 'Thursday'): 2,
     ('Monica', 'Tuesday'): 2,
     ('Monica', 'Wednesday'): 2}
    >>>
    [code]Code tags[/code] are essential for python code and Makefiles!
  24. #13
  25. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    13
    Rep Power
    0
    Thank you very much. This really helped developing my code
    To finish my whole program: How would you implement the offered days (i.e. Sunday, we need 2 persons, monday 1, tuesday 2 etc), s.t. every person is happy (i.e. as many as possible receive the 1. or the 2.preference)?

    Comments on this post

    • b49P23TIvg disagrees : reread post 6
  26. #14
  27. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    13
    Rep Power
    0
    At the moment, I have this:
    Code:
    def weight():
      choices = 'saturday sunday monday tuesday'.split()
      sorts = {}
      weights = dict()
      for (key, value) in data.items():
        name = key
        preferences = value
        for choice in choices:
          if choice == value[0]:
            w = 2
          elif choice == value[1]:
            w = 1
          else:
            w = 0
          weights[(name, choice)] = w
      for name, gew in weights.items():
        if sorts.has_key(name[1]):
          sorts[name[1]] += gew
        else:
          sorts[name[1]] = gew
      print sorts
    Now, I have a dict with the sum of all the preferences.
    Let's say I save the offered places also in a dict: offered = {'saturday':1, 'sunday':2, 'monday':1, 'tuesday':2}
    How can I finally solve the problem that I can distribute all the "wished" days (s.t. I know who works on which day) and I don't distribute too many places?
  28. #15
  29. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,850
    Rep Power
    481
    You've got 7 people and 7 days. These are the possible schedules:
    Code:
    >>> import itertools
    >>> for schedule in itertools.permutations('Bob Sue Jim Tony Alice Zane Tim'.split()):
    ...  print(schedule)
    ... 
    ('Bob', 'Sue', 'Jim', 'Tony', 'Alice', 'Zane', 'Tim')
    ('Bob', 'Sue', 'Jim', 'Tony', 'Alice', 'Tim', 'Zane')
    ('Bob', 'Sue', 'Jim', 'Tony', 'Zane', 'Alice', 'Tim')
    ('Bob', 'Sue', 'Jim', 'Tony', 'Zane', 'Tim', 'Alice')
    ('Bob', 'Sue', 'Jim', 'Tony', 'Tim', 'Alice', 'Zane')
    ('Bob', 'Sue', 'Jim', 'Tony', 'Tim', 'Zane', 'Alice')
    ('Bob', 'Sue', 'Jim', 'Alice', 'Tony', 'Zane', 'Tim')
    ...etceteras
    The first one means "Bob works on Sunday,...Tim works on Saturday".
    If Bob preferred Sunday, Tim's second preference was Saturday, and no one else got their preference, and if we assign 2 to first preference, 1 to 2nd preference, and 0 to dissatisfied, then the first schedule has a score of 3.

    Make all the schedules. (You told me that.) Score each schedule. Choose any of the schedules with the highest score. (Maximization.) I called it optimization, which means "find the minimum", but I assigned the weights traditionally. Obviously optimization searches for maximum of a function if you negate the goal function.

    And that, dude/dudette is why I told you to review one of my earlier posts.
    [code]Code tags[/code] are essential for python code and Makefiles!
Page 1 of 2 12 Last
  • Jump to page:

IMN logo majestic logo threadwatch logo seochat tools logo