Generate all subsets of size k (containing k elements) in Python












14














I have a set of values and would like to create list of all subsets containing 2 elements.



For example, a source set ([1,2,3]) has the following 2-element subsets: 



set([1,2]), set([1,3]), set([2,3])


Is there a way to do this in python?






python set tuples subset







share|improve this question





























    14














    I have a set of values and would like to create list of all subsets containing 2 elements.



    For example, a source set ([1,2,3]) has the following 2-element subsets: 



    set([1,2]), set([1,3]), set([2,3])


    Is there a way to do this in python?






    python set tuples subset







    share|improve this question



























      14












      14








      14


      3





      I have a set of values and would like to create list of all subsets containing 2 elements.



      For example, a source set ([1,2,3]) has the following 2-element subsets: 



      set([1,2]), set([1,3]), set([2,3])


      Is there a way to do this in python?






      python set tuples subset







      share|improve this question















      I have a set of values and would like to create list of all subsets containing 2 elements.



      For example, a source set ([1,2,3]) has the following 2-element subsets: 



      set([1,2]), set([1,3]), set([2,3])


      Is there a way to do this in python?






      python set tuples subset




      python set tuples subset






      share|improve this question















      share|improve this question













      share|improve this question




      share|improve this question








      edited Mar 19 '16 at 14:19









      omerbp

      2,49732038




      2,49732038










      asked Sep 11 '11 at 12:30









      John Manak

      7,4152562105




      7,4152562105
























          3 Answers
          3






          active

          oldest

          votes


















          26














          Seems like you want itertools.combinations:



          >>> list(itertools.combinations((1, 2, 3), 2))
          
[(1, 2), (1, 3), (2, 3)]


          If you want sets you'll have to convert them explicitly. If you don't mind an iterable instead of a list, and you're using Python 3, you can use map:



          >>> s = set((1, 2, 3))
          
>>> map(set, itertools.combinations(s, 2))
          
<map object at 0x10cdc26d8>


          To view all the results at once, you can pass the output of map to list. (In Python 2, the output of map is automatically a list.)



          >>> list(map(set, itertools.combinations(s, 2)))
          
[{1, 2}, {1, 3}, {2, 3}]


          However, if you know you'll need a list, a list comprehension is marginally better (h/t Jacob Bowyer):



          >>> [set(i) for i in itertools.combinations(s, 2)]
          
[{1, 2}, {1, 3}, {2, 3}]





          share|improve this answer























          • Damn it!, by the way your map can be done with a list comp [set(i) for i in itertools.combinations(s, 2))]
            – Jakob Bowyer
            Sep 11 '11 at 13:13



















          1














          This is a subset of the power set of {1, 2, 3} (or whatever set) containing all two-element sets.



          See the Python itertools documentation and search on the term "powerset" for a general answer to this problem.






          share|improve this answer





























            1














            Just to give another perspective, I looked for a way to iterate all subset of size 2 of {1.....N}, so I put itertools.combinations into test:



            import itertools
            
from time import time
            

            

            
N = 7000
            
lst = [i for i in xrange(N)]
            

            
st = time()
            
c1 = 0
            
for x in itertools.combinations(lst, 2):
            
    c1 += 1
            
print "combinations: %f" % (time()-st)
            

            
st = time()
            
c2=0
            
for x in xrange(N):
            
    for y in xrange(x):
            
        c2 += 1
            
print "double loop: %f" % (time()-st)
            
print "c1=%d,c2=%d" % (c1,c2)
            

            
# prints:
            
#combinations: 4.247000
            
#double loop: 3.479000
            
# c1=24496500,c2=24496500


            So I guess you should not always turn into the general solution.... If you know in advance the size of the subset you want, it should be more efficient to iterate using for loops.



            Also note that you should not iterate over list(itertools.combinations(lst, 2)) since this move creates the list (and much slower than using the generator itself).






            share|improve this answer



















            • 2




              These two tests don't do the same thing. itertools.combinations actually creates a tuple; your nested loop doesn't create a tuple.
              – senderle
              Dec 4 '17 at 15:30






            • 2




              I did a quick test. If you actually need to create tuples inside the nested loop, it's slower by 50%. Furthermore, if you don't need to use a for loop to process the output of itertools.combinations, you can get a substantial speedup with this generator expression: c3 = sum(1 for pair in itertools.combinations(lst, 2)). That runs about 40% faster than the fastest nested loop. There are always many subtleties to consider when optimizing this kind of code!
              – senderle
              Dec 4 '17 at 15:43











            Your Answer






            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: "1"
            };
            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',
            autoActivateHeartbeat: false,
            convertImagesToLinks: true,
            noModals: true,
            showLowRepImageUploadWarning: true,
            reputationToPostImages: 10,
            bindNavPrevention: true,
            postfix: "",
            imageUploader: {
            brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
            contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
            allowUrls: true
            },
            onDemand: true,
            discardSelector: ".discard-answer"
            ,immediatelyShowMarkdownHelp:true
            });


            }
            });














            draft saved

            draft discarded


















            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f7378180%2fgenerate-all-subsets-of-size-k-containing-k-elements-in-python%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown

























            3 Answers
            3






            active

            oldest

            votes








            3 Answers
            3






            active

            oldest

            votes









            active

            oldest

            votes






            active

            oldest

            votes









            26














            Seems like you want itertools.combinations:



            >>> list(itertools.combinations((1, 2, 3), 2))
            
[(1, 2), (1, 3), (2, 3)]


            If you want sets you'll have to convert them explicitly. If you don't mind an iterable instead of a list, and you're using Python 3, you can use map:



            >>> s = set((1, 2, 3))
            
>>> map(set, itertools.combinations(s, 2))
            
<map object at 0x10cdc26d8>


            To view all the results at once, you can pass the output of map to list. (In Python 2, the output of map is automatically a list.)



            >>> list(map(set, itertools.combinations(s, 2)))
            
[{1, 2}, {1, 3}, {2, 3}]


            However, if you know you'll need a list, a list comprehension is marginally better (h/t Jacob Bowyer):



            >>> [set(i) for i in itertools.combinations(s, 2)]
            
[{1, 2}, {1, 3}, {2, 3}]





            share|improve this answer























            • Damn it!, by the way your map can be done with a list comp [set(i) for i in itertools.combinations(s, 2))]
              – Jakob Bowyer
              Sep 11 '11 at 13:13
















            26














            Seems like you want itertools.combinations:



            >>> list(itertools.combinations((1, 2, 3), 2))
            
[(1, 2), (1, 3), (2, 3)]


            If you want sets you'll have to convert them explicitly. If you don't mind an iterable instead of a list, and you're using Python 3, you can use map:



            >>> s = set((1, 2, 3))
            
>>> map(set, itertools.combinations(s, 2))
            
<map object at 0x10cdc26d8>


            To view all the results at once, you can pass the output of map to list. (In Python 2, the output of map is automatically a list.)



            >>> list(map(set, itertools.combinations(s, 2)))
            
[{1, 2}, {1, 3}, {2, 3}]


            However, if you know you'll need a list, a list comprehension is marginally better (h/t Jacob Bowyer):



            >>> [set(i) for i in itertools.combinations(s, 2)]
            
[{1, 2}, {1, 3}, {2, 3}]





            share|improve this answer























            • Damn it!, by the way your map can be done with a list comp [set(i) for i in itertools.combinations(s, 2))]
              – Jakob Bowyer
              Sep 11 '11 at 13:13














            26












            26








            26






            Seems like you want itertools.combinations:



            >>> list(itertools.combinations((1, 2, 3), 2))
            
[(1, 2), (1, 3), (2, 3)]


            If you want sets you'll have to convert them explicitly. If you don't mind an iterable instead of a list, and you're using Python 3, you can use map:



            >>> s = set((1, 2, 3))
            
>>> map(set, itertools.combinations(s, 2))
            
<map object at 0x10cdc26d8>


            To view all the results at once, you can pass the output of map to list. (In Python 2, the output of map is automatically a list.)



            >>> list(map(set, itertools.combinations(s, 2)))
            
[{1, 2}, {1, 3}, {2, 3}]


            However, if you know you'll need a list, a list comprehension is marginally better (h/t Jacob Bowyer):



            >>> [set(i) for i in itertools.combinations(s, 2)]
            
[{1, 2}, {1, 3}, {2, 3}]





            share|improve this answer














            Seems like you want itertools.combinations:



            >>> list(itertools.combinations((1, 2, 3), 2))
            
[(1, 2), (1, 3), (2, 3)]


            If you want sets you'll have to convert them explicitly. If you don't mind an iterable instead of a list, and you're using Python 3, you can use map:



            >>> s = set((1, 2, 3))
            
>>> map(set, itertools.combinations(s, 2))
            
<map object at 0x10cdc26d8>


            To view all the results at once, you can pass the output of map to list. (In Python 2, the output of map is automatically a list.)



            >>> list(map(set, itertools.combinations(s, 2)))
            
[{1, 2}, {1, 3}, {2, 3}]


            However, if you know you'll need a list, a list comprehension is marginally better (h/t Jacob Bowyer):



            >>> [set(i) for i in itertools.combinations(s, 2)]
            
[{1, 2}, {1, 3}, {2, 3}]






            share|improve this answer














            share|improve this answer



            share|improve this answer








            edited Nov 14 '18 at 16:36

























            answered Sep 11 '11 at 12:54









            senderle

            91.6k20165188




            91.6k20165188












            • Damn it!, by the way your map can be done with a list comp [set(i) for i in itertools.combinations(s, 2))]
              – Jakob Bowyer
              Sep 11 '11 at 13:13


















            • Damn it!, by the way your map can be done with a list comp [set(i) for i in itertools.combinations(s, 2))]
              – Jakob Bowyer
              Sep 11 '11 at 13:13
















            Damn it!, by the way your map can be done with a list comp [set(i) for i in itertools.combinations(s, 2))]
            – Jakob Bowyer
            Sep 11 '11 at 13:13




            Damn it!, by the way your map can be done with a list comp [set(i) for i in itertools.combinations(s, 2))]
            – Jakob Bowyer
            Sep 11 '11 at 13:13













            1














            This is a subset of the power set of {1, 2, 3} (or whatever set) containing all two-element sets.



            See the Python itertools documentation and search on the term "powerset" for a general answer to this problem.






            share|improve this answer


























              1














              This is a subset of the power set of {1, 2, 3} (or whatever set) containing all two-element sets.



              See the Python itertools documentation and search on the term "powerset" for a general answer to this problem.






              share|improve this answer
























                1












                1








                1






                This is a subset of the power set of {1, 2, 3} (or whatever set) containing all two-element sets.



                See the Python itertools documentation and search on the term "powerset" for a general answer to this problem.






                share|improve this answer












                This is a subset of the power set of {1, 2, 3} (or whatever set) containing all two-element sets.



                See the Python itertools documentation and search on the term "powerset" for a general answer to this problem.







                share|improve this answer












                share|improve this answer



                share|improve this answer










                answered Sep 11 '11 at 12:59









                Alex Reynolds

                67k47205295




                67k47205295























                    1














                    Just to give another perspective, I looked for a way to iterate all subset of size 2 of {1.....N}, so I put itertools.combinations into test:



                    import itertools
                    
from time import time
                    

                    

                    
N = 7000
                    
lst = [i for i in xrange(N)]
                    

                    
st = time()
                    
c1 = 0
                    
for x in itertools.combinations(lst, 2):
                    
    c1 += 1
                    
print "combinations: %f" % (time()-st)
                    

                    
st = time()
                    
c2=0
                    
for x in xrange(N):
                    
    for y in xrange(x):
                    
        c2 += 1
                    
print "double loop: %f" % (time()-st)
                    
print "c1=%d,c2=%d" % (c1,c2)
                    

                    
# prints:
                    
#combinations: 4.247000
                    
#double loop: 3.479000
                    
# c1=24496500,c2=24496500


                    So I guess you should not always turn into the general solution.... If you know in advance the size of the subset you want, it should be more efficient to iterate using for loops.



                    Also note that you should not iterate over list(itertools.combinations(lst, 2)) since this move creates the list (and much slower than using the generator itself).






                    share|improve this answer



















                    • 2




                      These two tests don't do the same thing. itertools.combinations actually creates a tuple; your nested loop doesn't create a tuple.
                      – senderle
                      Dec 4 '17 at 15:30






                    • 2




                      I did a quick test. If you actually need to create tuples inside the nested loop, it's slower by 50%. Furthermore, if you don't need to use a for loop to process the output of itertools.combinations, you can get a substantial speedup with this generator expression: c3 = sum(1 for pair in itertools.combinations(lst, 2)). That runs about 40% faster than the fastest nested loop. There are always many subtleties to consider when optimizing this kind of code!
                      – senderle
                      Dec 4 '17 at 15:43
















                    1














                    Just to give another perspective, I looked for a way to iterate all subset of size 2 of {1.....N}, so I put itertools.combinations into test:



                    import itertools
                    
from time import time
                    

                    

                    
N = 7000
                    
lst = [i for i in xrange(N)]
                    

                    
st = time()
                    
c1 = 0
                    
for x in itertools.combinations(lst, 2):
                    
    c1 += 1
                    
print "combinations: %f" % (time()-st)
                    

                    
st = time()
                    
c2=0
                    
for x in xrange(N):
                    
    for y in xrange(x):
                    
        c2 += 1
                    
print "double loop: %f" % (time()-st)
                    
print "c1=%d,c2=%d" % (c1,c2)
                    

                    
# prints:
                    
#combinations: 4.247000
                    
#double loop: 3.479000
                    
# c1=24496500,c2=24496500


                    So I guess you should not always turn into the general solution.... If you know in advance the size of the subset you want, it should be more efficient to iterate using for loops.



                    Also note that you should not iterate over list(itertools.combinations(lst, 2)) since this move creates the list (and much slower than using the generator itself).






                    share|improve this answer



















                    • 2




                      These two tests don't do the same thing. itertools.combinations actually creates a tuple; your nested loop doesn't create a tuple.
                      – senderle
                      Dec 4 '17 at 15:30






                    • 2




                      I did a quick test. If you actually need to create tuples inside the nested loop, it's slower by 50%. Furthermore, if you don't need to use a for loop to process the output of itertools.combinations, you can get a substantial speedup with this generator expression: c3 = sum(1 for pair in itertools.combinations(lst, 2)). That runs about 40% faster than the fastest nested loop. There are always many subtleties to consider when optimizing this kind of code!
                      – senderle
                      Dec 4 '17 at 15:43














                    1












                    1








                    1






                    Just to give another perspective, I looked for a way to iterate all subset of size 2 of {1.....N}, so I put itertools.combinations into test:



                    import itertools
                    
from time import time
                    

                    

                    
N = 7000
                    
lst = [i for i in xrange(N)]
                    

                    
st = time()
                    
c1 = 0
                    
for x in itertools.combinations(lst, 2):
                    
    c1 += 1
                    
print "combinations: %f" % (time()-st)
                    

                    
st = time()
                    
c2=0
                    
for x in xrange(N):
                    
    for y in xrange(x):
                    
        c2 += 1
                    
print "double loop: %f" % (time()-st)
                    
print "c1=%d,c2=%d" % (c1,c2)
                    

                    
# prints:
                    
#combinations: 4.247000
                    
#double loop: 3.479000
                    
# c1=24496500,c2=24496500


                    So I guess you should not always turn into the general solution.... If you know in advance the size of the subset you want, it should be more efficient to iterate using for loops.



                    Also note that you should not iterate over list(itertools.combinations(lst, 2)) since this move creates the list (and much slower than using the generator itself).






                    share|improve this answer














                    Just to give another perspective, I looked for a way to iterate all subset of size 2 of {1.....N}, so I put itertools.combinations into test:



                    import itertools
                    
from time import time
                    

                    

                    
N = 7000
                    
lst = [i for i in xrange(N)]
                    

                    
st = time()
                    
c1 = 0
                    
for x in itertools.combinations(lst, 2):
                    
    c1 += 1
                    
print "combinations: %f" % (time()-st)
                    

                    
st = time()
                    
c2=0
                    
for x in xrange(N):
                    
    for y in xrange(x):
                    
        c2 += 1
                    
print "double loop: %f" % (time()-st)
                    
print "c1=%d,c2=%d" % (c1,c2)
                    

                    
# prints:
                    
#combinations: 4.247000
                    
#double loop: 3.479000
                    
# c1=24496500,c2=24496500


                    So I guess you should not always turn into the general solution.... If you know in advance the size of the subset you want, it should be more efficient to iterate using for loops.



                    Also note that you should not iterate over list(itertools.combinations(lst, 2)) since this move creates the list (and much slower than using the generator itself).







                    share|improve this answer














                    share|improve this answer



                    share|improve this answer








                    edited Mar 20 '16 at 8:05

























                    answered Mar 19 '16 at 13:26









                    omerbp

                    2,49732038




                    2,49732038








                    • 2




                      These two tests don't do the same thing. itertools.combinations actually creates a tuple; your nested loop doesn't create a tuple.
                      – senderle
                      Dec 4 '17 at 15:30






                    • 2




                      I did a quick test. If you actually need to create tuples inside the nested loop, it's slower by 50%. Furthermore, if you don't need to use a for loop to process the output of itertools.combinations, you can get a substantial speedup with this generator expression: c3 = sum(1 for pair in itertools.combinations(lst, 2)). That runs about 40% faster than the fastest nested loop. There are always many subtleties to consider when optimizing this kind of code!
                      – senderle
                      Dec 4 '17 at 15:43














                    • 2




                      These two tests don't do the same thing. itertools.combinations actually creates a tuple; your nested loop doesn't create a tuple.
                      – senderle
                      Dec 4 '17 at 15:30






                    • 2




                      I did a quick test. If you actually need to create tuples inside the nested loop, it's slower by 50%. Furthermore, if you don't need to use a for loop to process the output of itertools.combinations, you can get a substantial speedup with this generator expression: c3 = sum(1 for pair in itertools.combinations(lst, 2)). That runs about 40% faster than the fastest nested loop. There are always many subtleties to consider when optimizing this kind of code!
                      – senderle
                      Dec 4 '17 at 15:43








                    2




                    2




                    These two tests don't do the same thing. itertools.combinations actually creates a tuple; your nested loop doesn't create a tuple.
                    – senderle
                    Dec 4 '17 at 15:30




                    These two tests don't do the same thing. itertools.combinations actually creates a tuple; your nested loop doesn't create a tuple.
                    – senderle
                    Dec 4 '17 at 15:30




                    2




                    2




                    I did a quick test. If you actually need to create tuples inside the nested loop, it's slower by 50%. Furthermore, if you don't need to use a for loop to process the output of itertools.combinations, you can get a substantial speedup with this generator expression: c3 = sum(1 for pair in itertools.combinations(lst, 2)). That runs about 40% faster than the fastest nested loop. There are always many subtleties to consider when optimizing this kind of code!
                    – senderle
                    Dec 4 '17 at 15:43




                    I did a quick test. If you actually need to create tuples inside the nested loop, it's slower by 50%. Furthermore, if you don't need to use a for loop to process the output of itertools.combinations, you can get a substantial speedup with this generator expression: c3 = sum(1 for pair in itertools.combinations(lst, 2)). That runs about 40% faster than the fastest nested loop. There are always many subtleties to consider when optimizing this kind of code!
                    – senderle
                    Dec 4 '17 at 15:43


















                    draft saved

                    draft discarded




















































                    Thanks for contributing an answer to Stack Overflow!


                    • Please be sure to answer the question. Provide details and share your research!

                    But avoid …



                    • Asking for help, clarification, or responding to other answers.

                    • Making statements based on opinion; back them up with references or personal experience.


                    To learn more, see our tips on writing great answers.





                    Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


                    Please pay close attention to the following guidance:


                    • Please be sure to answer the question. Provide details and share your research!

                    But avoid …



                    • Asking for help, clarification, or responding to other answers.

                    • Making statements based on opinion; back them up with references or personal experience.


                    To learn more, see our tips on writing great answers.




                    draft saved


                    draft discarded














                    StackExchange.ready(
                    function () {
                    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f7378180%2fgenerate-all-subsets-of-size-k-containing-k-elements-in-python%23new-answer', 'question_page');
                    }
                    );

                    Post as a guest















                    Required, but never shown





















































                    Required, but never shown














                    Required, but never shown












                    Required, but never shown







                    Required, but never shown

































                    Required, but never shown














                    Required, but never shown












                    Required, but never shown







                    Required, but never shown







                    -

                    Popular posts from this blog

                    Guess what letter conforming each word

                    Image
                    6 $begingroup$ This is an entry in the Fortnightly Topic Challenge #41: Short and Sweet. 1 letter only could be mean anything . With an additional letter in front , could be used as medicine component and something you definitely learn or at least heard once. Add another letter in front , you would possibly hear that many times . Add an additional letter in front , you would found an independent country . With an additional letter, in the end , you would found something related to apple . Add another letter in the end , you would found something bad . Hint: Each letter is unique . word knowledge letters chemistry share | improve this question ...
                    Read more

                    Port of Spain

                    Image
                    For ports in the country of Spain, see List of ports in Spain. City in City of Port of Spain, Trinidad and Tobago Port of Spain City City of Port of Spain Top to bottom (left to right): Skyline of Port of Spain from Gulf of Paria; National Academy for the Performing Arts, Independence Square, Eric Williams Plaza; MovieTowne, Port of Port of Spain Motto(s):  "We Gather Strength As We Go Along" Port of Spain Coordinates: 10°40′N 61°31′W  /  10.667°N 61.517°W  / 10.667; -61.517 Coordinates: 10°40′N 61°31′W  /  10.667°N 61.517°W  / 10.667; -61.517 Country   Trinidad and Tobago Jurisdiction City of Port of Spain Settled 1560 Incorporated (town) 1853 Incorporated (city) 1914 Government  • Mayor Joel Martinez  • Governing body City Corporation Area [1]  • City 12 km 2 (5 sq mi) Elevation [2] 66 m (217 ft) Population (2011) [1]  • City 37,074  • Rank 3rd  • Density 3,090/km 2 (8,000/sq mi)...
                    Read more

                    Run scheduled task as local user group (not BUILTIN)

                    Image
                    0 I am trying to run a scheduled task with User Group (not a single user). This is working fine when I in the field "when running a task, use the following user account:" insert BUILTIN User Group (for example: Administrators or Users). But when I try it with the created Local User Group (example: TestGroup) it is not working. The Users in the TestGroup are the same as in the Administrators group. What could be the problem? Are there some restrictions to the Created User Group compared to BUILTINUsers? scheduled-tasks taskscheduler windowstaskschedule share | improve this question asked Nov 15 '18 at 15:36 Far...
                    Read more