Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
965 views
in Technique[技术] by (71.8m points)

python - The Concept Behind itertools's product Function

so basically i want to understand the concept of product() function in itertools. i mean what is the different between yield and return. And can this code be shorten down anyway.

    def product1(*args, **kwds):
        pools = map(tuple, args) * kwds.get('repeat', 1)
        n = len(pools)
        if n == 0:
            yield ()
            return
        if any(len(pool) == 0 for pool in pools):
            return
        indices = [0] * n
        yield tuple(pool[i] for pool, i in zip(pools, indices))
        while 1:
            for i in reversed(range(n)):  # right to left
                if indices[i] == len(pools[i]) - 1:
                    continue
                indices[i] += 1
                for j in range(i+1, n):
                    indices[j] = 0
                yield tuple(pool[i] for pool, i in zip(pools, indices))
                break
            else:
                return
See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

I would highly recommend using the well established and tested itertools standard module. Reinventing the wheel is never advisable as a programmer. That said, I would start by taking a look at the product() function in itertools.

As for not using itertools(), this problem is essentially a cartesian product problem (n-permutations with duplicates allowed). This is where recursion helps us! One possible solution below:

Method Body:

result = []
def permutations(alphabet, repeat, total = ''):
    if repeat >= 1:
        for i in alphabet:
            # Add the subsolutions.     
            permutations(alphabet, repeat - 1, total + i)  

    else:
        result.append(total)
    return result

And when we call with permutations()

Sample Outputs:

permutations('ab', 3) ->
$ ['aaa', 'aab', 'aba', 'abb', 'baa', 'bab', 'bba', 'bbb']
permutations('ab', 3) ->
$ ['aaa', 'aab', 'aac', 'aba', 'abb', 'abc', 'aca', 'acb', 'acc', 'baa',
  'bab', 'bac', 'bba', 'bbb', 'bbc', 'bca', 'bcb', 'bcc', 'caa', 'cab', 
  'cac', 'cba', 'cbb', 'cbc', 'cca', 'ccb', 'ccc']
permutations('ab', 1) ->
$ ['a', 'b']

How does it work?

This method works by nesting for loops in a recursive manner repeat-times. We then accumulate the result of the sub-solutions, appending to a result list. So if we use 4 as our repeat value, out expanded iterative trace of this problem would look like the following:

for i in alphabet:
    for j in alphabet:
        for k in alphabet:
            for l in alphabet:
                result.append(i + j + k + l)

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...