CODEWITHSUNDEEP
pythonrecursionsetgeneratorsequence
John Carter
John Carter

Reputation: 7005

Calculating the Nth Sequence of Length M in Python

I'm writing a library/utility I'm going to be using for verification. I'll have a set of elements and a system-under-test that consumes them in some order. The set represents all possible inputs, and the system will receive a finite sequence of those elements.

As the set of finite sequences will be infinite I'm not looking to calculate all sequences for a set, but instead envision using a python generator to accomplish the following:

def seq(s): # s is a set
  length = 0
  nth = 0
  # r = calculate nth sequence of length
  # if there are no more sequences of length, length += 1
  # else n += 1, yield r

I'll eventually extend this to injective and bijective sequences, but for now elements of the set can appear any number of times.

Are generators the best way to approach this? Does using a generator like this eliminate any simplicity gained from recursion? Can anyone point me toward any itertools (or other modules) short cuts that might help me?

Upvotes: 1

Views: 244

Answers (1)

senderle
senderle

Reputation: 151077

It sounds like you're looking for itertools.product. I believe this will do what you're asking:

def seq(s):
    length = 1
    while True:
        for p in itertools.product(s, repeat=length):
            yield p
        length += 1

Now you can do things like this:

>>> zip(range(10), seq(set((1, 2, 3))))
[(0, (1,)), (1, (2,)), (2, (3,)), (3, (1, 1)), (4, (1, 2)), 
 (5, (1, 3)), (6, (2, 1)), (7, (2, 2)), (8, (2, 3)), (9, (3, 1))]

Or this:

>>> test_seq = itertools.izip(itertools.count(), seq(set((1, 2, 3))))
>>> for i in range(10):
...     next(test_seq)
... 
(0, (1,))
(1, (2,))
(2, (3,))
(3, (1, 1))
(4, (1, 2))
(5, (1, 3))
(6, (2, 1))
(7, (2, 2))
(8, (2, 3))
(9, (3, 1))

This can also be compressed further, using other itertools:

>>> from itertools import chain, product, count
>>> s = set((1, 2, 3))
>>> test_seq = chain.from_iterable(product(s, repeat=n) for n in count(1))
>>> zip(range(10), test_seq)
[(0, (1,)), (1, (2,)), (2, (3,)), (3, (1, 1)), (4, (1, 2)), (5, (1, 3)), 
 (6, (2, 1)), (7, (2, 2)), (8, (2, 3)), (9, (3, 1))]

Upvotes: 2

Related Questions