Seeking Substantial Subcollections

The name of the pictureThe name of the pictureThe name of the pictureClash 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:



  1. the maximal number of subcollections $k$; or

  2. 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$.










share|improve this question



























    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:



    1. the maximal number of subcollections $k$; or

    2. 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$.










    share|improve this question

























      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:



      1. the maximal number of subcollections $k$; or

      2. 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$.










      share|improve this question















      (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:



      1. the maximal number of subcollections $k$; or

      2. 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






      share|improve this question















      share|improve this question













      share|improve this question




      share|improve this question








      edited 4 hours ago

























      asked 5 hours ago









      ETHproductions

      43.9k572219




      43.9k572219




















          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.






          share|improve this answer





























            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





            share|improve this answer





























              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!






              share|improve this answer






















                Your Answer




                StackExchange.ifUsing("editor", function ()
                return StackExchange.using("mathjaxEditing", function ()
                StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
                StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
                );
                );
                , "mathjax-editing");

                StackExchange.ifUsing("editor", function ()
                StackExchange.using("externalEditor", function ()
                StackExchange.using("snippets", function ()
                StackExchange.snippets.init();
                );
                );
                , "code-snippets");

                StackExchange.ready(function()
                var channelOptions =
                tags: "".split(" "),
                id: "200"
                ;
                initTagRenderer("".split(" "), "".split(" "), channelOptions);

                StackExchange.using("externalEditor", function()
                // Have to fire editor after snippets, if snippets enabled
                if (StackExchange.settings.snippets.snippetsEnabled)
                StackExchange.using("snippets", function()
                createEditor();
                );

                else
                createEditor();

                );

                function createEditor()
                StackExchange.prepareEditor(
                heartbeatType: 'answer',
                convertImagesToLinks: false,
                noModals: false,
                showLowRepImageUploadWarning: true,
                reputationToPostImages: null,
                bindNavPrevention: true,
                postfix: "",
                onDemand: true,
                discardSelector: ".discard-answer"
                ,immediatelyShowMarkdownHelp:true
                );



                );













                 

                draft saved


                draft discarded


















                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






























                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.






                share|improve this answer


























                  up vote
                  1
                  down vote














                  Jelly, 17 bytes



                  Œ!ŒṖ€ẎŒP€Ẏ§;EɗƇẈṀ


                  Try it online!



                  Outputs $k$ if there is a $T$, $0$ otherwise. Very slow.






                  share|improve this answer
























                    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.






                    share|improve this answer















                    Jelly, 17 bytes



                    Œ!ŒṖ€ẎŒP€Ẏ§;EɗƇẈṀ


                    Try it online!



                    Outputs $k$ if there is a $T$, $0$ otherwise. Very slow.







                    share|improve this answer














                    share|improve this answer



                    share|improve this answer








                    edited 4 hours ago

























                    answered 4 hours ago









                    Erik the Outgolfer

                    29.9k42899




                    29.9k42899




















                        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





                        share|improve this answer


























                          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





                          share|improve this answer
























                            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





                            share|improve this answer















                            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






                            share|improve this answer














                            share|improve this answer



                            share|improve this answer








                            edited 40 mins ago

























                            answered 1 hour ago









                            Jonathan Allan

                            49.5k534163




                            49.5k534163




















                                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!






                                share|improve this answer


























                                  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!






                                  share|improve this answer
























                                    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!






                                    share|improve this answer















                                    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!







                                    share|improve this answer














                                    share|improve this answer



                                    share|improve this answer








                                    edited 3 hours ago

























                                    answered 3 hours ago









                                    l4m2

                                    4,0381431




                                    4,0381431



























                                         

                                        draft saved


                                        draft discarded















































                                         


                                        draft saved


                                        draft discarded














                                        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













































































                                        Comments

                                        Popular posts from this blog

                                        Long meetings (6-7 hours a day): Being “babysat” by supervisor

                                        What does second last employer means? [closed]

                                        One-line joke