CODEWITHSUNDEEP
arraysalgorithm
sheetaldharerao
sheetaldharerao

Reputation: 492

Find total number of ways possible to create an array of size M

Suppose I have M = 2 and N = 5 and K = 2 where
M = size of array
N = Maximum number that can be present as an array element
K = Minimum number that can be present as an array element.
So how do I find the number of possible ways to create an array using the above conditions. Also the current number should be not be greater than the previous element.

The arrays created using the above conditions are [5,5],[5,4],[5,3],[5,2],[4,4],[4,3],[4,2],[3,3],[3,2],[2,2] i.e 10 array can be created from the above conditions.

I tried doing it by using combinations and factorials, but not getting the desired output. Any help would be appreciated.

Upvotes: 0

Views: 250

Answers (2)

Tom Ron
Tom Ron

Reputation: 6181

Assuming you are just interested in the number of combinations the formula is -

(N-K+M)!/(M!(N-K+1)!)

See more here

Upvotes: 2

Amadan
Amadan

Reputation: 198334

This is known as a combinations_with_replacement: combination because the order doesn't matter (or it would be a permutation), and with replacement because elements can be repeated, like [5, 5].

list(itertools.combinations_with_replacement(range(2, 6), 2))
# [(2, 2), (2, 3), (2, 4), (2, 5), (3, 3), (3, 4), (3, 5), (4, 4), (4, 5), (5, 5)]

If you want the exact ones you listed, you will have to reverse each element, and the list itself.

list(reversed([tuple(reversed(element)) for element in itertools.combinations_with_replacement(range(2,6), 2)]))

Upvotes: 1

Related Questions