import random

# in: group as integer, number of persons (maximum group size)
# out: integer as binary string, char i corresponds to person i  
### if python >= 2.6:
# else:
bix = lambda n: n>0 and bix(n>>1).lstrip('0')+str(n&1) or '0'
bin = lambda n: "0b%s" % bix(n)
### endif
gbins = lambda g, np: "".join(reversed(bin(g).replace("0b", "").rjust(np, '0')))

# in: group as integer
# out: number of person in this group
gsize = lambda g: len([d for d in gbins(g, 0) if d == '1'])

# in: group as integer
# out: set of numbers matching persons in this group (e.g. set([0,1,5])
gset = lambda g: set([n for n, bit in enumerate(gbins(g, 0)) if bit == '1'])

# in: group as set/list of person numbers
# out: group as integer
gint = lambda g: sum([2 ** i for i in g])

def build_groups(npersons, gconf, rseed=None):
    """Build a list of person groups.
    
    @param npersons:
        number of persons to build groups for
    @param gconf:
        list with number of groups per group size (starting at 1) or a list of
        of groups (in which case we don't have to do anything)
    @keyword rseed:
        random seed for group sampling

    @return:
        a list of groups as integers (binary person presence representation)
        
    """
    if not isinstance(gconf[0], int):
        # gconf already is a list of groups
        return [gint(g) for g in gconf] 
    
    levels = []
    groups = range(2 ** npersons)
    
    random.seed(rseed)
    
    for lnum, lwidth in enumerate(gconf):
        
        lwidth = gconf[lnum]
    
        # get groups matching current level
        lgroups = [g for g in groups if gsize(g) == (lnum + 1)]
        
        clevel = set()                                      # current level
        plevel = levels and levels[-1].copy() or set([0])   # previous level
        while len(clevel) < lwidth:
            g = random.choice(lgroups)
            if g in clevel:
                continue
            plevel = plevel and plevel.copy() or set([0])
            for pg in plevel.copy():
                if gset(g) > gset(pg):
                    clevel.add(g)
                    plevel.remove(pg)
                    
        levels.append(clevel)
    
    groups = []
    for clevel in  levels:
        groups.extend(clevel)
    
    return groups