Nearly five years to the day, I wrote about unordered combinations [http://blog.humaneguitarist.org/2011/10/20/on-facets-and-unordered-combinations/] within the context of faceting. About 2 years ago, I was using resistance bands as my main strength training equipment. While I still use them, I mainly use dumbbells now. Anyway, one of the issues I had with the bands was how to know all the combinations of different bands (I have about 5 different ones), sorted by level of resistance, low to high. In other words, I needed to calculate all the unordered combinations. The idea was that once I could do a given number of reps and sets for a given type of lift, I'd increase the resistance. I had my workout in a spreadsheet, so having a sheet of all the unordered combinations gave me an easy way, via some spreadsheet formulas, to show me the next set of bands I needed to use for my next workout. At the time, using some code I found using itertools [https://docs.python.org/2/library/itertools.html], I got what I needed. But it really bothered me that I couldn't figure out how to create a function on my own that did what I needed. So yesterday, after a couple of hours (or years!), I seem to have got something that's embarrassingly simple. Basically, once I realized that my problem involved recursion, I was able to get rolling. Because rather than take a set, for instance ("a", b", "c", "d"), and return all the unordered combinations, I realized that I just needed a function that returned all the unordered combinations of length "n - 1" for a set of length "n". I could then just pass the newly calculated unordered combination itself to the function. Sample code below. Feel free to share better implementations ... or tell me this doesn't work at all. A couple things to note:
1. While I think this will work fine (assuming it works at all) when the original set has repeated items - ("a", "b", "c", "c", "d"), it will incorrectly report what the correct number of unordered combinations are. I need to investigate the correct way of calculating this - by, you know, reading the page [http://www.mathsisfun.com/combinatorics/combinations-permutations.html] I cited in my original post.
2. This function returns an empty list as one of the unordered combinations. This is useless for calculating resistance band combinations - well, unless you're thinking about using body weight alone. But I included it due to something I remember reading in Discrete Mathematics And Its Applications [http://www.worldcat.org/oclc/712983477] (7th Edition, page 120), namely that "every nonempty set S is guaranteed to have at least two subsets, the empty set and the set S itself."
"""
Takes a list of unique "ITEMS" and reports:
1) number of items in ITEMS
2) number of unordered combinations within ITEMS
3) and prints what those combinations are (sorted by length of list).
"""
# establish the original list.
ITEMS = ["a", "b", "c", "d"]
# create an output list to hold all the unordered combinations;
# start by including the original list.
UNORDERED_COMBINATIONS = [ITEMS]
# calculate other combinations ...
def get_unordered_combinations(items):
""" Gets unordered combinations for lists whose length is (len(items) - 1). """
items_range = range(0, len(items))
for skip_pos in items_range: # get new combinations by excluding each item.
combination = [items[item_pos] for item_pos in items_range
if item_pos != skip_pos]
if combination not in UNORDERED_COMBINATIONS:
UNORDERED_COMBINATIONS.append(combination)
get_unordered_combinations(combination)
get_unordered_combinations(ITEMS)
# print reports.
print "the original list: ", ITEMS
print " - the number of ITEMS in the original list: ", len(ITEMS)
print " - the correct number of unordered lists within the original: ", (2**len(ITEMS))
print " - the number of unordered lists actually returned: ", len(UNORDERED_COMBINATIONS)
print " - the unordered lists (preceded by the member list's length) ..."
print
RESULTS = [(len(x), x) for x in UNORDERED_COMBINATIONS] # i.e. (length of combination, combination).
for RESULT in sorted(RESULTS):
print RESULT
"""
OUTPUTS:
the original list: ['a', 'b', 'c', 'd']
- the number of ITEMS in the original list: 4
- the correct number of unordered lists within the original: 16
- the number of unordered lists actually returned: 16
- the unordered lists (preceded by the member list's length) ...
(0, [])
(1, ['a'])
(1, ['b'])
(1, ['c'])
(1, ['d'])
(2, ['a', 'b'])
(2, ['a', 'c'])
(2, ['a', 'd'])
(2, ['b', 'c'])
(2, ['b', 'd'])
(2, ['c', 'd'])
(3, ['a', 'b', 'c'])
(3, ['a', 'b', 'd'])
(3, ['a', 'c', 'd'])
(3, ['b', 'c', 'd'])
(4, ['a', 'b', 'c', 'd'])
"""
Update, October 29, 2016: I wanted to see if I could clean this up a bit and cake it all within one function using nested functions and closures, so I've pasted that attempt below. This actually double-nests the main function. I just wanted to avoid writing a class [https://youtu.be/o9pEzgHorH0].
def get_unordered_combinations(original_items):
unordered_combinations = [original_items]
def calc_unordered_combinations(items):
def calc_combinations():
items_range = range(0, len(items))
for skip_pos in items_range:
combination = [items[item_pos] for item_pos in items_range
if item_pos != skip_pos]
if combination not in unordered_combinations:
unordered_combinations.append(combination)
recurse = calc_unordered_combinations(combination)
recurse()
return calc_combinations
run = calc_unordered_combinations(original_items)
run()
unordered_combinations = [(len(x), x) for x in unordered_combinations]
return sorted(unordered_combinations)
# create original combination; get/print all unordered combinations.
ITEMS = ["a", "b", "c", "d"]
RESULTS = get_unordered_combinations(ITEMS)
for R in RESULTS:
print R
Update, October 29, 2016: I knew something useless was there. Here's the same thing, without the closure. It was completely unnecessary. Sometimes I read things and want to incorporate the idea without always asking myself if I really need to or not.
def get_unordered_combinations(original_items):
unordered_combinations = [original_items]
def calc_combinations(items):
items_range = range(0, len(items))
for skip_pos in items_range:
combination = [items[item_pos] for item_pos in items_range
if item_pos != skip_pos]
if combination not in unordered_combinations:
unordered_combinations.append(combination)
calc_combinations(combination)
calc_combinations(original_items)
unordered_combinations = [(len(x), x) for x in unordered_combinations]
return sorted(unordered_combinations)
# create original combination; get/print all unordered combinations.
ITEMS = ["a", "b", "c", "d"]
RESULTS = get_unordered_combinations(ITEMS)
for R in RESULTS:
print R