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.
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
denominator = (math.factorial(i)) * (math.factorial(tags_len-i))
value = (numerator/denominator)
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:
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/>
= 15 unordered combinations<br/>
And here's me manually calculating it just to be sure ...
abc; abd; acd<br/>
ab; ac; ad<br/>
1 + 4 + 6 + 4 = 15 unordered combinations<br/>