# 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[1],a[2],a[3],... 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 AM

Ratnapal Shende12 Answers

New 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..

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) ;)