CODEWITHSUNDEEP
python
Meghna Mittal
Meghna Mittal

Reputation: 21

How to count the number of sequences of n numbers where no two adjacent numbers are the same?

Disclaimer: I am new to python/coding so this may come across as too basic for some of you experts.

I need to optimize the solution to the problem of finding the number of sequences of n numbers where no two adjacent numbers in a sequence are the same and the values in the sequence could be any number between 1 and k (k could be smaller or bigger than n).

I tried to find this using a brute force approach by first finding the sequences and then counting them but the solution is clearly not optimized and hence giving memory issues.

Here is a code that makes use of itertools library in python:

def notsame(nums): 
    return all(num1 != num2 for num1, num2 in zip(nums, nums[1:])) 
def sequence_count(n, k):
    count = 0
    a = list(range(1, k+1))
    for item in list(it.product(a, repeat = n)):
        if notsame(list(item)):
           count += 1
#taking the modulo as the number of sequences could get really large.
   count = count % (10**10+7)   
   print(count)

For example, if we are given a value of n = 3 and k = 2 then the possible sequences that fits the required criterion are (1, 2, 1), (2, 1, 2) so the count is 2.

Upvotes: 2

Views: 106

Answers (2)

576i
576i

Reputation: 8372

If you insist on counting them and maybe need the results, recursion might help.

def ap(n, k):
    if n==1:
        for e in range(k):
            yield [e + 1]
    else:
        for e in range(k):
            for e2 in ap(n - 1, k):
                tmp = [e + 1] + e2
                for i in range(len(tmp) - 1):
                    if tmp[i] == tmp[i + 1]:
                        break
                else:        
                    yield tmp

# count    
print(sum(1 for v in ap(4, 3)))
# result
print(list(ap(4, 3)))

This is a bit better than your approach memory wise, but still extremely slow.

Upvotes: 1

mitoRibo
mitoRibo

Reputation: 4548

This has a closed form solution where it is much easier to count the number of possibilities than to list all of them, so this feels more like a counting problem than a coding problem.

We are going to count how many possibilities we have at each position n and then multiply them together.

In the example you've given where n=3, k=2 then

  • For the 1st position there are 2 options (1 or 2)
  • The 2nd position only has 1 option (can't be the same as whatever is placed at pos 1)
  • The 3rd position also only has 1 option too (can't be the same as pos 2)

So the formula when n=3 is:

k*(k-1)*(k-1) = 2, when k=2

We can generalize this to: counts = k*(k-1)**(n-1)

If you do need to be able to list all the possibilities rather than just counting, then this answer isn't enough

Upvotes: 2

Related Questions