The question is to find number of valid sequences (A1,A2....AN) with given constraints:
- Value of Ai lies between 1 and 6 (1<= Ai <= 6)
- Two adjacent numbers should be coprime. For e.g. 2,4,.. sequence is not allowed
- If the value repeats in the sequence, then difference in their index should be greater than 2. For e.g. If K=4, (1,2,3,1) is a valid sequence while (1,3,4,3) is not a valid sequence
Note: N is given in the problem statement.
I could only think of a backtracking solution wherein each recursive call would try all numbers from 1 to 6 for the given Ai position.
This look like more of brute force way.
Could you please help with an optimal solution.
CodePudding user response：
What you have here is a graph search problem which can be solved using backtracking search and can be made to run even faster using memoization.
Defining the states
Following the rules in the question, the states are tuple where the first value in the tuple are the current number a_n and the previous number in the series a_{n-1} and the second value in the tuple is the length of the sequence, since the occurance of a number can be in an interval of 2 or more.
In addition, the forbidden states are states where the two numbers are not co-prime, this means that every permutation of the
number_set = [1, 2, 3, 4, 5, 6]
with the length of 2 is a valid state except the forbidden set which is:
forbidden_tuples = {(2,4), (2,6), (4,6), (3,6), (4,2), (6,2), (6,4), (6,3)}
Example: ((2,3), 5) is in state (2,3) with a needed sequence length of 5. In this case the following number can not be 2,3 (to keep distance of at least 2) or 6 (to keep adjacent numbers co-prime) so a total of thee subsequent states:
- ((3,1), 4)
- ((3,4), 4)
- ((3,5), 4)
Building the solution
The solution I will offer is a recursive DFE of the graph with memoization for time optimization. the solution is as follows:
import itertools
def count_seq(N, start_state=None, memoization=None):
"""
:param N:
:param start_state
:param memoization
:return: Rules:
1. a_i in {1,2,3,4,5,6}
2. Two adjacent numbers should be coprime. For e.g. 2,4,.. sequence is not allowed ( for the set {1,2,3,4,5,6} this means that (2,6),(2,4),(3,6),(4,6) are forbidden
3. repetitions with a distance >= 2
State are ordered as a 2 item tuple to remember the history: (a_{n-1} , a_n)
"""
if N == 1:
return 6
if memoization is None:
memoization = {}
count = 0
state_set = set() # Pending states which have not been explored yet
number_set = [1, 2, 3, 4, 5, 6]
forbidden_tuples = {(2,4), (2,6), (4,6), (3,6), (4,2), (6,2), (6,4), (6,3)}
if start_state is None: # Getting initial states
for subset in itertools.permutations(number_set, 2):
if subset in forbidden_tuples:
pass
else:
state_set.add((subset, N))
else: # checking all possible next states and appending to queue with 1 less length
for ii in number_set:
if ii in start_state or (ii, start_state[-1]) in forbidden_tuples:
pass
else:
state_set.add(((start_state[1:] tuple([ii])), N-1))
# for each possible next state
for state in state_set:
if state[1] <= 2:
count = 1
elif state in memoization: # checking if we computed this already
count = memoization[state]
else: #we did not compute this, doing the computation
memoization[state] = count_seq(state[1], state[0], memoization)
count = memoization[state]
return count
Explenation
If the wanted length is 1, reutn 6 since either of the numbers can be in the 1st location.
We see if the start state is
Nonewe assume that this is the initial calling, and so we create all the possible none forbidden permutations of the numbers with length 2. otherwise, we create a set of all the possible next states.For each possible next state, we check:
2.1. if the length required is 2: we increase the count by 1 since this is a valid state
2.2. If the length is more than 2, we check is we already computed this state before in the
memoizationdictionary. If we did we pull the count value from the dictionary and use that, otherwise we call the function recursively with the starting state and the wanted sequence length.
Timing
When running this function with memoization disabled we get for N=200:
%timeit count_seq_slow(200)
199 ms ± 9.63 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit count_seq(200)
13.6 ms ± 833 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
When increasing to N=2000 we get:
%timeit count_seq_slow(2000)
3.54 s ± 374 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit count_seq(2000)
147 ms ± 7.02 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
CodePudding user response：
We can use the fact that only 6 possible digits can be used to construct numbers.
- Consider a lookup table
dp[i][j][k], which is basicallycount of i-digit numbers with the i-th digit as j, (i-1)th digit as k. - Create a mapping of all valid co-primes for each digit. Something like
{2: [1,3,5], 3: [1,2,4,5], 6: [1,5]}... - Base cases:
dp[0] = 0 for all j,k,dp[1] = 1 for all j,k - Filling up the table should be relatively straighforward now.
for i in range 2 to n:
for j in range 1 to 6:
for k in range 1 to 6
if j and k are coprime, dp[i][j][k] = 0
else, dp[i][j][k] = summation(dp[i-1][k][l]) where l is in range [1,6] AND l!=j
# this ensures a min gap of 3 and maintains co-primality of adjacent numbers
- Final answer =
sum(dp[N][1..6])
This has a time and space complexity of O(N*6*6) ~ O(N).
CodePudding user response：
Let K[n, d1, d2] be the number of valid sequences of length n such that the sequence remains valid if d1, d2 appear just before. Or equivalently, the number of valid sequences of length n 2 that start with d1, d2.
There's a recurrence relation that K satisfies:
K[n, d1, d2] = 0 if d1 is not coprime to d2.
K[0, d1, d2] = 1
K[n, d1, d2] = sum(K[n-1, d2, d] for d=1..6 - {d1, d2})
This K can be calculated using a bottom-up dynamic program, or memoization.
The original problem can be solved for n>=2, using this:
S[n] = sum(K[n-2, d1, d2] for d1=1..6, d2=1..6)
For n<=2, we have S[0] = 1 and S[1] = 6.