testcomb.py

combi.py

# when you asked the question, this is what popped in my head;
# a solution to abstracting the requested problem into indexes

def combi(n, k):
    r = []
    for i in range(n - k + 1):
        for j in range(i + 1, n - k + 2):
            s = [i]
            for m in range(k - 1):
                s.append(j + m)
            r.append(s)
    return r


# there would need to be something that converted these sets of
# indexes into objects from the sets desired

def fn(s, k):
    idx = combi(len(s), k)
    result = []
    for p in idx:
        result_item = []
        for i in p:
            result_item.append(s[i])
        result.append(result_item)
    return result


# so the reduction looks like

print combi(7, 5)
print fn([4,7,2,5,9,3,1], 5)

# naturally, this isn't a whiteboard-sized solution.
# there is more than one solution to your problem,
# but I'm not sure that if someone thinks differently than you do
# that they will be able to solve this problem reasonably.

# I do like your solution; it looks a lot like haskell code
# and has a functional beauty. I don't think my solution is near ideal.
# However, it's what popped into my head in an on-demand situation.

# this isn't beautiful, I'll think of something clever to send still.
# I hope the slackulator daemon didn't scare you, but it's real code.

# also, thank you for prodding me to check out gists. This is useful!

results.txt

Unfortunately, that solution doesn't work. The test harness follows.

----------------------------------------------------------------------
Ran 45 tests in 0.024s

FAILED (failures=21)

check_list(S=[1], k=1) ... ok
check_list(S=[1, 2], k=1) ... ok
check_list(S=[1, 2], k=2) ... ok
check_list(S=[1, 2, 3], k=1) ... ok
check_list(S=[1, 2, 3], k=2) ... ok
check_list(S=[1, 2, 3], k=3) ... ok
check_list(S=[1, 2, 3, 4], k=1) ... ok
check_list(S=[1, 2, 3, 4], k=2) ... ok
check_list(S=[1, 2, 3, 4], k=3) ... FAIL
check_list(S=[1, 2, 3, 4], k=4) ... ok
check_list(S=[1, 2, 3, 4, 5], k=1) ... ok
check_list(S=[1, 2, 3, 4, 5], k=2) ... ok
check_list(S=[1, 2, 3, 4, 5], k=3) ... FAIL
check_list(S=[1, 2, 3, 4, 5], k=4) ... FAIL
check_list(S=[1, 2, 3, 4, 5], k=5) ... ok
check_list(S=[1, 2, 3, 4, 5, 6], k=1) ... ok
check_list(S=[1, 2, 3, 4, 5, 6], k=2) ... ok
check_list(S=[1, 2, 3, 4, 5, 6], k=3) ... FAIL
check_list(S=[1, 2, 3, 4, 5, 6], k=4) ... FAIL
check_list(S=[1, 2, 3, 4, 5, 6], k=5) ... FAIL
check_list(S=[1, 2, 3, 4, 5, 6], k=6) ... ok
check_list(S=[1, 2, 3, 4, 5, 6, 7], k=1) ... ok
check_list(S=[1, 2, 3, 4, 5, 6, 7], k=2) ... ok
check_list(S=[1, 2, 3, 4, 5, 6, 7], k=3) ... FAIL
check_list(S=[1, 2, 3, 4, 5, 6, 7], k=4) ... FAIL
check_list(S=[1, 2, 3, 4, 5, 6, 7], k=5) ... FAIL
check_list(S=[1, 2, 3, 4, 5, 6, 7], k=6) ... FAIL
check_list(S=[1, 2, 3, 4, 5, 6, 7], k=7) ... ok
check_list(S=[1, 2, 3, 4, 5, 6, 7, 8], k=1) ... ok
check_list(S=[1, 2, 3, 4, 5, 6, 7, 8], k=2) ... ok
check_list(S=[1, 2, 3, 4, 5, 6, 7, 8], k=3) ... FAIL
check_list(S=[1, 2, 3, 4, 5, 6, 7, 8], k=4) ... FAIL
check_list(S=[1, 2, 3, 4, 5, 6, 7, 8], k=5) ... FAIL
check_list(S=[1, 2, 3, 4, 5, 6, 7, 8], k=6) ... FAIL
check_list(S=[1, 2, 3, 4, 5, 6, 7, 8], k=7) ... FAIL
check_list(S=[1, 2, 3, 4, 5, 6, 7, 8], k=8) ... ok
check_list(S=[1, 2, 3, 4, 5, 6, 7, 8, 9], k=1) ... ok
check_list(S=[1, 2, 3, 4, 5, 6, 7, 8, 9], k=2) ... ok
check_list(S=[1, 2, 3, 4, 5, 6, 7, 8, 9], k=3) ... FAIL
check_list(S=[1, 2, 3, 4, 5, 6, 7, 8, 9], k=4) ... FAIL
check_list(S=[1, 2, 3, 4, 5, 6, 7, 8, 9], k=5) ... FAIL
check_list(S=[1, 2, 3, 4, 5, 6, 7, 8, 9], k=6) ... FAIL
check_list(S=[1, 2, 3, 4, 5, 6, 7, 8, 9], k=7) ... FAIL
check_list(S=[1, 2, 3, 4, 5, 6, 7, 8, 9], k=8) ... FAIL
check_list(S=[1, 2, 3, 4, 5, 6, 7, 8, 9], k=9) ... ok

...And here are a few of the shorter failing cases:

======================================================================
FAIL: check_list(S=[1, 2, 3, 4, 5, 6, 7, 8, 9], k=9)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/usr/local/Cellar/python/2.7.2/Frameworks/Python.framework/Versions/2.7/lib/python2.7/site-packages/nose/case.py", line 197, in runTest
    self.test(*self.arg)
  File "/Volumes/Mez/msc/tmp/testcomb.py", line 64, in check_list
    assert set(map(frozenset, expected)) == set(map(frozenset, got)), "k=%s, S=%s\nExpected: %s\nGot:      %s" % (k, S, expected, got)
AssertionError: k=3, S=[1, 2, 3, 4]
Expected: [[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]
Got:      [[1, 2, 3], [1, 3, 4], [2, 3, 4]]

======================================================================
FAIL: check_list(S=[1, 2, 3, 4, 5, 6, 7, 8, 9], k=9)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/usr/local/Cellar/python/2.7.2/Frameworks/Python.framework/Versions/2.7/lib/python2.7/site-packages/nose/case.py", line 197, in runTest
    self.test(*self.arg)
  File "/Volumes/Mez/msc/tmp/testcomb.py", line 64, in check_list
    assert set(map(frozenset, expected)) == set(map(frozenset, got)), "k=%s, S=%s\nExpected: %s\nGot:      %s" % (k, S, expected, got)
AssertionError: k=3, S=[1, 2, 3, 4, 5]
Expected: [[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5]]
Got:      [[1, 2, 3], [1, 3, 4], [1, 4, 5], [2, 3, 4], [2, 4, 5], [3, 4, 5]]

testcomb.py

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


# when you asked the question, this is what popped in my head;
# a solution to abstracting the requested problem into indexes

def combi(n, k):
    r = []
    for i in range(n - k + 1):
        for j in range(i + 1, n - k + 2):
            s = [i]
            for m in range(k - 1):
                s.append(j + m)
            r.append(s)
    return r


# there would need to be something that converted these sets of
# indexes into objects from the sets desired

def fn(s, k):
    idx = combi(len(s), k)
    result = []
    for p in idx:
        result_item = []
        for i in p:
            result_item.append(s[i])
        result.append(result_item)
    return result




### My reference implementation from https://gist.github.com/2407735

def kcomb(S, k):
    "All S choose k: All combinations of size k out of the set/sequence S."
    if k <= 0:
        return None
    elif k == 1:
        return [ [v] for v in S ]
    else:
        return [ [v]+suffix for i, v in enumerate(S) for suffix in kcomb(S[i+1:], k-1) ]



### Tests

def test_all():
    "Run a test for each list range(1, 1..10) with k=1..len(S)+1"
    for size in range(1,10):
        S = range(1, size+1)
        for k in range(1, len(S)+1):
            # so nose prints me a nice list of the results
            test_all.__doc__ = check_list.__doc__ = "check_list(S=%s, k=%s)" % (S, k)
            yield check_list, S, k

def check_list(S, k):
    expected = kcomb(S, k)
    got = fn(S, k)
    # convert to sets so order of results doesn't matter
    # use frozenset so subsets are hashable
    assert set(map(frozenset, expected)) == set(map(frozenset, got)), "k=%s, S=%s\nExpected: %s\nGot:      %s" % (k, S, expected, got)


if __name__ == '__main__':
    # or better yet, run `nosetests testcomb.py` (or whatever you named this file)
    for (test, S, k) in test_all():
        try:
            test(S, k)
        except AssertionError as ex:
            print 'Failure:', ex, '\n'