Doubt regarding Permutations

1

Hey , i have a doubt regarding permutations . In some problems , we have to remove certain value from total permutations to get the resultant answer ( Example : permutations of string such that no two characters stay together ) . Theoritically , we solve such problems by removing the unnecessary permutations from the total number of permutations . But calculating the total permutations answer is impossible while writing code as the number can be very large . Can anyone please suggest me some approaches or resources to tackle such questions

Thanks in advance :slight_smile:

2

isn’t that just optimisation in short?
Like suppose we do Best First Search, we avoid unnecessary permutations by checking the cost to reach the global optimum answer…

1 Like
3

Yeah , but this is a bit different

https://world4tech.com/mockvita-2019-round-2-question-bad-permutations/

Here’s the problem

4

Can’t think of anything else besides a brute force approach… :slightly_frowning_face:
I guess there’s a pattern.
Like 9 has [1,3,9] and 4 has [1,2,4]
they both will have the same answer…

6

I did solve the problem . There is a reccurrence relation . It took me around 3 hours to crack logic :neutral_face:. So, i want to know whether there is any other shortcut solution :slight_smile:

Code

from sys import stdin,stdout
from math import sqrt
def factor(n):
low=1
fact=0
high=sqrt(n)
while low<=high:
if n%low==0:
if n//low==high:
fact+=1
else:
fact+=2
low+=1
return fact
bad_permut=1
values=[]
for i in range(0,70):
if i==0:
values.append(0)
elif i==1:
values.append(0)
elif i==2:
values.append(1)
else:
values.append(((i-1)*values[i-1])+bad_permut)
bad_permut=(i-1)*values[i-1]
def compute():

for _ in range(int(input())):
    n=int(stdin.readline())
    x=factor(n)
    stdout.write(str(values[x]))
    print()

if name==“main”:
compute()

7

This will give TLE?
And is my theory correct or wrong?

8

Brute force didn’t work because the solution is bound to be recursive in nature

1 Like
9

was wondering the same thing

10

this is the program for the above question:

import math
import sys
sys.setrecursionlimit(1500)

dp = {}

def getDivisorCount(n):
rootN = int(math.sqrt(n))
divisors = []
for num in range(1, rootN + 1):
if(n % num == 0):
a = int(n / num)
if a * a == n:
divisors.append(a)
else:
divisors.append(num)
divisors.append(a)

return len(divisors)

def validPermutation(n):
if(n == 1):
return 1
if(n == 2):
return 1
if(n == 3):
return 3
ans = 0
if n - 1 in dp:
ans += dp[n - 1]
else:
dp[n - 1] = (n - 1) * validPermutation(n - 1)
ans += dp[n - 1]
if n - 2 in dp:
ans += dp[n - 2]
else:
dp[n - 2] = (n - 2) * validPermutation(n - 2)
ans += dp[n - 2]
dp[n] = ans
return ans

t = int(input())
for _ in range(t):
n = int(input())
divisorCount = getDivisorCount(n)
print(validPermutation(divisorCount))