List all subsets of a given set

output.txt

[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3], [4], [1, 4], [2, 4], [1, 2, 4], [3, 4], [1, 3, 4], [2, 3, 4], [1, 2, 3, 4]]

subsets.rb

#!/usr/bin/env ruby

S = (1..4).to_a
p (0...(2 ** S.length)).map { |i| S.select { present = i % 2; i >>= 1; present != 0 } }

Without the binary trick, similar to next_permutation, for example from subset = [3,2,1] the next 4 is to be inserted when 4 > subset[i], and the elements after the insertion point removed, so next subset is [4], next is [4,1], [4,2] and so on.

#!/usr/bin/env python
# -*- coding: utf-8 -*-
import sys

def getss(seq):
    # elements in the current subset
    left = []
    # elements not in the current subset, ordered
    right = seq
    yield left
    while len(right):
        next_el = right.pop(0)
#        print 'next_el:',next_el
        ins_pos = None
        for i in range(len(left)-1,-1,-1):
#            print 'i:',i,'left[i]',left[i]
            if next_el < left[i]:
                left.insert(i+1, next_el)
                next_el = None
                ins_pos = i+1
                break

        if not ins_pos:
            left.insert(0, next_el)
            ins_pos = 0

        tmp = left[ins_pos+1:]
        tmp.reverse()
        right = tmp + right
#        print 'right:',right
        left = left[:ins_pos+1]
        yield left
#        print 'left end: ', left

def main():
    seq = [1,2,3,4,5,6,7,8,9,10]
    for s in getss(seq):
        print s


    return 1

if __name__ == '__main__':
    sys.exit(main())