I am facing this problem in one or other way during my research(Graph labeling>Magic labeling). What will be the best logic to make a computer programme? I have tried this but it doesn't work properly for large values of m,n and k.
Dear Siddhant Trivedi,
Let S=[1,2,3...,n]; is an array of elements and m=2 then
for(int i=0;i
Python Code using itertools library :
from itertools import combinations
def find(arr,r):
l=list(combinations(arr,r))
res=[]
s=0
for i in l:
for j in range (0,r):
s=s+i[j]
if s == K:
res.append(i)
s=0
print(l)
print(res)
-------------------------------------------------------------------
S=[1,2,3,4,..........]
r=int(input("Enter m value"))
K=int(input("Enter k value"))
find(S,r,K)
I will recommend to ask this Q at Stack Overflow community too:
https://stackoverflow.com/
Dear Siddhant Trivedi ,
The itertools library of Python will be of most use it you are interested in all combinations from the Set S where the sum of the elements is equal to k. A complete sample code is attached herewith.
My Attempt: It doesn't work for large values.
from itertools import combinations def findTriplets(lst, key): def valid(val): return sum(val) == key return list(filter(valid, list(combinations(lst, m)))) # Driver Code n = int(input("Enter a value of n: ")) lst = [i for i in range(1,n)] print(findTriplets(lst, k))
Hi Siddhant Trivedi , it would be better if you could tell us what is the value of 'n' that you consider to be large. The algorithm is capable of handling large values but keep in mind that you'll definitely run out of memory when 'n' becomes sufficiently large.
The number of combinations of n things taken m at a time is n!/((n-m)!m!).
So, if n is 1000 and m is 3, list(combinations(lst, m)) will be a list of approx 1.1E8 elements (occupying approx 400MB RAM), and if n is 4000 and m is 3, it will be approx 1.1E10 elements (occupying approx 40GB RAM)
Being a Mathematician so, I don't know much about it. But I want ask you Anoop Ebey Thomas few questions :
(1) Is it possible to develop this algorithm so that it can be run with low memory?
(2) If I am writing an algorithm, how do I know, how much memory it will be consumed by RAM?
(3) As you said if the value of n=1000 and m=3 then the system occupying approx 400MB RAM. As far as I have observed, it will also depend on the values of m and k. What happen if we increase m and k to a certain range?
(4) What happens if we take If we take n=1000, m=500 and k=1,25,250=sum of first 500 natural numbers or we may take the value of k in the range (125250, 375250)?
Hi Siddhant Trivedi , I will try to answer your questions as comprehensively as I can. This might be a slightly longer answer, so please excuse me and read through it patiently.
In all the answers discussed here(both what has been suggested and what you have implmented), what we are essentially doing are the following steps.
a) Creating a list of all the possible ways in which a set of n numbers S can be combined in smaller sets of m numbers.
b) Evaluating the sum of all these smaller lists and see if these are equal to k.
c) Creating a separate list which satisfies the sum condition.
The most memory is consumed in storing the first list that is created. For any given set of numbers S of size n, the number of combinations of size m that can be generated from it without replacements and where the order doesn't matter is given as n!/((n-m)!*m!). (Please review the topic Combinations without repetition in Permutations and Combinations. https://www.mathsisfun.com/combinatorics/combinations-permutations.html)
To illustrate with an example, if S = {1,2,3,4,5} and m = 3, then,
list(combinations(S,m)) = [(1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 3, 4), (1, 3, 5), (1, 4, 5), (2, 3, 4), (2, 3, 5), (2, 4, 5), (3, 4, 5)], ie, it has 10 components.
By computing it analytically from the formula, it is 5!/((5-3)!*3!) = 5!/(2!*3!) = 120/(2*6) = 10
The same way the number of components in list(combinations(S,m)) can be computed analytically for any given n and m. For instance if n is 1000 and m is 3, then the number of components in the list of combinations that will be generated will equal 1000!/(997!*3!) = 166167000 = 1.6E8
Now, I'll address your specific questions.
(1) Is it possible to develop this algorithm so that it can be run with low memory?
Definitely yes. For that the combinations function should be rewritten and you may not be able to use the inbuilt combinations function of python. When n is large, the problem that you have is that the program proceeds by first creating the list of all the combinations and then evaluates whether the sum of the components is equal to k. Instead what you should be doing is evaluate the sum while the different possible combinations are being created one by one. For that you will have to define an equivalent of the combinations function yourself where the additional condition of the sum is also included while the different combinations are being generated.
(2) If I am writing an algorithm, how do I know, how much memory it will be consumed by RAM?
It is not an exact calculation, since compiler optimizations and other things can play a factor. Integer values in Python occupy 4 bytes. So the size of an integer list having 1E8 components is equal to approx 4E8 bytes or 4E5 KB or 400MB
(3) As you said if the value of n=1000 and m=3 then the system occupying approx 400MB RAM. As far as I have observed, it will also depend on the values of m and k. What happen if we increase m and k to a certain range?
The value of k should not in general have an appreciable difference in the memory usage, though it is possible. The major difference will be caused by the value of m and it can be computed as explained above.
(4) What happens if we take n=1000, m=500 and k=1,25,250=sum of first 500 natural numbers or we may take the value of k in the range (125250, 375250)?
If n=1000 and m=500, then the number of combinations that are possible will be 1000!/(500!*500!) = 2.7E299. Storing such a huge list is practically not very feasible.
Instead what can be done is that you can create the combinations one by one and simultaneously evaluate the sum and store only the combinations that satisfy the sum condition.
- Badges
- Science topic
- Similar topics
- Social Science