The problem has 3 inputs.
L: a list of all numbers
size: the size each set can be
max: the max sum amongst each set
The challenge is as follows:
Given L, size and max, construct as many sets from L such that the number of elements is size and the sum of each of the elements does not exceed max.
Examples:
func(L=[1,2,3,4], size=2, max=5) = [{1,2}, {1,3}, {2,3}, {1,4}]
Notice how each of the values in the outputted set are sum <= max.
func(L=[1,2,3,4], size=3, max=6) = [{1,2,3}]
func(L=[1,2,3,4], size=3, max=5) = [{}] or empty list, whichever you want
Note that in the set you cannot have duplicated items. ie: {2,1} = {1,2}
Constraints on inputs:
L: 0 or more elements
size: 0 <= size <= len(L)
max: 0 or more
If a list has 0 items, then always return the empty set.
If the size is 0, then always return the empty set.
If max is 0, it is possible that there are negative values in L, in which case the returned sets need not be empty.
Shorted bytes wins!
9 Answers 9
-
1\$\begingroup\$ Duplicated items in list: try this:
2,[1,1,2,2,3,3,4,4],20. [1,2] is repeated \$\endgroup\$K Split X– K Split X2019年09月20日 18:04:18 +00:00Commented Sep 20, 2019 at 18:04 -
\$\begingroup\$ @KSplitX Thanks, fixed. It would be helpful if you added that test case to the question! \$\endgroup\$Grimmy– Grimmy2019年09月20日 21:58:30 +00:00Commented Sep 20, 2019 at 21:58
Brachylog, 9 bytes
≥t⟨⟨⊇l⟩+⟩
Takes input as [[L,size],max] through the input variable and generates the output through the output variable.
Python 3, (削除) 82 (削除ここまで) 79 bytes
lambda l,s,m:[i for i in __import__("itertools").combinations(l,s)if sum(i)<=m]
-3 bytes thanks to squid
Japt, 11 bytes
àV â fÈx §W
àV â fÈx §W :Implicit input of array U=L and integers V=size & W=max
àV :Combinations of U of length V
â :Deduplicate
f :Filter by
È :Function
x : Sum
§W : Less than or equal to W
-
\$\begingroup\$ Not unique outputs. Try the following:
[1,1,2,2,3,3,4,4],4,20...1,1,2,3for example is repeated \$\endgroup\$K Split X– K Split X2019年09月20日 17:54:52 +00:00Commented Sep 20, 2019 at 17:54 -
\$\begingroup\$ @KSplitX, Missed that. Fixed \$\endgroup\$Shaggy– Shaggy2019年09月20日 18:02:45 +00:00Commented Sep 20, 2019 at 18:02
R, 56 bytes
function(L,s,m,a=combn(L,s))unique(a[,colSums(a)<=m],,2)
Creates a matrix where each column is a subset of L of size s, and keeps those for which the sum is less than m. Output is a matrix, with each column corresponding to one allowable subset (if there is only one such subset, the output is a s×ばつ1 matrix and R will display it on one row instead by default).
Note that this fails for the edge case where L is empty. Handling that edge case as specified in the challenge takes 19 more bytes:
R, 75 bytes
function(L,s,m,a=combn(L,s))`if`(length(L),unique(a[,colSums(a)<=m],,2),{})
-
\$\begingroup\$ 53 bytes? I don't think I've ever noticed that
uniquehas amarginargument, that's quite a helpful tip! I usually justunique(t()); the comments on other answers seem to indicate that[1,1]shouldn't be a valid output on[1,1,2,3],2,20\$\endgroup\$Giuseppe– Giuseppe2019年09月20日 19:26:39 +00:00Commented Sep 20, 2019 at 19:26 -
\$\begingroup\$ @Giuseppe I discovered the
marginargument today as well. I was going tounique(t())but checked the help ofuniquejust in case... and luckily, the argument exists! I guess we need to wait for OP to clarify the challenge to know where to applyunique. \$\endgroup\$Robin Ryder– Robin Ryder2019年09月20日 20:13:26 +00:00Commented Sep 20, 2019 at 20:13
-
1\$\begingroup\$ You need to move the
Qto the beginning. The challenge doesn't really have adequate test cases right now, so you might easily miss that. \$\endgroup\$Erik the Outgolfer– Erik the Outgolfer2019年09月20日 19:55:32 +00:00Commented Sep 20, 2019 at 19:55 -
\$\begingroup\$ @EriktheOutgolfer thanks \$\endgroup\$Nick Kennedy– Nick Kennedy2019年09月20日 19:56:41 +00:00Commented Sep 20, 2019 at 19:56
Pyth, 15 bytes
{SMfgeQsT.PhQht
{SMfgeQsT.PhQhtQ # (last Q implicit; Q = input)
.P # all permutations
hQ # of Q[0]
htQ # of length Q[1:][0] = Q[1]
f # filter those with lambda T:
eQ # Q[-1]
g # >=
sT # sum(T)
SM # sort each element
{ # deduplicate
Kotlin, 286 bytes
fun p(l:List<Int>,s:Int,m:Int){val r=MutableList(0){""}
val a=l.toSet().toList()
fun r(n:Int,b:Int,t:Int,u:List<Int>){if(n<1){if(t<=m)r.add(u.joinToString(",","{","}"))}else
for(e in b..a.size-1)r(n-1,e+1,t+a[e],u+listOf(a[e]))}
r(s,0,0,List(0){0})
println(r.joinToString(",","[","]"))}
Lwill be non-empty. It is generally advisable to avoid edge cases in code-golf challenges, as they don't add much and can cost many bytes. \$\endgroup\$