CODEWITHSUNDEEP
pythonrecursion
Matt Stave
Matt Stave

Reputation: 3

generating sequences with arbitrary distance between consecutive members

I'm trying to write a function that will take as input length L and distance D (both integers > 1) and output all possible sequences that fit the following parameters:

  1. start with the number 1
  2. have L elements
  3. have a distance of 1 to D between each element and the following element

So, for L = 4 and D = 2, the possible sequences would be:

1 2 3 4   (distance of 1 between each consecutive element)  
1 2 3 5  
1 2 4 5  
1 2 4 6  
1 3 4 5  
1 3 4 6  
1 3 5 6  
1 3 5 7   (distance of 2 between each consecutive element)

Or, for L = 3 and D = 3, the possible sequences would be:

1 2 3   (distance of 1 between each consecutive element)  
1 2 4  
1 2 5  
1 3 4  
1 3 5   (distance of 2 between each consecutive element)  
1 3 6  
1 4 5  
1 4 6  
1 4 7   (distance of 3 between each consecutive element)

From hand-coding several of these, the number of possible sequences seems to be D ** (L-1). At first I only needed 2\**7, and 128 sequences wasn't that difficult to create by hand. However, I now need 3**7, and possibly even larger amounts, so I need to write a function.

Python is the language I'm learning. Recursion seems to be the way to do it, but I've only practiced on simple recursion, and I'm stuck as to how precisely to write this. As best as I can work out, I need a function that calls itself from within a for-loop. Does this make sense? Directions to similarly structured functions would be greatly appreciated, as well.

Upvotes: 0

Views: 68

Answers (3)

englealuze
englealuze

Reputation: 1663

The point of recursion is not only formalizing the code in a recursive way, but orientating your mind in a recursive way. Compare carefully the results for length 3 and length 4 with distance 2.

a. Length 3

1 2 3
1 2 4
1 3 4
1 3 5

b. Length 4

1 2 3 | 4
1 2 3 | 5
1 2 4 | 5
1 2 4 | 6
1 3 4 | 5
1 3 4 | 6
1 3 5 | 6
1 3 5 | 7

In the result of length 4, the right side of | is just the result of length 3. That means the result of N length can be derived from N - 1 length.

Assume that we have already a procedure to solve k - 1 length solve_part(k-1), by extending the result of k-1 to next length k next_len(solve_part(k-1) ...), this problem is naturally solved in a recursive way.

import itertools

def flatmap(func, *iterable):
    return itertools.chain.from_iterable(map(func, *iterable))

def next_distance(eachlist, D):
  return map(lambda eachdis: eachlist + [eachlist[-1] + eachdis], range(1,D+1))

def next_len(L,D):
  return flatmap(lambda eachlist: next_distance(eachlist, D), L)

def solve_it(leng,dis):
  def solve_part(k):
    if k == 0:
      return [[]]
    elif k == 1:
      return [[1]]
    else:
      return next_len(solve_part(k-1),dis)
  return solve_part(leng)

result=solve_it(4,2)

print([[i for i in j] for j in result])

Upvotes: 0

Francisco
Francisco

Reputation: 11496

You can use itertools.product and itertools.accumulate to achieve your desired function:

import itertools

def f(l, d):
    for sub in itertools.product(range(1, d+1), repeat=l-1):
        yield tuple(itertools.accumulate((1,) + sub))

for l in f(4, 2):
    print(l)

(1, 2, 3, 4)
(1, 2, 3, 5)
(1, 2, 4, 5)
(1, 2, 4, 6)
(1, 3, 4, 5)
(1, 3, 4, 6)
(1, 3, 5, 6)
(1, 3, 5, 7)

Upvotes: 2

Gribouillis
Gribouillis

Reputation: 2220

Here is a quick and dirty implementation

def gen_seq(D, L):
    for uple in itertools.product(range(1, D+1), repeat=L-1):
        yield tuple(numpy.cumsum((1,) + uple))

Upvotes: 0

Related Questions