Maths behind itertools combinations with replacement
I need to find the total number of arrays using n and k inputs.. n=int(input()) k=int(input() N denotes the maximum number range of array elements K denotes the length of array I need to find all possible arrays using the inputs N and K a,a,a,... a[k] where every number a[i] is in range from 1 to N and moreover a[i+1] should be divisible by a[i] where 1< i <= K Sample case : n=2 k=2 output : [1,1], [1,2], [2,2] [2,1] is invalid because a[i+1] is not divisible by a[i] so total number of arrays are 3 ------------------------------------------------------------------------ without caring the condition [a+1] % a[i] = 0 I use itertools.combinations_with_replacement in my code and using formula I found out the total number of possible arrays. formula : k+(n-1)! ---------------- k! (n-1)! I used formula because when we use bug nunbers as input N and K then time complexity increases.. I need formula for condition also a[i+1] % a[i]
7/14/2021 11:49:57 AMRatnapal Shende
12 AnswersNew Answer
# try this: def combinations_count(N,K): last = range(1,N+1) for _ in range(K-1): last = ( v for a in last for v in range(a,N+1,a) ) return sum(1 for _ in last) n = int(input()) k = int(input()) if K<1 or N<1: print(0) elif l==1 or n==1: print(n) else: print(combinations_count(n,k))
visph Thank you so much! 🎉☺️🎊 please explain math behind it sir I am weak in maths..
here is my attempt --> https://code.sololearn.com/c8fws6qiJh87/?ref=app
Ratnapal Shende wrote: "[1,2] is invalid because a[i+1] is not divisible by a[i]"... but a[i+1] == 2, a[i] == 1 and 2 is divisible by 1... did you mean the converse? a[i] is not divisible by a[i+1]? and so condition must be a[i] % a[i+1] == 0?
visph i mean [1,2] # valid here 2 should be divisible by 1 [2,4] #valid 4 should be divisible by 2 [9,3] # invalid because 3 is not divisible by 9 when k is 3 --> [2,4,8] # valid because 8 is divisible by 4 and 4 is divisible by 2 [3,5,10] # invalid 10 is divisible by 5 but 5 is not divisible by 3 so this array is invalid.. like this I need a formula which tells the number of all the possible arrays..
you should edit your sample case in question description as it state that [1,2] is invalid ^^ anyway,,not sure at all that there's a formula as you expect... if time duration is a problem, I guess you must find a smarter algorithm to compute the solution, but not necessarly by finding a formula ;P however, my math skills are not bad, but not enough to give you the expected formula if only it exists :(
maybe you could avoid using itertools combinations_with_replacement function and instead generate yourself them (without storing and only counting) only for values that match your condition...
visph case edited ! please give me any solution for that please.. Atleast, If i give input n=100 k=3 My system should say the possible numbers of arrays without getting stuck ... 😛 edit: OK I will try...
Ratnapal Shende for: [a0,a1,..,an] a0 < a1 < ... < an (a[i] < a[i+1]) and a[i+1] = x*a[i] (wich imply previous if x >= 1) with x as int number
visph i am not getting what to do... my brain is not working 😢 I read code of combination in docs but I am unable to implement according to my need. please help me sir !
if a[i] == x then possible values of a[i+1] are: [x, x*2, x*3, ... x*n] for x<=N and x*n <= N (max number range of array elements)
no much math behind... instead of generating all combinations based on rule previously explained, I generate (and keep), only last a[i] as generator... with last list (generator) I get length of elements by adding 1 for each element (iterate only once to get count) ;)