'''http://stackoverflow.com/questions/8347815/generating-combinations-of-a-string-not-permutations/8349358#8349358'''


def combine0(s):
    out = []
    length = len(s)
    def loc(start):
        for i in range(start, length):
            out.append(s[i])
            print out
            if (i < length-1):
                loc(i+1)
            del out[-1]
    loc(0)


def combine1(s):
    #A bit faster than combine2
    out = []
    length = len(s)
    def loc(start):
        for i in range(start, length):
            out.append(s[i])
            yield out
            if (i < length-1):
                for els in loc(i+1):
                    yield els              
            del out[-1]
    for v in loc(0):
        yield v


def combine2(s):
    #A bit slower than combine1
    length = len(s)
    def gen(start, prepending=[]): #recursive generator
        if start == length-1:
            yield prepending + [s[start]]
        else:
            for i in range(start,length):
                current = prepending + [s[i]] #save the current list for reusing
                yield current
                for els in gen(i+1,current):
                    yield els
    for v in gen(0):
        yield v



if __name__ == '__main__':
    s = "wxyz"

    print('combine0')
    combine0(s)

    print('')
    print('combine1')
    for v in combine1(s):
        print(v)

    print('')
    print('combine2')    
    for v in combine2(s):
        print(v)




    print('')
    print('Efficiency testings')    
    import timeit
    import __main__

    N = 1 #Number of executions

    s = 'a'*16

    f_names = ['combine1','combine2']

        
    for f_name in f_names:
        
        init = '''from __main__ import {name}, s'''.format(name=f_name)
        t = timeit.Timer(stmt='[i for i in {name}(s)]'.format(name=f_name),
                         setup=init)

        time = t.timeit(N)
        print('{name}: {time}'.format(name=f_name,time=time))