Seeking Substantial Subcollections
Clash Royale CLAN TAG#URR8PPP
up vote
5
down vote
favorite
(thanks to @JonathanFrech for the title)
Challenge
Write a program or function that, given a collection of positive integers $S$ and a positive integer $n$, finds as many non-overlapping subcollections $T_1, T_2, ..., T_k$ of $S$ as possible, such that the sum of every $T_m$ is equal to $n$.
Example
Given $S=lbrace1,1,2,2,3,3,3,5,6,8rbrace$ and $n=6$, you could take the following subcollections to get $k=3$:
- $T_1=lbrace1,1,2,2rbrace$
- $T_2=lbrace3,3rbrace$
- $T_3=lbrace6rbrace$
And the remaining elements $lbrace3,5,8rbrace$ are not used. However, there is a way to get $k=4$ separate subcollections:
- $T_1=lbrace1,2,3rbrace$
- $T_2=lbrace1,5rbrace$
- $T_3=lbrace3,3rbrace$
- $T_4=lbrace6rbrace$
This leaves $lbrace2,8rbrace$ unused. There is no way to do this with 5 subcollections1, so $k=4$ for this example.
Input
Input will be a collection of positive integers $S$, and a positive integer $n$. $S$ may be taken in any reasonable format: a comma- or newline-separated string, an actual array/list, etc. You may assume that $S$ is sorted (if your input format has a defined order).
Output
The output may be either:
- the maximal number of subcollections $k$; or
- any collection which has $k$ items (e.g., the list of subcollections $T$ itself), in any reasonable format.
Note that there is not guaranteed to be any subcollections with sum $n$ (i.e. some inputs will output 0
, , etc.)
Test cases
n, S -> k
1, [1] -> 1
1, [2] -> 0
2, [1] -> 0
1, [1, 1] -> 2
2, [1, 1, 1] -> 1
3, [1, 1, 2, 2] -> 2
9, [1, 1, 3, 3, 5, 5, 7] -> 2
9, [1, 1, 3, 3, 5, 7, 7] -> 1
8, [1, 1, 2, 3, 4, 6, 6, 6] -> 2
6, [1, 1, 2, 2, 3, 3, 3, 5, 6, 8] -> 4
13, [2, 2, 2, 2, 3, 3, 4, 5, 5, 6, 8, 9, 9, 11, 12] -> 5
22, [1, 1, 2, 3, 3, 3, 3, 3, 4, 4, 4, 5, 6, 6, 7, 7, 7, 8, 9, 9, 10, 13, 14, 14, 17, 18, 18, 21] -> 10
Scoring
This is code-golf, so the shortest program in bytes in each language wins. Good luck!
1. Mini-proof: the $8$ is obviously useless, but when you remove it, the total sum of $S$ becomes $26$; therefore, it can only contain up to $4$ non-overlapping subcollections whose sums are $6$.
code-golf number combinatorics
add a comment |Â
up vote
5
down vote
favorite
(thanks to @JonathanFrech for the title)
Challenge
Write a program or function that, given a collection of positive integers $S$ and a positive integer $n$, finds as many non-overlapping subcollections $T_1, T_2, ..., T_k$ of $S$ as possible, such that the sum of every $T_m$ is equal to $n$.
Example
Given $S=lbrace1,1,2,2,3,3,3,5,6,8rbrace$ and $n=6$, you could take the following subcollections to get $k=3$:
- $T_1=lbrace1,1,2,2rbrace$
- $T_2=lbrace3,3rbrace$
- $T_3=lbrace6rbrace$
And the remaining elements $lbrace3,5,8rbrace$ are not used. However, there is a way to get $k=4$ separate subcollections:
- $T_1=lbrace1,2,3rbrace$
- $T_2=lbrace1,5rbrace$
- $T_3=lbrace3,3rbrace$
- $T_4=lbrace6rbrace$
This leaves $lbrace2,8rbrace$ unused. There is no way to do this with 5 subcollections1, so $k=4$ for this example.
Input
Input will be a collection of positive integers $S$, and a positive integer $n$. $S$ may be taken in any reasonable format: a comma- or newline-separated string, an actual array/list, etc. You may assume that $S$ is sorted (if your input format has a defined order).
Output
The output may be either:
- the maximal number of subcollections $k$; or
- any collection which has $k$ items (e.g., the list of subcollections $T$ itself), in any reasonable format.
Note that there is not guaranteed to be any subcollections with sum $n$ (i.e. some inputs will output 0
, , etc.)
Test cases
n, S -> k
1, [1] -> 1
1, [2] -> 0
2, [1] -> 0
1, [1, 1] -> 2
2, [1, 1, 1] -> 1
3, [1, 1, 2, 2] -> 2
9, [1, 1, 3, 3, 5, 5, 7] -> 2
9, [1, 1, 3, 3, 5, 7, 7] -> 1
8, [1, 1, 2, 3, 4, 6, 6, 6] -> 2
6, [1, 1, 2, 2, 3, 3, 3, 5, 6, 8] -> 4
13, [2, 2, 2, 2, 3, 3, 4, 5, 5, 6, 8, 9, 9, 11, 12] -> 5
22, [1, 1, 2, 3, 3, 3, 3, 3, 4, 4, 4, 5, 6, 6, 7, 7, 7, 8, 9, 9, 10, 13, 14, 14, 17, 18, 18, 21] -> 10
Scoring
This is code-golf, so the shortest program in bytes in each language wins. Good luck!
1. Mini-proof: the $8$ is obviously useless, but when you remove it, the total sum of $S$ becomes $26$; therefore, it can only contain up to $4$ non-overlapping subcollections whose sums are $6$.
code-golf number combinatorics
add a comment |Â
up vote
5
down vote
favorite
up vote
5
down vote
favorite
(thanks to @JonathanFrech for the title)
Challenge
Write a program or function that, given a collection of positive integers $S$ and a positive integer $n$, finds as many non-overlapping subcollections $T_1, T_2, ..., T_k$ of $S$ as possible, such that the sum of every $T_m$ is equal to $n$.
Example
Given $S=lbrace1,1,2,2,3,3,3,5,6,8rbrace$ and $n=6$, you could take the following subcollections to get $k=3$:
- $T_1=lbrace1,1,2,2rbrace$
- $T_2=lbrace3,3rbrace$
- $T_3=lbrace6rbrace$
And the remaining elements $lbrace3,5,8rbrace$ are not used. However, there is a way to get $k=4$ separate subcollections:
- $T_1=lbrace1,2,3rbrace$
- $T_2=lbrace1,5rbrace$
- $T_3=lbrace3,3rbrace$
- $T_4=lbrace6rbrace$
This leaves $lbrace2,8rbrace$ unused. There is no way to do this with 5 subcollections1, so $k=4$ for this example.
Input
Input will be a collection of positive integers $S$, and a positive integer $n$. $S$ may be taken in any reasonable format: a comma- or newline-separated string, an actual array/list, etc. You may assume that $S$ is sorted (if your input format has a defined order).
Output
The output may be either:
- the maximal number of subcollections $k$; or
- any collection which has $k$ items (e.g., the list of subcollections $T$ itself), in any reasonable format.
Note that there is not guaranteed to be any subcollections with sum $n$ (i.e. some inputs will output 0
, , etc.)
Test cases
n, S -> k
1, [1] -> 1
1, [2] -> 0
2, [1] -> 0
1, [1, 1] -> 2
2, [1, 1, 1] -> 1
3, [1, 1, 2, 2] -> 2
9, [1, 1, 3, 3, 5, 5, 7] -> 2
9, [1, 1, 3, 3, 5, 7, 7] -> 1
8, [1, 1, 2, 3, 4, 6, 6, 6] -> 2
6, [1, 1, 2, 2, 3, 3, 3, 5, 6, 8] -> 4
13, [2, 2, 2, 2, 3, 3, 4, 5, 5, 6, 8, 9, 9, 11, 12] -> 5
22, [1, 1, 2, 3, 3, 3, 3, 3, 4, 4, 4, 5, 6, 6, 7, 7, 7, 8, 9, 9, 10, 13, 14, 14, 17, 18, 18, 21] -> 10
Scoring
This is code-golf, so the shortest program in bytes in each language wins. Good luck!
1. Mini-proof: the $8$ is obviously useless, but when you remove it, the total sum of $S$ becomes $26$; therefore, it can only contain up to $4$ non-overlapping subcollections whose sums are $6$.
code-golf number combinatorics
(thanks to @JonathanFrech for the title)
Challenge
Write a program or function that, given a collection of positive integers $S$ and a positive integer $n$, finds as many non-overlapping subcollections $T_1, T_2, ..., T_k$ of $S$ as possible, such that the sum of every $T_m$ is equal to $n$.
Example
Given $S=lbrace1,1,2,2,3,3,3,5,6,8rbrace$ and $n=6$, you could take the following subcollections to get $k=3$:
- $T_1=lbrace1,1,2,2rbrace$
- $T_2=lbrace3,3rbrace$
- $T_3=lbrace6rbrace$
And the remaining elements $lbrace3,5,8rbrace$ are not used. However, there is a way to get $k=4$ separate subcollections:
- $T_1=lbrace1,2,3rbrace$
- $T_2=lbrace1,5rbrace$
- $T_3=lbrace3,3rbrace$
- $T_4=lbrace6rbrace$
This leaves $lbrace2,8rbrace$ unused. There is no way to do this with 5 subcollections1, so $k=4$ for this example.
Input
Input will be a collection of positive integers $S$, and a positive integer $n$. $S$ may be taken in any reasonable format: a comma- or newline-separated string, an actual array/list, etc. You may assume that $S$ is sorted (if your input format has a defined order).
Output
The output may be either:
- the maximal number of subcollections $k$; or
- any collection which has $k$ items (e.g., the list of subcollections $T$ itself), in any reasonable format.
Note that there is not guaranteed to be any subcollections with sum $n$ (i.e. some inputs will output 0
, , etc.)
Test cases
n, S -> k
1, [1] -> 1
1, [2] -> 0
2, [1] -> 0
1, [1, 1] -> 2
2, [1, 1, 1] -> 1
3, [1, 1, 2, 2] -> 2
9, [1, 1, 3, 3, 5, 5, 7] -> 2
9, [1, 1, 3, 3, 5, 7, 7] -> 1
8, [1, 1, 2, 3, 4, 6, 6, 6] -> 2
6, [1, 1, 2, 2, 3, 3, 3, 5, 6, 8] -> 4
13, [2, 2, 2, 2, 3, 3, 4, 5, 5, 6, 8, 9, 9, 11, 12] -> 5
22, [1, 1, 2, 3, 3, 3, 3, 3, 4, 4, 4, 5, 6, 6, 7, 7, 7, 8, 9, 9, 10, 13, 14, 14, 17, 18, 18, 21] -> 10
Scoring
This is code-golf, so the shortest program in bytes in each language wins. Good luck!
1. Mini-proof: the $8$ is obviously useless, but when you remove it, the total sum of $S$ becomes $26$; therefore, it can only contain up to $4$ non-overlapping subcollections whose sums are $6$.
code-golf number combinatorics
code-golf number combinatorics
edited 4 hours ago
asked 5 hours ago
ETHproductions
43.9k572219
43.9k572219
add a comment |Â
add a comment |Â
3 Answers
3
active
oldest
votes
up vote
1
down vote
Jelly, 17 bytes
Ã
Â!Ã
Âá¹Ââ¬áºÂÃ
ÂPâ¬áºÂç;EÃÂÃÂáºÂá¹Â
Try it online!
Outputs $k$ if there is a $T$, $0$ otherwise. Very slow.
add a comment |Â
up vote
1
down vote
Jelly, Â 17Â 11 bytes
Ã
Â!Ã
Âá¹Âç=ÃÂâFá¹Â
A dyadic link accepting a list and an integer which yields the maximal count, $k$.
Try it online! Or see the test-suite -- it's too slow for the larger test cases :(
How?
Ã
Â!Ã
Âá¹Âç=ÃÂâFá¹ - Link: list L, integer I
Ã
Â! - all permutations
⬠- for â¬ach:
ÃÂ - last three links as a dyad - i.e. f(permutation, I)
Ã
Âá¹ - partitions (all ways to slice up the permutation)
ç - sum each (vectorises at depth 1, so this gets the sums of the parts of
- the partitions)
= - equals? (==I) -> 1 if so 0 otherwise
ç - sum each (vectorises at depth 1, so this gets the counts of parts equal to I
- for each partition of each permutation)
F - flatten
á¹ - maximum
add a comment |Â
up vote
0
down vote
JavaScript (Node.js), 115 bytes
k=>f=([i,...s])=>i?Math.max(...[i,...s].map((_,j)=>(e[j]=~~e[j]+i,_=f(s),e[j]-=i,_))):e.filter(_=>_==k).length;e=
Try it online!
add a comment |Â
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
Jelly, 17 bytes
Ã
Â!Ã
Âá¹Ââ¬áºÂÃ
ÂPâ¬áºÂç;EÃÂÃÂáºÂá¹Â
Try it online!
Outputs $k$ if there is a $T$, $0$ otherwise. Very slow.
add a comment |Â
up vote
1
down vote
Jelly, 17 bytes
Ã
Â!Ã
Âá¹Ââ¬áºÂÃ
ÂPâ¬áºÂç;EÃÂÃÂáºÂá¹Â
Try it online!
Outputs $k$ if there is a $T$, $0$ otherwise. Very slow.
add a comment |Â
up vote
1
down vote
up vote
1
down vote
Jelly, 17 bytes
Ã
Â!Ã
Âá¹Ââ¬áºÂÃ
ÂPâ¬áºÂç;EÃÂÃÂáºÂá¹Â
Try it online!
Outputs $k$ if there is a $T$, $0$ otherwise. Very slow.
Jelly, 17 bytes
Ã
Â!Ã
Âá¹Ââ¬áºÂÃ
ÂPâ¬áºÂç;EÃÂÃÂáºÂá¹Â
Try it online!
Outputs $k$ if there is a $T$, $0$ otherwise. Very slow.
edited 4 hours ago
answered 4 hours ago
Erik the Outgolfer
29.9k42899
29.9k42899
add a comment |Â
add a comment |Â
up vote
1
down vote
Jelly, Â 17Â 11 bytes
Ã
Â!Ã
Âá¹Âç=ÃÂâFá¹Â
A dyadic link accepting a list and an integer which yields the maximal count, $k$.
Try it online! Or see the test-suite -- it's too slow for the larger test cases :(
How?
Ã
Â!Ã
Âá¹Âç=ÃÂâFá¹ - Link: list L, integer I
Ã
Â! - all permutations
⬠- for â¬ach:
ÃÂ - last three links as a dyad - i.e. f(permutation, I)
Ã
Âá¹ - partitions (all ways to slice up the permutation)
ç - sum each (vectorises at depth 1, so this gets the sums of the parts of
- the partitions)
= - equals? (==I) -> 1 if so 0 otherwise
ç - sum each (vectorises at depth 1, so this gets the counts of parts equal to I
- for each partition of each permutation)
F - flatten
á¹ - maximum
add a comment |Â
up vote
1
down vote
Jelly, Â 17Â 11 bytes
Ã
Â!Ã
Âá¹Âç=ÃÂâFá¹Â
A dyadic link accepting a list and an integer which yields the maximal count, $k$.
Try it online! Or see the test-suite -- it's too slow for the larger test cases :(
How?
Ã
Â!Ã
Âá¹Âç=ÃÂâFá¹ - Link: list L, integer I
Ã
Â! - all permutations
⬠- for â¬ach:
ÃÂ - last three links as a dyad - i.e. f(permutation, I)
Ã
Âá¹ - partitions (all ways to slice up the permutation)
ç - sum each (vectorises at depth 1, so this gets the sums of the parts of
- the partitions)
= - equals? (==I) -> 1 if so 0 otherwise
ç - sum each (vectorises at depth 1, so this gets the counts of parts equal to I
- for each partition of each permutation)
F - flatten
á¹ - maximum
add a comment |Â
up vote
1
down vote
up vote
1
down vote
Jelly, Â 17Â 11 bytes
Ã
Â!Ã
Âá¹Âç=ÃÂâFá¹Â
A dyadic link accepting a list and an integer which yields the maximal count, $k$.
Try it online! Or see the test-suite -- it's too slow for the larger test cases :(
How?
Ã
Â!Ã
Âá¹Âç=ÃÂâFá¹ - Link: list L, integer I
Ã
Â! - all permutations
⬠- for â¬ach:
ÃÂ - last three links as a dyad - i.e. f(permutation, I)
Ã
Âá¹ - partitions (all ways to slice up the permutation)
ç - sum each (vectorises at depth 1, so this gets the sums of the parts of
- the partitions)
= - equals? (==I) -> 1 if so 0 otherwise
ç - sum each (vectorises at depth 1, so this gets the counts of parts equal to I
- for each partition of each permutation)
F - flatten
á¹ - maximum
Jelly, Â 17Â 11 bytes
Ã
Â!Ã
Âá¹Âç=ÃÂâFá¹Â
A dyadic link accepting a list and an integer which yields the maximal count, $k$.
Try it online! Or see the test-suite -- it's too slow for the larger test cases :(
How?
Ã
Â!Ã
Âá¹Âç=ÃÂâFá¹ - Link: list L, integer I
Ã
Â! - all permutations
⬠- for â¬ach:
ÃÂ - last three links as a dyad - i.e. f(permutation, I)
Ã
Âá¹ - partitions (all ways to slice up the permutation)
ç - sum each (vectorises at depth 1, so this gets the sums of the parts of
- the partitions)
= - equals? (==I) -> 1 if so 0 otherwise
ç - sum each (vectorises at depth 1, so this gets the counts of parts equal to I
- for each partition of each permutation)
F - flatten
á¹ - maximum
edited 40 mins ago
answered 1 hour ago
Jonathan Allan
49.5k534163
49.5k534163
add a comment |Â
add a comment |Â
up vote
0
down vote
JavaScript (Node.js), 115 bytes
k=>f=([i,...s])=>i?Math.max(...[i,...s].map((_,j)=>(e[j]=~~e[j]+i,_=f(s),e[j]-=i,_))):e.filter(_=>_==k).length;e=
Try it online!
add a comment |Â
up vote
0
down vote
JavaScript (Node.js), 115 bytes
k=>f=([i,...s])=>i?Math.max(...[i,...s].map((_,j)=>(e[j]=~~e[j]+i,_=f(s),e[j]-=i,_))):e.filter(_=>_==k).length;e=
Try it online!
add a comment |Â
up vote
0
down vote
up vote
0
down vote
JavaScript (Node.js), 115 bytes
k=>f=([i,...s])=>i?Math.max(...[i,...s].map((_,j)=>(e[j]=~~e[j]+i,_=f(s),e[j]-=i,_))):e.filter(_=>_==k).length;e=
Try it online!
JavaScript (Node.js), 115 bytes
k=>f=([i,...s])=>i?Math.max(...[i,...s].map((_,j)=>(e[j]=~~e[j]+i,_=f(s),e[j]-=i,_))):e.filter(_=>_==k).length;e=
Try it online!
edited 3 hours ago
answered 3 hours ago
l4m2
4,0381431
4,0381431
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f174906%2fseeking-substantial-subcollections%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password