Get subsets of a set given as a list











up vote
5
down vote

favorite
1












This code is meant to create a list of subsets of a given set which is represented as a list.



I'm doing this to improve my style and to improve my knowledge of fundamental algorithms/data structures for an upcoming coding interview.



def subsets(s):
if s == :
return [s]
sets = [s]
for i in range(0, len(s)):
tmp_subsets = subsets(s[:i] + s[i+1:])
for subset in tmp_subsets:
if subset not in sets:
sets.append(subset)
return sets


I'm also not sure if using the set() data structure would be considered cheating in an interview context.



If there are any ideas about how to improve its performance without significantly compromising on readability I would also be open to that.










share|improve this question


























    up vote
    5
    down vote

    favorite
    1












    This code is meant to create a list of subsets of a given set which is represented as a list.



    I'm doing this to improve my style and to improve my knowledge of fundamental algorithms/data structures for an upcoming coding interview.



    def subsets(s):
    if s == :
    return [s]
    sets = [s]
    for i in range(0, len(s)):
    tmp_subsets = subsets(s[:i] + s[i+1:])
    for subset in tmp_subsets:
    if subset not in sets:
    sets.append(subset)
    return sets


    I'm also not sure if using the set() data structure would be considered cheating in an interview context.



    If there are any ideas about how to improve its performance without significantly compromising on readability I would also be open to that.










    share|improve this question
























      up vote
      5
      down vote

      favorite
      1









      up vote
      5
      down vote

      favorite
      1






      1





      This code is meant to create a list of subsets of a given set which is represented as a list.



      I'm doing this to improve my style and to improve my knowledge of fundamental algorithms/data structures for an upcoming coding interview.



      def subsets(s):
      if s == :
      return [s]
      sets = [s]
      for i in range(0, len(s)):
      tmp_subsets = subsets(s[:i] + s[i+1:])
      for subset in tmp_subsets:
      if subset not in sets:
      sets.append(subset)
      return sets


      I'm also not sure if using the set() data structure would be considered cheating in an interview context.



      If there are any ideas about how to improve its performance without significantly compromising on readability I would also be open to that.










      share|improve this question













      This code is meant to create a list of subsets of a given set which is represented as a list.



      I'm doing this to improve my style and to improve my knowledge of fundamental algorithms/data structures for an upcoming coding interview.



      def subsets(s):
      if s == :
      return [s]
      sets = [s]
      for i in range(0, len(s)):
      tmp_subsets = subsets(s[:i] + s[i+1:])
      for subset in tmp_subsets:
      if subset not in sets:
      sets.append(subset)
      return sets


      I'm also not sure if using the set() data structure would be considered cheating in an interview context.



      If there are any ideas about how to improve its performance without significantly compromising on readability I would also be open to that.







      python performance python-3.x recursion reinventing-the-wheel






      share|improve this question













      share|improve this question











      share|improve this question




      share|improve this question










      asked Nov 20 '16 at 21:40









      cycloidistic

      1701211




      1701211






















          3 Answers
          3






          active

          oldest

          votes

















          up vote
          6
          down vote













          This is unnecessary:




          if s == :
          return [s]



          You can safely remove it, the program will still work.



          This step is not so great:




          if subset not in sets:
          sets.append(subset)



          For two reasons:




          • Checking if a list contains some items is an $O(n)$ operation

          • Comparing sets is not free either


          A more efficient solution is to count from 0 until 1 << n, and use the bitmap of the count to decide the elements that are part of a subset.



          def subsets(s):
          sets =
          for i in range(1 << len(s)):
          subset = [s[bit] for bit in range(len(s)) if is_bit_set(i, bit)]
          sets.append(subset)
          return sets

          def is_bit_set(num, bit):
          return num & (1 << bit) > 0


          That is, in a subset, each element may be either present, or not. So each element has only 2 possible states: in or out. 1 or 0. If we look at the binary representation of numbers from 0 to 2^n -1, where n is the number of elements, for example when n=3, we have:



              cba
          0 = 000
          1 = 001
          2 = 010
          3 = 011
          4 = 100
          5 = 101
          6 = 110
          7 = 111


          There are 8 possible subsets, and the bits represent whether an element is in the subset or not.
          This is the idea used by the program:




          • The outer loop goes from 0 until 2^n - 1.

          • The inner loop goes from 0 until n - 1.


          • 1 << bit is 1 shifted to the left bit times.


          For example, when i = 3, that corresponds to bits 011.
          We loop from 0 until 2, comparing i against 001, 010, and 100.
          For these values, the expression i & (1 << bit) will be evaluated as
          011 & 001 = 001, 011 & 010 = 010, and 011 & 100 = 000, respectively.
          The first two are greater than 0, the last one is not.






          share|improve this answer























          • Please explain in more detail what you are doing instead of the "if subset not in sets: ..." part.
            – Nikolas Rieble
            Nov 20 '16 at 22:20










          • @NikolasRieble I added more explanation about the bit shifting algorithm.
            – janos
            Nov 20 '16 at 22:45










          • @janos Thanks for the answer. Removing the first return makes sense. Also, it's good that you mentioned that not in is O(n). That will be useful for the future. The fact that you can represent a set as a bitmap and that all the subsets are just all the numbers from 0 to len(s) is quite elegant. I never thought about it that way. I'll be sure to use more bitmaps in the future :)
            – cycloidistic
            Nov 21 '16 at 6:10










          • @cycloidistic From what I can see it is more that representing all possible permutations of something being in or out is easily represented using binary.
            – Graipher
            Nov 21 '16 at 7:31










          • Representing the subsets as bits value is more efficient but much less readable, I'd put the i & (1 << bit) > 0 part in a function called something like is_subset_present or at least put a comment explaining what's happening. Using bit manipulation is fine, but with no explanation it would look bad to me in an interview, I think code should be as efficient as possible but also readable.
            – ChatterOne
            Nov 21 '16 at 8:20


















          up vote
          4
          down vote













          No need to reinvent the wheel here.
          You can get subsets with length r as tuples of a set s by using itertools.combinations.
          Doing this for all possible subset lengths:



          def subsets(s):
          for cardinality in range(len(s) + 1):
          yield from combinations(s, cardinality)


          If you want the subsets as sets instead of tuples and within a list you can invoke the method above via:



          sub_sets = [set(sub_set) for sub_set in subsets(s)]





          share|improve this answer





















          • Thanks for the answer. I like how succinct it is. I'll definitely look into itertools more in the future :)
            – cycloidistic
            Nov 22 '16 at 7:27


















          up vote
          4
          down vote













          @janos Answer is great, but it was easier for me to think about it with one less bitwise operations.



          def subsets(s):
          """
          :type s: list
          """
          sets =
          for i in range(2**len(s)):
          subset =
          for j in range(len(s)):
          if i & (1 << j) > 0:
          subset.append(s[j])
          sets.append(subset)
          return sets


          Explanation:



          So we know there are $2^n$ subsets in a set where $n$ is the size of the set. So we loop through all those numbers: for i in range(2**len(s)):.



          This gives us a range $0 - 2^n$ which corresponds to these binary numbers (example of a set of size 3):



          0 = 000
          1 = 001
          2 = 010
          3 = 011
          4 = 100
          5 = 101
          6 = 110
          7 = 111
          ...
          n - 1 = 0b(n-1)


          As you can see, the binary representation is every subset possible where 1 means it is in the set and 0 means it is not.



          Now we just need to use these indexes to find out what should be in each set.
          (While under the hood the numbers are stored as binary, if you try printing them you'll see an int.)



          So we'll do a nested for loop: for j in range(len(s)):



          Here we do need to do a bitwise operation: i & (1 << j) > 0 where i is the current index of the loop described earlier. j is the index of which element in the second loop we're at.



          1 << j just converts the index to the binary representation. For example, the first element (at index 0): 1 << 0 = 001, or the second 1 << 1 = 010, etc.



          The & operator just makes sure the indexes match up. 000 & 101 = 0 but 100 & 101 = 100. So anytime it is greater than 0, it means we've come across an element that belongs in our set.



          Let's take the set {a, b, c} and loop through our range. At 0, 0 & anything = 0, so we have the empty set.



          Let's skip to i = 6: 6 & (1 << 0) > 0 returns false because in binary: 110 & 001 = 0. But the second iteration (j = 1) 6 & (1 << 1) > 0 returns true (110 & 010 = 1). And it will for the 3rd element too. Thus giving you the subset {b, c}.



          The runtime of this algorithm is $O(2^n)$ if that isn't clear! Hope this helps!






          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: "196"
            };
            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: true,
            showLowRepImageUploadWarning: true,
            reputationToPostImages: null,
            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%2fcodereview.stackexchange.com%2fquestions%2f147633%2fget-subsets-of-a-set-given-as-a-list%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








            up vote
            6
            down vote













            This is unnecessary:




            if s == :
            return [s]



            You can safely remove it, the program will still work.



            This step is not so great:




            if subset not in sets:
            sets.append(subset)



            For two reasons:




            • Checking if a list contains some items is an $O(n)$ operation

            • Comparing sets is not free either


            A more efficient solution is to count from 0 until 1 << n, and use the bitmap of the count to decide the elements that are part of a subset.



            def subsets(s):
            sets =
            for i in range(1 << len(s)):
            subset = [s[bit] for bit in range(len(s)) if is_bit_set(i, bit)]
            sets.append(subset)
            return sets

            def is_bit_set(num, bit):
            return num & (1 << bit) > 0


            That is, in a subset, each element may be either present, or not. So each element has only 2 possible states: in or out. 1 or 0. If we look at the binary representation of numbers from 0 to 2^n -1, where n is the number of elements, for example when n=3, we have:



                cba
            0 = 000
            1 = 001
            2 = 010
            3 = 011
            4 = 100
            5 = 101
            6 = 110
            7 = 111


            There are 8 possible subsets, and the bits represent whether an element is in the subset or not.
            This is the idea used by the program:




            • The outer loop goes from 0 until 2^n - 1.

            • The inner loop goes from 0 until n - 1.


            • 1 << bit is 1 shifted to the left bit times.


            For example, when i = 3, that corresponds to bits 011.
            We loop from 0 until 2, comparing i against 001, 010, and 100.
            For these values, the expression i & (1 << bit) will be evaluated as
            011 & 001 = 001, 011 & 010 = 010, and 011 & 100 = 000, respectively.
            The first two are greater than 0, the last one is not.






            share|improve this answer























            • Please explain in more detail what you are doing instead of the "if subset not in sets: ..." part.
              – Nikolas Rieble
              Nov 20 '16 at 22:20










            • @NikolasRieble I added more explanation about the bit shifting algorithm.
              – janos
              Nov 20 '16 at 22:45










            • @janos Thanks for the answer. Removing the first return makes sense. Also, it's good that you mentioned that not in is O(n). That will be useful for the future. The fact that you can represent a set as a bitmap and that all the subsets are just all the numbers from 0 to len(s) is quite elegant. I never thought about it that way. I'll be sure to use more bitmaps in the future :)
              – cycloidistic
              Nov 21 '16 at 6:10










            • @cycloidistic From what I can see it is more that representing all possible permutations of something being in or out is easily represented using binary.
              – Graipher
              Nov 21 '16 at 7:31










            • Representing the subsets as bits value is more efficient but much less readable, I'd put the i & (1 << bit) > 0 part in a function called something like is_subset_present or at least put a comment explaining what's happening. Using bit manipulation is fine, but with no explanation it would look bad to me in an interview, I think code should be as efficient as possible but also readable.
              – ChatterOne
              Nov 21 '16 at 8:20















            up vote
            6
            down vote













            This is unnecessary:




            if s == :
            return [s]



            You can safely remove it, the program will still work.



            This step is not so great:




            if subset not in sets:
            sets.append(subset)



            For two reasons:




            • Checking if a list contains some items is an $O(n)$ operation

            • Comparing sets is not free either


            A more efficient solution is to count from 0 until 1 << n, and use the bitmap of the count to decide the elements that are part of a subset.



            def subsets(s):
            sets =
            for i in range(1 << len(s)):
            subset = [s[bit] for bit in range(len(s)) if is_bit_set(i, bit)]
            sets.append(subset)
            return sets

            def is_bit_set(num, bit):
            return num & (1 << bit) > 0


            That is, in a subset, each element may be either present, or not. So each element has only 2 possible states: in or out. 1 or 0. If we look at the binary representation of numbers from 0 to 2^n -1, where n is the number of elements, for example when n=3, we have:



                cba
            0 = 000
            1 = 001
            2 = 010
            3 = 011
            4 = 100
            5 = 101
            6 = 110
            7 = 111


            There are 8 possible subsets, and the bits represent whether an element is in the subset or not.
            This is the idea used by the program:




            • The outer loop goes from 0 until 2^n - 1.

            • The inner loop goes from 0 until n - 1.


            • 1 << bit is 1 shifted to the left bit times.


            For example, when i = 3, that corresponds to bits 011.
            We loop from 0 until 2, comparing i against 001, 010, and 100.
            For these values, the expression i & (1 << bit) will be evaluated as
            011 & 001 = 001, 011 & 010 = 010, and 011 & 100 = 000, respectively.
            The first two are greater than 0, the last one is not.






            share|improve this answer























            • Please explain in more detail what you are doing instead of the "if subset not in sets: ..." part.
              – Nikolas Rieble
              Nov 20 '16 at 22:20










            • @NikolasRieble I added more explanation about the bit shifting algorithm.
              – janos
              Nov 20 '16 at 22:45










            • @janos Thanks for the answer. Removing the first return makes sense. Also, it's good that you mentioned that not in is O(n). That will be useful for the future. The fact that you can represent a set as a bitmap and that all the subsets are just all the numbers from 0 to len(s) is quite elegant. I never thought about it that way. I'll be sure to use more bitmaps in the future :)
              – cycloidistic
              Nov 21 '16 at 6:10










            • @cycloidistic From what I can see it is more that representing all possible permutations of something being in or out is easily represented using binary.
              – Graipher
              Nov 21 '16 at 7:31










            • Representing the subsets as bits value is more efficient but much less readable, I'd put the i & (1 << bit) > 0 part in a function called something like is_subset_present or at least put a comment explaining what's happening. Using bit manipulation is fine, but with no explanation it would look bad to me in an interview, I think code should be as efficient as possible but also readable.
              – ChatterOne
              Nov 21 '16 at 8:20













            up vote
            6
            down vote










            up vote
            6
            down vote









            This is unnecessary:




            if s == :
            return [s]



            You can safely remove it, the program will still work.



            This step is not so great:




            if subset not in sets:
            sets.append(subset)



            For two reasons:




            • Checking if a list contains some items is an $O(n)$ operation

            • Comparing sets is not free either


            A more efficient solution is to count from 0 until 1 << n, and use the bitmap of the count to decide the elements that are part of a subset.



            def subsets(s):
            sets =
            for i in range(1 << len(s)):
            subset = [s[bit] for bit in range(len(s)) if is_bit_set(i, bit)]
            sets.append(subset)
            return sets

            def is_bit_set(num, bit):
            return num & (1 << bit) > 0


            That is, in a subset, each element may be either present, or not. So each element has only 2 possible states: in or out. 1 or 0. If we look at the binary representation of numbers from 0 to 2^n -1, where n is the number of elements, for example when n=3, we have:



                cba
            0 = 000
            1 = 001
            2 = 010
            3 = 011
            4 = 100
            5 = 101
            6 = 110
            7 = 111


            There are 8 possible subsets, and the bits represent whether an element is in the subset or not.
            This is the idea used by the program:




            • The outer loop goes from 0 until 2^n - 1.

            • The inner loop goes from 0 until n - 1.


            • 1 << bit is 1 shifted to the left bit times.


            For example, when i = 3, that corresponds to bits 011.
            We loop from 0 until 2, comparing i against 001, 010, and 100.
            For these values, the expression i & (1 << bit) will be evaluated as
            011 & 001 = 001, 011 & 010 = 010, and 011 & 100 = 000, respectively.
            The first two are greater than 0, the last one is not.






            share|improve this answer














            This is unnecessary:




            if s == :
            return [s]



            You can safely remove it, the program will still work.



            This step is not so great:




            if subset not in sets:
            sets.append(subset)



            For two reasons:




            • Checking if a list contains some items is an $O(n)$ operation

            • Comparing sets is not free either


            A more efficient solution is to count from 0 until 1 << n, and use the bitmap of the count to decide the elements that are part of a subset.



            def subsets(s):
            sets =
            for i in range(1 << len(s)):
            subset = [s[bit] for bit in range(len(s)) if is_bit_set(i, bit)]
            sets.append(subset)
            return sets

            def is_bit_set(num, bit):
            return num & (1 << bit) > 0


            That is, in a subset, each element may be either present, or not. So each element has only 2 possible states: in or out. 1 or 0. If we look at the binary representation of numbers from 0 to 2^n -1, where n is the number of elements, for example when n=3, we have:



                cba
            0 = 000
            1 = 001
            2 = 010
            3 = 011
            4 = 100
            5 = 101
            6 = 110
            7 = 111


            There are 8 possible subsets, and the bits represent whether an element is in the subset or not.
            This is the idea used by the program:




            • The outer loop goes from 0 until 2^n - 1.

            • The inner loop goes from 0 until n - 1.


            • 1 << bit is 1 shifted to the left bit times.


            For example, when i = 3, that corresponds to bits 011.
            We loop from 0 until 2, comparing i against 001, 010, and 100.
            For these values, the expression i & (1 << bit) will be evaluated as
            011 & 001 = 001, 011 & 010 = 010, and 011 & 100 = 000, respectively.
            The first two are greater than 0, the last one is not.







            share|improve this answer














            share|improve this answer



            share|improve this answer








            edited Nov 21 '16 at 8:46

























            answered Nov 20 '16 at 22:04









            janos

            96.6k12124350




            96.6k12124350












            • Please explain in more detail what you are doing instead of the "if subset not in sets: ..." part.
              – Nikolas Rieble
              Nov 20 '16 at 22:20










            • @NikolasRieble I added more explanation about the bit shifting algorithm.
              – janos
              Nov 20 '16 at 22:45










            • @janos Thanks for the answer. Removing the first return makes sense. Also, it's good that you mentioned that not in is O(n). That will be useful for the future. The fact that you can represent a set as a bitmap and that all the subsets are just all the numbers from 0 to len(s) is quite elegant. I never thought about it that way. I'll be sure to use more bitmaps in the future :)
              – cycloidistic
              Nov 21 '16 at 6:10










            • @cycloidistic From what I can see it is more that representing all possible permutations of something being in or out is easily represented using binary.
              – Graipher
              Nov 21 '16 at 7:31










            • Representing the subsets as bits value is more efficient but much less readable, I'd put the i & (1 << bit) > 0 part in a function called something like is_subset_present or at least put a comment explaining what's happening. Using bit manipulation is fine, but with no explanation it would look bad to me in an interview, I think code should be as efficient as possible but also readable.
              – ChatterOne
              Nov 21 '16 at 8:20


















            • Please explain in more detail what you are doing instead of the "if subset not in sets: ..." part.
              – Nikolas Rieble
              Nov 20 '16 at 22:20










            • @NikolasRieble I added more explanation about the bit shifting algorithm.
              – janos
              Nov 20 '16 at 22:45










            • @janos Thanks for the answer. Removing the first return makes sense. Also, it's good that you mentioned that not in is O(n). That will be useful for the future. The fact that you can represent a set as a bitmap and that all the subsets are just all the numbers from 0 to len(s) is quite elegant. I never thought about it that way. I'll be sure to use more bitmaps in the future :)
              – cycloidistic
              Nov 21 '16 at 6:10










            • @cycloidistic From what I can see it is more that representing all possible permutations of something being in or out is easily represented using binary.
              – Graipher
              Nov 21 '16 at 7:31










            • Representing the subsets as bits value is more efficient but much less readable, I'd put the i & (1 << bit) > 0 part in a function called something like is_subset_present or at least put a comment explaining what's happening. Using bit manipulation is fine, but with no explanation it would look bad to me in an interview, I think code should be as efficient as possible but also readable.
              – ChatterOne
              Nov 21 '16 at 8:20
















            Please explain in more detail what you are doing instead of the "if subset not in sets: ..." part.
            – Nikolas Rieble
            Nov 20 '16 at 22:20




            Please explain in more detail what you are doing instead of the "if subset not in sets: ..." part.
            – Nikolas Rieble
            Nov 20 '16 at 22:20












            @NikolasRieble I added more explanation about the bit shifting algorithm.
            – janos
            Nov 20 '16 at 22:45




            @NikolasRieble I added more explanation about the bit shifting algorithm.
            – janos
            Nov 20 '16 at 22:45












            @janos Thanks for the answer. Removing the first return makes sense. Also, it's good that you mentioned that not in is O(n). That will be useful for the future. The fact that you can represent a set as a bitmap and that all the subsets are just all the numbers from 0 to len(s) is quite elegant. I never thought about it that way. I'll be sure to use more bitmaps in the future :)
            – cycloidistic
            Nov 21 '16 at 6:10




            @janos Thanks for the answer. Removing the first return makes sense. Also, it's good that you mentioned that not in is O(n). That will be useful for the future. The fact that you can represent a set as a bitmap and that all the subsets are just all the numbers from 0 to len(s) is quite elegant. I never thought about it that way. I'll be sure to use more bitmaps in the future :)
            – cycloidistic
            Nov 21 '16 at 6:10












            @cycloidistic From what I can see it is more that representing all possible permutations of something being in or out is easily represented using binary.
            – Graipher
            Nov 21 '16 at 7:31




            @cycloidistic From what I can see it is more that representing all possible permutations of something being in or out is easily represented using binary.
            – Graipher
            Nov 21 '16 at 7:31












            Representing the subsets as bits value is more efficient but much less readable, I'd put the i & (1 << bit) > 0 part in a function called something like is_subset_present or at least put a comment explaining what's happening. Using bit manipulation is fine, but with no explanation it would look bad to me in an interview, I think code should be as efficient as possible but also readable.
            – ChatterOne
            Nov 21 '16 at 8:20




            Representing the subsets as bits value is more efficient but much less readable, I'd put the i & (1 << bit) > 0 part in a function called something like is_subset_present or at least put a comment explaining what's happening. Using bit manipulation is fine, but with no explanation it would look bad to me in an interview, I think code should be as efficient as possible but also readable.
            – ChatterOne
            Nov 21 '16 at 8:20












            up vote
            4
            down vote













            No need to reinvent the wheel here.
            You can get subsets with length r as tuples of a set s by using itertools.combinations.
            Doing this for all possible subset lengths:



            def subsets(s):
            for cardinality in range(len(s) + 1):
            yield from combinations(s, cardinality)


            If you want the subsets as sets instead of tuples and within a list you can invoke the method above via:



            sub_sets = [set(sub_set) for sub_set in subsets(s)]





            share|improve this answer





















            • Thanks for the answer. I like how succinct it is. I'll definitely look into itertools more in the future :)
              – cycloidistic
              Nov 22 '16 at 7:27















            up vote
            4
            down vote













            No need to reinvent the wheel here.
            You can get subsets with length r as tuples of a set s by using itertools.combinations.
            Doing this for all possible subset lengths:



            def subsets(s):
            for cardinality in range(len(s) + 1):
            yield from combinations(s, cardinality)


            If you want the subsets as sets instead of tuples and within a list you can invoke the method above via:



            sub_sets = [set(sub_set) for sub_set in subsets(s)]





            share|improve this answer





















            • Thanks for the answer. I like how succinct it is. I'll definitely look into itertools more in the future :)
              – cycloidistic
              Nov 22 '16 at 7:27













            up vote
            4
            down vote










            up vote
            4
            down vote









            No need to reinvent the wheel here.
            You can get subsets with length r as tuples of a set s by using itertools.combinations.
            Doing this for all possible subset lengths:



            def subsets(s):
            for cardinality in range(len(s) + 1):
            yield from combinations(s, cardinality)


            If you want the subsets as sets instead of tuples and within a list you can invoke the method above via:



            sub_sets = [set(sub_set) for sub_set in subsets(s)]





            share|improve this answer












            No need to reinvent the wheel here.
            You can get subsets with length r as tuples of a set s by using itertools.combinations.
            Doing this for all possible subset lengths:



            def subsets(s):
            for cardinality in range(len(s) + 1):
            yield from combinations(s, cardinality)


            If you want the subsets as sets instead of tuples and within a list you can invoke the method above via:



            sub_sets = [set(sub_set) for sub_set in subsets(s)]






            share|improve this answer












            share|improve this answer



            share|improve this answer










            answered Nov 21 '16 at 8:53









            Richard Neumann

            1,856722




            1,856722












            • Thanks for the answer. I like how succinct it is. I'll definitely look into itertools more in the future :)
              – cycloidistic
              Nov 22 '16 at 7:27


















            • Thanks for the answer. I like how succinct it is. I'll definitely look into itertools more in the future :)
              – cycloidistic
              Nov 22 '16 at 7:27
















            Thanks for the answer. I like how succinct it is. I'll definitely look into itertools more in the future :)
            – cycloidistic
            Nov 22 '16 at 7:27




            Thanks for the answer. I like how succinct it is. I'll definitely look into itertools more in the future :)
            – cycloidistic
            Nov 22 '16 at 7:27










            up vote
            4
            down vote













            @janos Answer is great, but it was easier for me to think about it with one less bitwise operations.



            def subsets(s):
            """
            :type s: list
            """
            sets =
            for i in range(2**len(s)):
            subset =
            for j in range(len(s)):
            if i & (1 << j) > 0:
            subset.append(s[j])
            sets.append(subset)
            return sets


            Explanation:



            So we know there are $2^n$ subsets in a set where $n$ is the size of the set. So we loop through all those numbers: for i in range(2**len(s)):.



            This gives us a range $0 - 2^n$ which corresponds to these binary numbers (example of a set of size 3):



            0 = 000
            1 = 001
            2 = 010
            3 = 011
            4 = 100
            5 = 101
            6 = 110
            7 = 111
            ...
            n - 1 = 0b(n-1)


            As you can see, the binary representation is every subset possible where 1 means it is in the set and 0 means it is not.



            Now we just need to use these indexes to find out what should be in each set.
            (While under the hood the numbers are stored as binary, if you try printing them you'll see an int.)



            So we'll do a nested for loop: for j in range(len(s)):



            Here we do need to do a bitwise operation: i & (1 << j) > 0 where i is the current index of the loop described earlier. j is the index of which element in the second loop we're at.



            1 << j just converts the index to the binary representation. For example, the first element (at index 0): 1 << 0 = 001, or the second 1 << 1 = 010, etc.



            The & operator just makes sure the indexes match up. 000 & 101 = 0 but 100 & 101 = 100. So anytime it is greater than 0, it means we've come across an element that belongs in our set.



            Let's take the set {a, b, c} and loop through our range. At 0, 0 & anything = 0, so we have the empty set.



            Let's skip to i = 6: 6 & (1 << 0) > 0 returns false because in binary: 110 & 001 = 0. But the second iteration (j = 1) 6 & (1 << 1) > 0 returns true (110 & 010 = 1). And it will for the 3rd element too. Thus giving you the subset {b, c}.



            The runtime of this algorithm is $O(2^n)$ if that isn't clear! Hope this helps!






            share|improve this answer



























              up vote
              4
              down vote













              @janos Answer is great, but it was easier for me to think about it with one less bitwise operations.



              def subsets(s):
              """
              :type s: list
              """
              sets =
              for i in range(2**len(s)):
              subset =
              for j in range(len(s)):
              if i & (1 << j) > 0:
              subset.append(s[j])
              sets.append(subset)
              return sets


              Explanation:



              So we know there are $2^n$ subsets in a set where $n$ is the size of the set. So we loop through all those numbers: for i in range(2**len(s)):.



              This gives us a range $0 - 2^n$ which corresponds to these binary numbers (example of a set of size 3):



              0 = 000
              1 = 001
              2 = 010
              3 = 011
              4 = 100
              5 = 101
              6 = 110
              7 = 111
              ...
              n - 1 = 0b(n-1)


              As you can see, the binary representation is every subset possible where 1 means it is in the set and 0 means it is not.



              Now we just need to use these indexes to find out what should be in each set.
              (While under the hood the numbers are stored as binary, if you try printing them you'll see an int.)



              So we'll do a nested for loop: for j in range(len(s)):



              Here we do need to do a bitwise operation: i & (1 << j) > 0 where i is the current index of the loop described earlier. j is the index of which element in the second loop we're at.



              1 << j just converts the index to the binary representation. For example, the first element (at index 0): 1 << 0 = 001, or the second 1 << 1 = 010, etc.



              The & operator just makes sure the indexes match up. 000 & 101 = 0 but 100 & 101 = 100. So anytime it is greater than 0, it means we've come across an element that belongs in our set.



              Let's take the set {a, b, c} and loop through our range. At 0, 0 & anything = 0, so we have the empty set.



              Let's skip to i = 6: 6 & (1 << 0) > 0 returns false because in binary: 110 & 001 = 0. But the second iteration (j = 1) 6 & (1 << 1) > 0 returns true (110 & 010 = 1). And it will for the 3rd element too. Thus giving you the subset {b, c}.



              The runtime of this algorithm is $O(2^n)$ if that isn't clear! Hope this helps!






              share|improve this answer

























                up vote
                4
                down vote










                up vote
                4
                down vote









                @janos Answer is great, but it was easier for me to think about it with one less bitwise operations.



                def subsets(s):
                """
                :type s: list
                """
                sets =
                for i in range(2**len(s)):
                subset =
                for j in range(len(s)):
                if i & (1 << j) > 0:
                subset.append(s[j])
                sets.append(subset)
                return sets


                Explanation:



                So we know there are $2^n$ subsets in a set where $n$ is the size of the set. So we loop through all those numbers: for i in range(2**len(s)):.



                This gives us a range $0 - 2^n$ which corresponds to these binary numbers (example of a set of size 3):



                0 = 000
                1 = 001
                2 = 010
                3 = 011
                4 = 100
                5 = 101
                6 = 110
                7 = 111
                ...
                n - 1 = 0b(n-1)


                As you can see, the binary representation is every subset possible where 1 means it is in the set and 0 means it is not.



                Now we just need to use these indexes to find out what should be in each set.
                (While under the hood the numbers are stored as binary, if you try printing them you'll see an int.)



                So we'll do a nested for loop: for j in range(len(s)):



                Here we do need to do a bitwise operation: i & (1 << j) > 0 where i is the current index of the loop described earlier. j is the index of which element in the second loop we're at.



                1 << j just converts the index to the binary representation. For example, the first element (at index 0): 1 << 0 = 001, or the second 1 << 1 = 010, etc.



                The & operator just makes sure the indexes match up. 000 & 101 = 0 but 100 & 101 = 100. So anytime it is greater than 0, it means we've come across an element that belongs in our set.



                Let's take the set {a, b, c} and loop through our range. At 0, 0 & anything = 0, so we have the empty set.



                Let's skip to i = 6: 6 & (1 << 0) > 0 returns false because in binary: 110 & 001 = 0. But the second iteration (j = 1) 6 & (1 << 1) > 0 returns true (110 & 010 = 1). And it will for the 3rd element too. Thus giving you the subset {b, c}.



                The runtime of this algorithm is $O(2^n)$ if that isn't clear! Hope this helps!






                share|improve this answer














                @janos Answer is great, but it was easier for me to think about it with one less bitwise operations.



                def subsets(s):
                """
                :type s: list
                """
                sets =
                for i in range(2**len(s)):
                subset =
                for j in range(len(s)):
                if i & (1 << j) > 0:
                subset.append(s[j])
                sets.append(subset)
                return sets


                Explanation:



                So we know there are $2^n$ subsets in a set where $n$ is the size of the set. So we loop through all those numbers: for i in range(2**len(s)):.



                This gives us a range $0 - 2^n$ which corresponds to these binary numbers (example of a set of size 3):



                0 = 000
                1 = 001
                2 = 010
                3 = 011
                4 = 100
                5 = 101
                6 = 110
                7 = 111
                ...
                n - 1 = 0b(n-1)


                As you can see, the binary representation is every subset possible where 1 means it is in the set and 0 means it is not.



                Now we just need to use these indexes to find out what should be in each set.
                (While under the hood the numbers are stored as binary, if you try printing them you'll see an int.)



                So we'll do a nested for loop: for j in range(len(s)):



                Here we do need to do a bitwise operation: i & (1 << j) > 0 where i is the current index of the loop described earlier. j is the index of which element in the second loop we're at.



                1 << j just converts the index to the binary representation. For example, the first element (at index 0): 1 << 0 = 001, or the second 1 << 1 = 010, etc.



                The & operator just makes sure the indexes match up. 000 & 101 = 0 but 100 & 101 = 100. So anytime it is greater than 0, it means we've come across an element that belongs in our set.



                Let's take the set {a, b, c} and loop through our range. At 0, 0 & anything = 0, so we have the empty set.



                Let's skip to i = 6: 6 & (1 << 0) > 0 returns false because in binary: 110 & 001 = 0. But the second iteration (j = 1) 6 & (1 << 1) > 0 returns true (110 & 010 = 1). And it will for the 3rd element too. Thus giving you the subset {b, c}.



                The runtime of this algorithm is $O(2^n)$ if that isn't clear! Hope this helps!







                share|improve this answer














                share|improve this answer



                share|improve this answer








                edited Nov 23 at 5:54









                Sᴀᴍ Onᴇᴌᴀ

                7,84561749




                7,84561749










                answered Nov 22 at 19:27









                Shahaed

                413




                413






























                    draft saved

                    draft discarded




















































                    Thanks for contributing an answer to Code Review Stack Exchange!


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


                    Use MathJax to format equations. MathJax reference.


                    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%2fcodereview.stackexchange.com%2fquestions%2f147633%2fget-subsets-of-a-set-given-as-a-list%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

                    Сан-Квентин

                    Алькесар

                    Josef Freinademetz