blog.humaneguitarist.org
on facets and unordered combinations
[Fri, 21 Oct 2011 02:13:11 +0000]
I have to come up with some sort of basic taxonomy for our files at work, so today I was doing some research to help my mind get where it needs to be.
First, I need to mention this [http://www.taxonomystrategies.com/presentations/Getting_Started.ppt] really nice PowerPoint on developing a taxonomy for work called "Getting Started with Business Taxonomy Design". It got me thinking about tags and how if I tagged something with four tags, "a", "b", "c", and the equally dull "d", then I could calculate the number of ways I could filter down to a set of results that would contain that document.
I don't know if my thinking is correct, but I'm thinking there should be 15 ways to get to that document with four tags because I should be able to filter, inclusively, not only by each individual tag but also by unordered combinations of those tags, i.e. tagged with both "b" AND "a", etc.
So, I read this [http://www.mathsisfun.com/combinatorics/combinations-permutations.html] neat page on calculating unordered combinations for a set and wrote a Python script, below, to calculate the total. I had to also see this [http://www.adonald.btinternet.co.uk/Factor/Zero.html] page about what the value of zero factorial is as I'd assumed it would be undefinable.
The script tells how many unordered combinations for four tags there would be for a group of four tags (i.e. all of them), then three, then two, then each of the four.
import math
tags = ['a','b','c','d'] #say I have assigned 4 tags to a file
tags_len = len(tags)
numerator = math.factorial(tags_len)
combinations_value = 0
i = tags_len
def calculateCombinations(i):
denominator = (math.factorial(i)) * (math.factorial(tags_len-i))
value = (numerator/denominator)
return value
while i > 0:
print calculateCombinations(i), 'unordered combination(s) per', i
combinations_value = combinations_value + calculateCombinations(i)
i = i - 1
print '-----\n=', combinations_value, 'unordered combinations'
Here's the output:
>>> <br/>
1 unordered combination(s) per 4<br/>
4 unordered combination(s) per 3<br/>
6 unordered combination(s) per 2<br/>
4 unordered combination(s) per 1<br/>
-----<br/>
= 15 unordered combinations<br/>
>>> <br/>
And here's me manually calculating it just to be sure ...
QUADS (1):<br/>
abcd<br/>
<br/>
TRIPLES (4):<br/>
abc; abd; acd<br/>
bcd;<br/>
<br/>
DOUBLES (6):<br/>
ab; ac; ad<br/>
bc; bd<br/>
cd<br/>
<br/>
SINGLES (4):<br/>
a<br/>
b<br/>
c<br/>
d<br/>
-----<br/>
1 + 4 + 6 + 4 = 15 unordered combinations<br/>