Maths behind itertools combinations with replacement

Question

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]

Answer 1

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

Answer 2

visph Thank you so much! 🎉☺️🎊
please explain math behind it sir I am weak in maths..

Answer 3

here is my attempt -->

https://code.sololearn.com/c8fws6qiJh87/?ref=app

Answer 4

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?

Answer 5

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

Answer 6

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 :(

Answer 7

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

Answer 8

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

Answer 9

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

Answer 10

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 !

Answer 11

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)

Answer 12

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