Login

Real shuffle function

Author:
marinho
Posted:
May 20, 2010
Language:
Python
Version:
1.2
Score:
0 (after 0 ratings)

This function solve the issue of random.shuffle that is based only on randomized shuffling (that's not a real shuffling, because many times items returned aren't shuffled enough).

This function make a randomized shuffle and after this loops long the list resorting to avoid two items with a same value in a given attribute.

When shuffling is over and there are duplicates, they are leftover to the end (and you can remove them if you set 'remove_duplicates' to True)

Run it in a separated file to see it in action.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
import random

try:
    set
except:
    from sets import Set as set

def _get_value(obj, attr):
    if not attr:
        return obj
    elif isinstance(obj, dict):
        return obj[attr]
    else:
        return getattr(obj, attr)

def all_are_duplicates(items, attr=None):
    """Returns True if all given items has the same value for a given attribute"""
    return len(set([_get_value(item, attr) for item in items])) == 1

def real_shuffle(l, attr=None, remove_duplicates=False):
    """This function make a 'real' shuffle of a list, without only depend on a
    randomized shuffling but looping along the list to make sure they aren't
    repeating a given attribute."""

    # Make a copy of the list
    ret = list(l)

    # Just returns it if has 1 or less items
    if len(ret) <= 1:
        return ret

    # Randomic shuffling
    random.shuffle(ret)

    # Loop along the list to make 'real' shuffle
    new_list = []
    while not all_are_duplicates(ret, attr):
        for cur_index in range(len(ret)):
            if not new_list or _get_value(ret[cur_index], attr) != _get_value(new_list[-1], attr):
                new_list.append(ret.pop(cur_index))
                break

    new_list += ret

    # Remove the duplicates
    if remove_duplicates:
        while len(new_list) > 1 and  _get_value(new_list[-1], attr) == _get_value(new_list[-2], attr):
            new_list.pop(-1)

    return new_list

if __name__ == '__main__':
    class Animal(object):
        name = str()
        kind = str()

        def __init__(self, name, kind):
            self.name, self.kind = name, kind

        def __str__(self):
            return '%s/%s'%(self.name, self.kind)

    animals = [
        Animal('a1', 'lion'),
        Animal('b1', 'tiger'),
        Animal('a2', 'lion'),
        Animal('a3', 'lion'),
        Animal('a5', 'lion'),
        Animal('c1', 'lion'),
        Animal('a4', 'lion'),
        Animal('b2', 'tiger'),
        Animal('b3', 'tiger'),
        Animal('a6', 'lion'),
        Animal('c2', 'cat'),
        Animal('b4', 'tiger'),
    ]

    print all_are_duplicates(animals, 'kind'), all_are_duplicates(animals[2:5], 'kind')

    print '\n\nOriginal:'
    print '  ', ', '.join(map(str, animals))

    print '\n\nShuffled by Python'
    animals2 = list(animals)
    random.shuffle(animals2)
    print '  ', ', '.join(map(str, animals2))

    print '\n\nShuffled by me'
    animals3 = real_shuffle(animals, 'kind')
    print '  ', ', '.join(map(str, animals3))

    print '\n\nShuffled by me - removing duplicates'
    animals3 = real_shuffle(animals, 'kind', True)
    print '  ', ', '.join(map(str, animals3))

    print '\n\n'

More like this

  1. Template tag - list punctuation for a list of items by shapiromatron 11 months, 1 week ago
  2. JSONRequestMiddleware adds a .json() method to your HttpRequests by cdcarter 11 months, 2 weeks ago
  3. Serializer factory with Django Rest Framework by julio 1 year, 6 months ago
  4. Image compression before saving the new model / work with JPG, PNG by Schleidens 1 year, 7 months ago
  5. Help text hyperlinks by sa2812 1 year, 7 months ago

Comments

Please login first before commenting.