#1
  1. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2012
    Posts
    44
    Rep Power
    2

    How to delete the ranked last [Python]?


    Hi so i have a question..
    I want help with a code in which i can understand how something in a dictionary could be deleted in the code for ranking last by the number of values it gets..

    For example..
    {(A,B,C,D):3
    (A,C,B,D):2
    (B,D,C,A):4
    (D,C,B,A):3
    (C,B,A,D):1
    (C,D,A,B):1}
    Total values added = 14
    A came first = 5 times
    B came first = 4 times
    C came first = 2 times
    D came first = 3 times
    We would delete C/ eliminate it because it has the lowest value: so we will get something like..
    {(A,B,D):3
    (A,B,D):2
    (B,D,A):4
    (D,B,A):3
    (B,A,D):1
    (D,A,B):1}

    [A, B, D]
    [5, 5, 4]

    Then D would be eliminated and so on...

    The highest number is 5 and 5 out of 14 is less than 50% so we will continuously eliminate all the least numbers until we have one large..
    in this example --
    B = 8 times in the end
    A = 6 times in the end

    and 8/ 14 is more than 50% so majority s B!!
    How do i accomplish such a code.. any ideas??

    In the end the output should be a tuple of (str, NoneType) .. Any ideas?

    Only if its less than 50% at the beginning will we begin eliminating, if its more than 50% we will already have a winner..
  2. #2
  3. Contributing User
    Devshed Novice (500 - 999 posts)

    Join Date
    Feb 2005
    Posts
    611
    Rep Power
    65
    The problem is that interim dictionary
    {(A,B,D):3
    (A,B,D):2
    (B,D,A):4
    (D,B,A):3
    (B,A,D):1
    (D,A,B):1}
    would have a key collision at key (A,B,D). Keys have to stay unique.
    Real Programmers always confuse Christmas and Halloween because Oct31 == Dec25
  4. #3
  5. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,900
    Rep Power
    481
    Code:
    def eliminate(d):
        '''
            >>> d = {'ABCD':3,'ACBD':2,'BDCA':4,'DCBA':3,'CBAD':1,'CDAB':1,}
            >>> expect = {('A','B','D'):5,  # the Dietrich condition
            ...           tuple('BDA'):4,
            ...           tuple('DBA'):3,
            ...           tuple('BAD'):1,
            ...           tuple('DAB'):1,}
            ...
            >>> expect == eliminate(d)
            True
        '''
        # s is the set of all objects in the dictionary keys.
        s = set()
        for key in d:
            s = s.union(set(key))
        # count starting occurrences.
        counts = {o:0 for o in s}
        for (key,value,) in d.items():
            counts[key[0]] += value
        # find least used object (1 only)
        n = min(value for value in counts.values())
        for (k,v,) in counts.items():
            if v == n:
                lulo = k                          # least used lead object
                break
        else:
            return {}                # or maybe this is an error condition
        # form resulting dictionary
        result = {}
        for (key,v,) in d.items():
            newKey = tuple(k for k in key if k != lulo)
            if newKey in result: # One way to apply the Dietrich condition
                result[newKey] += v
            else:
                result[newKey] = v
        # and return it
        return result
    [code]Code tags[/code] are essential for python code and Makefiles!
  6. #4
  7. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2012
    Posts
    44
    Rep Power
    2
    Is there an easier way of understanding this? because that code looks advance... also.

    I want the last remaining party.. but this code seems too long

    Please help
  8. #5
  9. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,900
    Rep Power
    481
    I did think of a direct algorithm, which I offer without proof, (and written in j). First, understand how to use eliminate. Call it repeatedly until the key length is reduced sufficiently. This hidden comment
    # find least used object (1 only)
    indicates that the function drops only one object from the keys per call.
    Code:
    >>> d = {'ABCD':3,'ACBD':2,'BDCA':4,'DCBA':3,'CBAD':1,'CDAB':1,}
    >>> eliminate(d)
    {('B', 'D', 'A'): 4, ('A', 'B', 'D'): 5, ('D', 'A', 'B'): 1, ('B', 'A', 'D'): 1, ('D', 'B', 'A'): 3}
    >>> eliminate(eliminate(d))
    {('B', 'A'): 8, ('A', 'B'): 6}
    >>> eliminate(eliminate(eliminate(d)))
    {('B',): 14}
    >>> eliminate(eliminate(eliminate({'ABCD':3,'ACBD':2,'BDCA':4,'DCBA':3,'CBAD':1,'CDAB':1,})))
    {('B',): 14}
    >>> ##### found your answer B
    >>> ##Now try to rank ABC and D
    >>> eliminate(eliminate({'ACD':3,'ACD':2,'DCA':4,'DCA':3,'CAD':1,'CDA':1,})) # remove B and try again
    {('C',): 7}
    >>> eliminate({'AD':3,'AD':2,'DA':4,'DA':3,'AD':1,'DA':1,})  # remove C, try again
    {('D',): 2}
    >>> # remove D, leaving A.  The ranking becomes BCDA
    >>>
    The direct algorithm (which as of yesterday I thought didn't work. Today I see it works for your example.) I'll explain the algorithm with two of your test dictionary entries:

    'ABCD':3, 'BDCA':4,

    Assign weights to the objects in the key by position and multiply by the value
    Code:
    In 'ABCD':3,
    A gets 4  *  3  =  12
    B gets 3  *  3  =   9
    C gets 2  *  3  =   6
    D gets 1  *  3  =   3
    
    for 'BDCA':4
    B gets 4  *  4  =  16
    D gets 3  *  4  =  12  D is 2nd.  Assign weight 3.  d['BDCA'] is the factor 4
    C gets 2  *  4  =   8
    A gets 1  *  4  =   4
    Find a value for each object by sum over all occurrences:
    A 16 = 12+4
    B 25 = 16+9
    C 14 = 8+6
    D 15 = 12+3

    Here's the verb and example. At the end you'll see that it determines the order BCDA.
    Code:
       rankThem=: monad define
    KEYS=. 0 {::"1 y  NB. Array of keys
    FREQ=. 1 {::"1 y  NB. Array of values
    O=. ~. , KEYS     NB. O is the set of objects in the keys
    WEIGHTS=. KEYS (#@:] - i."1) O
    R=. FREQ +/ .* WEIGHTS
    O ;&:,. R
    )
       [D=: ('ABCD';3),('ACBD';2),('BDCA';4),('DCBA';3),('CBAD';1),:('CDAB';1)
    ┌────┬─┐
    │ABCD│3│
    ├────┼─┤
    │ACBD│2│
    ├────┼─┤
    │BDCA│4│
    ├────┼─┤
    │DCBA│3│
    ├────┼─┤
    │CBAD│1│
    ├────┼─┤
    │CDAB│1│
    └────┴─┘
    
       rankThem D
    ┌─┬──┐
    │A│31│
    │B│39│
    │C│37│
    │D│33│
    └─┴──┘

    Comments on this post

    • Winters agrees
    Last edited by b49P23TIvg; November 26th, 2012 at 09:51 AM.
    [code]Code tags[/code] are essential for python code and Makefiles!
  10. #6
  11. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2012
    Posts
    44
    Rep Power
    2
    Originally Posted by b49P23TIvg
    I did think of a direct algorithm, which I offer without proof, (and written in j). First, understand how to use eliminate. Call it repeatedly until the key length is reduced sufficiently. This hidden comment
    # find least used object (1 only)
    indicates that the function drops only one object from the keys per call.
    Code:
    >>> d = {'ABCD':3,'ACBD':2,'BDCA':4,'DCBA':3,'CBAD':1,'CDAB':1,}
    >>> eliminate(d)
    {('B', 'D', 'A'): 4, ('A', 'B', 'D'): 5, ('D', 'A', 'B'): 1, ('B', 'A', 'D'): 1, ('D', 'B', 'A'): 3}
    >>> eliminate(eliminate(d))
    {('B', 'A'): 8, ('A', 'B'): 6}
    >>> eliminate(eliminate(eliminate(d)))
    {('B',): 14}
    >>> eliminate(eliminate(eliminate({'ABCD':3,'ACBD':2,'BDCA':4,'DCBA':3,'CBAD':1,'CDAB':1,})))
    {('B',): 14}
    >>> ##### found your answer B
    >>> ##Now try to rank ABC and D
    >>> eliminate(eliminate({'ACD':3,'ACD':2,'DCA':4,'DCA':3,'CAD':1,'CDA':1,})) # remove B and try again
    {('C',): 7}
    >>> eliminate({'AD':3,'AD':2,'DA':4,'DA':3,'AD':1,'DA':1,})  # remove C, try again
    {('D',): 2}
    >>> # remove D, leaving A.  The ranking becomes BCDA
    >>>
    The direct algorithm (which as of yesterday I thought didn't work. Today I see it works for your example.) I'll explain the algorithm with two of your test dictionary entries:

    'ABCD':3, 'BDCA':4,

    Assign weights to the objects in the key by position and multiply by the value
    Code:
    In 'ABCD':3,
    A gets 4  *  3  =  12
    B gets 3  *  3  =   9
    C gets 2  *  3  =   6
    D gets 1  *  3  =   3
    
    for 'BDCA':4
    B gets 4  *  4  =  16
    D gets 3  *  4  =  12  D is 2nd.  Assign weight 3.  d['BDCA'] is the factor 4
    C gets 2  *  4  =   8
    A gets 1  *  4  =   4
    Find a value for each object by sum over all occurrences:
    A 16 = 12+4
    B 25 = 16+9
    C 14 = 8+6
    D 15 = 12+3

    Here's the verb and example. At the end you'll see that it determines the order BCDA.
    Code:
       rankThem=: monad define
    KEYS=. 0 {::"1 y  NB. Array of keys
    FREQ=. 1 {::"1 y  NB. Array of values
    O=. ~. , KEYS     NB. O is the set of objects in the keys
    WEIGHTS=. KEYS (#@:] - i."1) O
    R=. FREQ +/ .* WEIGHTS
    O ;&:,. R
    )
       [D=: ('ABCD';3),('ACBD';2),('BDCA';4),('DCBA';3),('CBAD';1),:('CDAB';1)
    ┌────┬─┐
    │ABCD│3│
    ├────┼─┤
    │ACBD│2│
    ├────┼─┤
    │BDCA│4│
    ├────┼─┤
    │DCBA│3│
    ├────┼─┤
    │CBAD│1│
    ├────┼─┤
    │CDAB│1│
    └────┴─┘
    
       rankThem D
    ┌─┬──┐
    │A│31│
    │B│39│
    │C│37│
    │D│33│
    └─┴──┘
    Okay, but howcome u are getting such large sums for each letter when the values are so less?? I just need to understand that part.. Thanks for your help.. I think i do understand this a little more
  12. #7
  13. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,900
    Rep Power
    481
    Code:
     consider D
    │ABCD│3│   1*3
    │ACBD│2│ + 1*2
    │BDCA│4│ + 3*4
    │DCBA│3│ + 4*3
    │CBAD│1│ + 1*1
    │CDAB│1│ + 3*1
    -----------------
                33
    [code]Code tags[/code] are essential for python code and Makefiles!

IMN logo majestic logo threadwatch logo seochat tools logo