Re: [R] Subset sum problem.
Hans, you're my personal hero today !
The function seems to work fine for the tests I did already.
Thank you very much !
Geert
On Thursday 10 December 2009, Hans W Borchers wrote:
Geert Janssens janssens-geert at telenet.be writes:
On Wednesday 9 December 2009, Hans W Borchers wrote:
Geert Janssens janssens-geert at telenet.be writes:
[ ... ]
Has anybody tackled this issue before in R ? If so, I would be very
grateful if you could share your solution with me.
Is it really true that you only want to see a Yes or No answer to
this question whether a subset sums up to s --- without learning which
numbers this subset is composed of (the pure SUBSET SUM problem)?
Then the following procedure does that in a reasonable amount of time
(returning 'TRUE' or 'FALSE' instead of Y-or-N):
Unfortunately no. I do need the numbers in the subset. But thank you for
presenting this code.
Geert
Okay then, here we go. But don't tell later that your requirement was to
generate _all_ subsets that add up to a certain amount. I will generate
only one (with largest elements).
For simplicity I assume that the set is prepared s.t. it is decreasingly
ordered, has no elements larger than the amount given, and has a total sum
larger than this amount.
# Assume S decreasing, no elements t, total sum = t
solveSubsetSum - function(S, t) {
L - c(0)
inds - NULL
for (i in 1:length(S)) {
# L - unique(sort(c(L, L + S[i])))
L - c(L, L+S[i])
L - L[L = t]
if (max(L) == t) {
inds - c(i)
t - t - S[i]
while (t 0) {
K - c(0)
for (j in 1:(i-1)) {
K - c(K, K+S[j])
if (t %in% K) break
}
inds - c(inds, j)
t - t - S[j]
}
break
}
}
return(inds)
}
# former example
amount - 4748652
products -
c(30500,30500,30500,30500,42000,42000,42000,42000,
42000,42000,42000,42000,42000,42000,71040,90900,
76950,35100,71190,53730,456000,70740,70740,533600,
83800,59500,27465,28000,28000,28000,28000,28000,
26140,49600,77000,123289,27000,27000,27000,27000,
27000,27000,8,33000,33000,55000,77382,48048,
51186,4,35000,21716,63051,15025,15025,15025,
15025,80,111,59700,25908,829350,1198000,1031655)
# prepare set
prods - products[products = amount] # no elements amount
prods - sort(prods, decreasing=TRUE) # decreasing order
# now find one solution
system.time(is - solveSubsetSum(prods, amount))
# user system elapsed
# 0.320 0.032 0.359
prods[is]
# [1] 70740 70740 71190 76950 77382 8 83800
# [8] 90900 456000 533600 829350 111 1198000
sum(prods[is]) == amount
# [1] TRUE
Note that running times and memory needs will be much higher when more
summands are needed. To mention that too: I have not tested the code
extensively.
Regards
Hans Werner
__
R-help@r-project.org mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide
http://www.R-project.org/posting-guide.html and provide commented, minimal,
self-contained, reproducible code.
__
R-help@r-project.org mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
Re: [R] Subset sum problem.
Hans, you're my personal hero today !
The function seems to work fine for the tests I did already.
Thank you very much !
Geert
On Thursday 10 December 2009, Hans W Borchers wrote:
Geert Janssens janssens-geert at telenet.be writes:
On Wednesday 9 December 2009, Hans W Borchers wrote:
Geert Janssens janssens-geert at telenet.be writes:
[ ... ]
Has anybody tackled this issue before in R ? If so, I would be very
grateful if you could share your solution with me.
Is it really true that you only want to see a Yes or No answer to
this question whether a subset sums up to s --- without learning which
numbers this subset is composed of (the pure SUBSET SUM problem)?
Then the following procedure does that in a reasonable amount of time
(returning 'TRUE' or 'FALSE' instead of Y-or-N):
Unfortunately no. I do need the numbers in the subset. But thank you for
presenting this code.
Geert
Okay then, here we go. But don't tell later that your requirement was to
generate _all_ subsets that add up to a certain amount. I will generate
only one (with largest elements).
For simplicity I assume that the set is prepared s.t. it is decreasingly
ordered, has no elements larger than the amount given, and has a total sum
larger than this amount.
# Assume S decreasing, no elements t, total sum = t
solveSubsetSum - function(S, t) {
L - c(0)
inds - NULL
for (i in 1:length(S)) {
# L - unique(sort(c(L, L + S[i])))
L - c(L, L+S[i])
L - L[L = t]
if (max(L) == t) {
inds - c(i)
t - t - S[i]
while (t 0) {
K - c(0)
for (j in 1:(i-1)) {
K - c(K, K+S[j])
if (t %in% K) break
}
inds - c(inds, j)
t - t - S[j]
}
break
}
}
return(inds)
}
# former example
amount - 4748652
products -
c(30500,30500,30500,30500,42000,42000,42000,42000,
42000,42000,42000,42000,42000,42000,71040,90900,
76950,35100,71190,53730,456000,70740,70740,533600,
83800,59500,27465,28000,28000,28000,28000,28000,
26140,49600,77000,123289,27000,27000,27000,27000,
27000,27000,8,33000,33000,55000,77382,48048,
51186,4,35000,21716,63051,15025,15025,15025,
15025,80,111,59700,25908,829350,1198000,1031655)
# prepare set
prods - products[products = amount] # no elements amount
prods - sort(prods, decreasing=TRUE) # decreasing order
# now find one solution
system.time(is - solveSubsetSum(prods, amount))
# user system elapsed
# 0.320 0.032 0.359
prods[is]
# [1] 70740 70740 71190 76950 77382 8 83800
# [8] 90900 456000 533600 829350 111 1198000
sum(prods[is]) == amount
# [1] TRUE
Note that running times and memory needs will be much higher when more
summands are needed. To mention that too: I have not tested the code
extensively.
Regards
Hans Werner
__
R-help@r-project.org mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide
http://www.R-project.org/posting-guide.html and provide commented, minimal,
self-contained, reproducible code.
--
Kobalt W.I.T.
Web Information Technology
Brusselsesteenweg 152
1850 Grimbergen
Tel : +32 479 339 655
Email: i...@kobaltwit.be
__
R-help@r-project.org mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
Re: [R] Subset sum problem.
Geert Janssens janssens-geert at telenet.be writes:
Hi,
I'm quite new to the R-project. I was suggested to look into it because I am
trying to solve the Subset sum problem, which basically is:
Given a set of integers and an integer s, does any non-empty subset sum to s?
(See http://en.wikipedia.org/wiki/Subset_sum_problem)
I have been searching the web for quite some time now (which is how I
eventually discovered that my problem is called subset sum), but I can't seem
to find an easily applicable implementation. I did search the list archive,
the R website and used the help.search and apropos function. I'm afraid
nothing obvious showed up for me.
Has anybody tackled this issue before in R ? If so, I would be very grateful
if you could share your solution with me.
Is it really true that you only want to see a Yes or No answer to this
question whether a subset sums up to s --- without learning which numbers
this subset is composed of (the pure SUBSET SUM problem)?
Then the following procedure does that in a reasonable amount of time
(returning 'TRUE' or 'FALSE' instead of Y-or-N):
# Exact algorithm for the SUBSET SUM problem
exactSubsetSum - function(S, t) {
S - S[S = t]
if (sum(S) t) return(FALSE)
S - sort(S, decreasing=TRUE)
n - length(S)
L - c(0)
for (i in 1:n) {
L - unique(sort(c(L, L + S[i])))
L - L[L = t]
if (max(L) == t) return(TRUE)
}
return(FALSE)
}
# Example with a set of cardinality 64
amount - 4748652
products -
c(30500,30500,30500,30500,42000,42000,42000,42000,
42000,42000,42000,42000,42000,42000,71040,90900,
76950,35100,71190,53730,456000,70740,70740,533600,
83800,59500,27465,28000,28000,28000,28000,28000,
26140,49600,77000,123289,27000,27000,27000,27000,
27000,27000,8,33000,33000,55000,77382,48048,
51186,4,35000,21716,63051,15025,15025,15025,
15025,80,111,59700,25908,829350,1198000,1031655)
# Timing is not that bad
system.time( sol - exactSubsetSum(products, amount) )
# user system elapsed
# 0.516 0.096 0.673
sol
# [1] TRUE
Thank you very much.
Geert
__
R-help@r-project.org mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
Re: [R] Subset sum problem.
On Wednesday 9 December 2009, Hans W Borchers wrote:
Geert Janssens janssens-geert at telenet.be writes:
Hi,
I'm quite new to the R-project. I was suggested to look into it because I
am trying to solve the Subset sum problem, which basically is:
Given a set of integers and an integer s, does any non-empty subset sum
to s? (See http://en.wikipedia.org/wiki/Subset_sum_problem)
I have been searching the web for quite some time now (which is how I
eventually discovered that my problem is called subset sum), but I can't
seem to find an easily applicable implementation. I did search the list
archive, the R website and used the help.search and apropos function. I'm
afraid nothing obvious showed up for me.
Has anybody tackled this issue before in R ? If so, I would be very
grateful if you could share your solution with me.
Is it really true that you only want to see a Yes or No answer to this
question whether a subset sums up to s --- without learning which numbers
this subset is composed of (the pure SUBSET SUM problem)?
Then the following procedure does that in a reasonable amount of time
(returning 'TRUE' or 'FALSE' instead of Y-or-N):
Unfortunatly no. I do need the numbers in the subset. But thank you for
presenting this code.
Geert
# Exact algorithm for the SUBSET SUM problem
exactSubsetSum - function(S, t) {
S - S[S = t]
if (sum(S) t) return(FALSE)
S - sort(S, decreasing=TRUE)
n - length(S)
L - c(0)
for (i in 1:n) {
L - unique(sort(c(L, L + S[i])))
L - L[L = t]
if (max(L) == t) return(TRUE)
}
return(FALSE)
}
# Example with a set of cardinality 64
amount - 4748652
products -
c(30500,30500,30500,30500,42000,42000,42000,42000,
42000,42000,42000,42000,42000,42000,71040,90900,
76950,35100,71190,53730,456000,70740,70740,533600,
83800,59500,27465,28000,28000,28000,28000,28000,
26140,49600,77000,123289,27000,27000,27000,27000,
27000,27000,8,33000,33000,55000,77382,48048,
51186,4,35000,21716,63051,15025,15025,15025,
15025,80,111,59700,25908,829350,1198000,1031655)
# Timing is not that bad
system.time( sol - exactSubsetSum(products, amount) )
# user system elapsed
# 0.516 0.096 0.673
sol
# [1] TRUE
__
R-help@r-project.org mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
Re: [R] Subset sum problem.
On Wednesday 9 December 2009, Hans W Borchers wrote:
Geert Janssens janssens-geert at telenet.be writes:
Hi,
I'm quite new to the R-project. I was suggested to look into it because I
am trying to solve the Subset sum problem, which basically is:
Given a set of integers and an integer s, does any non-empty subset sum
to s? (See http://en.wikipedia.org/wiki/Subset_sum_problem)
I have been searching the web for quite some time now (which is how I
eventually discovered that my problem is called subset sum), but I can't
seem to find an easily applicable implementation. I did search the list
archive, the R website and used the help.search and apropos function. I'm
afraid nothing obvious showed up for me.
Has anybody tackled this issue before in R ? If so, I would be very
grateful if you could share your solution with me.
Is it really true that you only want to see a Yes or No answer to this
question whether a subset sums up to s --- without learning which numbers
this subset is composed of (the pure SUBSET SUM problem)?
Then the following procedure does that in a reasonable amount of time
(returning 'TRUE' or 'FALSE' instead of Y-or-N):
Unfortunatly no. I do need the numbers in the subset. But thank you for
presenting this code.
Geert
# Exact algorithm for the SUBSET SUM problem
exactSubsetSum - function(S, t) {
S - S[S = t]
if (sum(S) t) return(FALSE)
S - sort(S, decreasing=TRUE)
n - length(S)
L - c(0)
for (i in 1:n) {
L - unique(sort(c(L, L + S[i])))
L - L[L = t]
if (max(L) == t) return(TRUE)
}
return(FALSE)
}
# Example with a set of cardinality 64
amount - 4748652
products -
c(30500,30500,30500,30500,42000,42000,42000,42000,
42000,42000,42000,42000,42000,42000,71040,90900,
76950,35100,71190,53730,456000,70740,70740,533600,
83800,59500,27465,28000,28000,28000,28000,28000,
26140,49600,77000,123289,27000,27000,27000,27000,
27000,27000,8,33000,33000,55000,77382,48048,
51186,4,35000,21716,63051,15025,15025,15025,
15025,80,111,59700,25908,829350,1198000,1031655)
# Timing is not that bad
system.time( sol - exactSubsetSum(products, amount) )
# user system elapsed
# 0.516 0.096 0.673
sol
# [1] TRUE
--
Kobalt W.I.T.
Web Information Technology
Brusselsesteenweg 152
1850 Grimbergen
Tel : +32 479 339 655
Email: i...@kobaltwit.be
__
R-help@r-project.org mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
Re: [R] Subset sum problem.
Geert Janssens janssens-geert at telenet.be writes:
On Wednesday 9 December 2009, Hans W Borchers wrote:
Geert Janssens janssens-geert at telenet.be writes:
[ ... ]
Has anybody tackled this issue before in R ? If so, I would be very
grateful if you could share your solution with me.
Is it really true that you only want to see a Yes or No answer to this
question whether a subset sums up to s --- without learning which numbers
this subset is composed of (the pure SUBSET SUM problem)?
Then the following procedure does that in a reasonable amount of time
(returning 'TRUE' or 'FALSE' instead of Y-or-N):
Unfortunately no. I do need the numbers in the subset. But thank you for
presenting this code.
Geert
Okay then, here we go. But don't tell later that your requirement was to
generate _all_ subsets that add up to a certain amount. I will generate
only one (with largest elements).
For simplicity I assume that the set is prepared s.t. it is decreasingly
ordered, has no elements larger than the amount given, and has a total sum
larger than this amount.
# Assume S decreasing, no elements t, total sum = t
solveSubsetSum - function(S, t) {
L - c(0)
inds - NULL
for (i in 1:length(S)) {
# L - unique(sort(c(L, L + S[i])))
L - c(L, L+S[i])
L - L[L = t]
if (max(L) == t) {
inds - c(i)
t - t - S[i]
while (t 0) {
K - c(0)
for (j in 1:(i-1)) {
K - c(K, K+S[j])
if (t %in% K) break
}
inds - c(inds, j)
t - t - S[j]
}
break
}
}
return(inds)
}
# former example
amount - 4748652
products -
c(30500,30500,30500,30500,42000,42000,42000,42000,
42000,42000,42000,42000,42000,42000,71040,90900,
76950,35100,71190,53730,456000,70740,70740,533600,
83800,59500,27465,28000,28000,28000,28000,28000,
26140,49600,77000,123289,27000,27000,27000,27000,
27000,27000,8,33000,33000,55000,77382,48048,
51186,4,35000,21716,63051,15025,15025,15025,
15025,80,111,59700,25908,829350,1198000,1031655)
# prepare set
prods - products[products = amount] # no elements amount
prods - sort(prods, decreasing=TRUE) # decreasing order
# now find one solution
system.time(is - solveSubsetSum(prods, amount))
# user system elapsed
# 0.320 0.032 0.359
prods[is]
# [1] 70740 70740 71190 76950 77382 8 83800
# [8] 90900 456000 533600 829350 111 1198000
sum(prods[is]) == amount
# [1] TRUE
Note that running times and memory needs will be much higher when more
summands are needed. To mention that too: I have not tested the code
extensively.
Regards
Hans Werner
__
R-help@r-project.org mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
Re: [R] Subset sum problem.
Thank you for your reply. Unfortunately, I don't have any experience with this kind of mathematics. I don't understand what the wiki page tries to tell me. Please don't misinterpret his, but I simply don't have the time to learn a) how to interpret the math description on wikipedia and b) how that translates into a new environment for me. I tried what I could, but just like all volunteers on this list, my time is limited. I do have a practical use for a subset sum solving algorithm and R seems like a quite capable package. But for my novice eyes it looks I'll need to understand more of it than entering a simple formula which needs time I currently don't have. That's why I asked if someone had solved it before, and was willing to share his/her program with me. I would be very grateful if someone can help me here. Regards, Geert On Monday 7 December 2009, guohao.hu...@gmail.com wrote: The problem is NP-Complete and the real problem is how you can solve it. According to the wiki page, you can use the bottom algorithm(Polynomial time approximate algorithm) to solve your problems. If you had trouble with writing R code, you can read ``R-introduction''. regards Guo-Hao Huang __ R-help@r-project.org mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code.
Re: [R] Subset sum problem.
On Dec 8, 2009, at 8:29 AM, Geert Janssens wrote: Thank you for your reply. Unfortunately, I don't have any experience with this kind of mathematics. I don't understand what the wiki page tries to tell me. Please don't misinterpret his, but I simply don't have the time to learn a) how to interpret the math description on wikipedia and b) how that translates into a new environment for me. I tried what I could, but just like all volunteers on this list, my time is limited. I do have a practical use for a subset sum solving algorithm and R seems like a quite capable package. But for my novice eyes it looks I'll need to understand more of it than entering a simple formula which needs time I currently don't have. Dangerously close to: library(fortunes) fortune(brain surgery) That's why I asked if someone had solved it before, and was willing to share his/her program with me. I would be very grateful if someone can help me here. An implementation was described in the last few months on this list. Regards, Geert On Monday 7 December 2009, guohao.hu...@gmail.com wrote: The problem is NP-Complete and the real problem is how you can solve it. According to the wiki page, you can use the bottom algorithm(Polynomial time approximate algorithm) to solve your problems. If you had trouble with writing R code, you can read ``R- introduction''. regards Guo-Hao Huang David Winsemius, MD Heritage Laboratories West Hartford, CT __ R-help@r-project.org mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code.
Re: [R] Subset sum problem.
On Tuesday 8 December 2009, David Winsemius wrote: On Dec 8, 2009, at 8:29 AM, Geert Janssens wrote: Thank you for your reply. Unfortunately, I don't have any experience with this kind of mathematics. I don't understand what the wiki page tries to tell me. Please don't misinterpret his, but I simply don't have the time to learn a) how to interpret the math description on wikipedia and b) how that translates into a new environment for me. I tried what I could, but just like all volunteers on this list, my time is limited. I do have a practical use for a subset sum solving algorithm and R seems like a quite capable package. But for my novice eyes it looks I'll need to understand more of it than entering a simple formula which needs time I currently don't have. Dangerously close to: library(fortunes) fortune(brain surgery) I understand. The problem in this case is easily described, but not easily solved. When I started to look for a solution, I didn't realize that. That's why I asked if someone had solved it before, and was willing to share his/her program with me. I would be very grateful if someone can help me here. An implementation was described in the last few months on this list. I did find The 'Subset matching' challenge thread before asking any questions myself (https://stat.ethz.ch/pipermail/r-help/2009-October/216604.html) That's where I learned the Subset sum name in the first place, which I used to search further. The thread itself does not provide a solution in R, unless I'm really mistaking. If you were thinking of another thread on the list, I sure could use a hint on what keywords to search for. I also tried google in various incantations, but R is not really a useful search term in google... I find lots of theoretical descriptions of the subset sum problem, but no implementation in R. Geert __ R-help@r-project.org mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code.
Re: [R] Subset sum problem.
On Dec 8, 2009, at 9:14 AM, Geert Janssens wrote: On Tuesday 8 December 2009, David Winsemius wrote: On Dec 8, 2009, at 8:29 AM, Geert Janssens wrote: Thank you for your reply. Unfortunately, I don't have any experience with this kind of mathematics. I don't understand what the wiki page tries to tell me. Please don't misinterpret his, but I simply don't have the time to learn a) how to interpret the math description on wikipedia and b) how that translates into a new environment for me. I tried what I could, but just like all volunteers on this list, my time is limited. I do have a practical use for a subset sum solving algorithm and R seems like a quite capable package. But for my novice eyes it looks I'll need to understand more of it than entering a simple formula which needs time I currently don't have. Dangerously close to: library(fortunes) fortune(brain surgery) I understand. The problem in this case is easily described, but not easily solved. When I started to look for a solution, I didn't realize that. That's why I asked if someone had solved it before, and was willing to share his/her program with me. I would be very grateful if someone can help me here. An implementation was described in the last few months on this list. I did find The 'Subset matching' challenge thread before asking any questions myself (https://stat.ethz.ch/pipermail/r-help/2009-October/216604.html) That's the one. I didn't test the code that the OP offered. He said it was inefficient but implied that it did the job. Inefficiency is pretty much what you would expect after considering the combinatoric explosion that would occur, so I thought the request for code was satisfied. That's where I learned the Subset sum name in the first place, which I used to search further. The thread itself does not provide a solution in R, unless I'm really mistaking. If you were thinking of another thread on the list, I sure could use a hint on what keywords to search for. I also tried google in various incantations, but R is not really a useful search term in google... I find lots of theoretical descriptions of the subset sum problem, but no implementation in R. When I search with Google, I use r-project, since that is a reasonably specific term that would be found in citations and links to the website. Geert David Winsemius, MD Heritage Laboratories West Hartford, CT __ R-help@r-project.org mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code.
Re: [R] Subset sum problem.
The problem is NP-Complete and the real problem is how you can solve it. According to the wiki page, you can use the bottom algorithm(Polynomial time approximate algorithm) to solve your problems. If you had trouble with writing R code, you can read ``R-introduction''. regards Guo-Hao Huang -- From: Geert Janssens janssens-ge...@telenet.be Sent: Monday, December 07, 2009 10:56 PM To: r-help@r-project.org Subject: [R] Subset sum problem. Hi, I'm quite new to the R-project. I was suggested to look into it because I am trying to solve the Subset sum problem, which basically is: Given a set of integers and an integer s, does any non-empty subset sum to s? (See http://en.wikipedia.org/wiki/Subset_sum_problem) I have been searching the web for quite some time now (which is how I eventually discovered that my problem is called subset sum), but I can't seem to find an easily applicable implementation. I did search the list archive, the R website and used the help.search and apropos function. I'm afraid nothing obvious showed up for me. Has anybody tackled this issue before in R ? If so, I would be very grateful if you could share your solution with me. Thank you very much. Geert __ R-help@r-project.org mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code. __ R-help@r-project.org mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code.
