"""
Module for generating all the subsets of a given set of elements. The following
code draws inspiration from:
  http://visualstudiomagazine.com/articles/2012/08/01/biginteger-data-type.aspx
"""


def binom(n, k):
    """
    Computes the binomial coefficient "n choose k"
    """
    if n < 0 or k < 0:
        raise Exception("Error: Negative argument in binomial coefficient!")
    if n < k:
        return 0
    if n == k or k == 0:
        return 1
    if k < n - k:
        delta = n - k
        iMax = k
    else:
        delta = k
        iMax = n - k
    ans = delta + 1
    for i in range(2, iMax + 1):
        ans = (ans * (delta + i)) // i
    return ans


def largestV(a, b, x):
    """
    Helper function for get_subset
    """
    v = a - 1
    while (binom(v, b) > x):
        v -= 1
    return v


def get_subset(h, k, elements):
    """
    Returns the (h+1)-th element, w.r.t. the lexicographic ordering, among all
    the subsets of elements having cardinality k.
    """
    n = len(elements)
    maxM = binom(n, k) - 1
    ans = [0] * k
    a = n
    b = k
    # x is the "dual" of h.
    x = maxM - h
    for i in range(0, k):
        ans[i] = largestV(a, b, x)
        x -= binom(ans[i], b)
        a = ans[i]
        b = b - 1
    ans = [elements[(n - 1) - ans[i]] for i in range(0, k)]
    return ans


'''
# Dummy testing.
from time import time
elements = [
    'S_1', 'S_2', 'S_3', 'S_4', 'S_5', 'S_6',
    'S_7', 'S_8', 'S_9', 'S_10', 'S_11', 'S_12'
]
n = len(elements)
start = time()
i = 1
for k in range(0, n):
    for h in range(0, binom(n, k)):
        s = get_subset(h, k, elements)
        print(s)
        i += 1
elapsed = (time() - start)
print(i, pow(2,len(elements)))
assert(i == pow(2,len(elements)))
print("Computed", i, "subsets of", elements, "in", elapsed, "seconds")
'''

d42d07a7816e6972fd7b92aecc7fb0abc6bbd373
<mask token>

<mask token>


def get_subset(h, k, elements):
    """
    Returns the (h+1)-th element, w.r.t. the lexicographic ordering, among all
    the subsets of elements having cardinality k.
    """
    n = len(elements)
    maxM = binom(n, k) - 1
    ans = [0] * k
    a = n
    b = k
    x = maxM - h
    for i in range(0, k):
        ans[i] = largestV(a, b, x)
        x -= binom(ans[i], b)
        a = ans[i]
        b = b - 1
    ans = [elements[n - 1 - ans[i]] for i in range(0, k)]
    return ans


<mask token>

<mask token>


def largestV(a, b, x):
    """
    Helper function for get_subset
    """
    v = a - 1
    while binom(v, b) > x:
        v -= 1
    return v


def get_subset(h, k, elements):
    """
    Returns the (h+1)-th element, w.r.t. the lexicographic ordering, among all
    the subsets of elements having cardinality k.
    """
    n = len(elements)
    maxM = binom(n, k) - 1
    ans = [0] * k
    a = n
    b = k
    x = maxM - h
    for i in range(0, k):
        ans[i] = largestV(a, b, x)
        x -= binom(ans[i], b)
        a = ans[i]
        b = b - 1
    ans = [elements[n - 1 - ans[i]] for i in range(0, k)]
    return ans


<mask token>

<mask token>


def binom(n, k):
    """
    Computes the binomial coefficient "n choose k"
    """
    if n < 0 or k < 0:
        raise Exception('Error: Negative argument in binomial coefficient!')
    if n < k:
        return 0
    if n == k or k == 0:
        return 1
    if k < n - k:
        delta = n - k
        iMax = k
    else:
        delta = k
        iMax = n - k
    ans = delta + 1
    for i in range(2, iMax + 1):
        ans = ans * (delta + i) // i
    return ans


def largestV(a, b, x):
    """
    Helper function for get_subset
    """
    v = a - 1
    while binom(v, b) > x:
        v -= 1
    return v


def get_subset(h, k, elements):
    """
    Returns the (h+1)-th element, w.r.t. the lexicographic ordering, among all
    the subsets of elements having cardinality k.
    """
    n = len(elements)
    maxM = binom(n, k) - 1
    ans = [0] * k
    a = n
    b = k
    x = maxM - h
    for i in range(0, k):
        ans[i] = largestV(a, b, x)
        x -= binom(ans[i], b)
        a = ans[i]
        b = b - 1
    ans = [elements[n - 1 - ans[i]] for i in range(0, k)]
    return ans


<mask token>

"""
Module for generating all the subsets of a given set of elements. The following
code draws inspiration from:
  http://visualstudiomagazine.com/articles/2012/08/01/biginteger-data-type.aspx
"""


def binom(n, k):
    """
    Computes the binomial coefficient "n choose k"
    """
    if n < 0 or k < 0:
        raise Exception("Error: Negative argument in binomial coefficient!")
    if n < k:
        return 0
    if n == k or k == 0:
        return 1
    if k < n - k:
        delta = n - k
        iMax = k
    else:
        delta = k
        iMax = n - k
    ans = delta + 1
    for i in range(2, iMax + 1):
        ans = (ans * (delta + i)) // i
    return ans


def largestV(a, b, x):
    """
    Helper function for get_subset
    """
    v = a - 1
    while (binom(v, b) > x):
        v -= 1
    return v


def get_subset(h, k, elements):
    """
    Returns the (h+1)-th element, w.r.t. the lexicographic ordering, among all
    the subsets of elements having cardinality k.
    """
    n = len(elements)
    maxM = binom(n, k) - 1
    ans = [0] * k
    a = n
    b = k
    # x is the "dual" of h.
    x = maxM - h
    for i in range(0, k):
        ans[i] = largestV(a, b, x)
        x -= binom(ans[i], b)
        a = ans[i]
        b = b - 1
    ans = [elements[(n - 1) - ans[i]] for i in range(0, k)]
    return ans


'''
# Dummy testing.
from time import time
elements = [
    'S_1', 'S_2', 'S_3', 'S_4', 'S_5', 'S_6',
    'S_7', 'S_8', 'S_9', 'S_10', 'S_11', 'S_12'
]
n = len(elements)
start = time()
i = 1
for k in range(0, n):
    for h in range(0, binom(n, k)):
        s = get_subset(h, k, elements)
        print(s)
        i += 1
elapsed = (time() - start)
print(i, pow(2,len(elements)))
assert(i == pow(2,len(elements)))
print("Computed", i, "subsets of", elements, "in", elapsed, "seconds")
'''
