Monday, March 16
Big numbers
A request for assistance, really. Need to know what 250,000_P_10 is i.e. how many permutations of 10 or less objects from a collection of 250,000 objects.
I'll make do with knowing the number of digits in the answer (in normal, common-or-garden base-10).
O if only I could remember what I used to know about O notation this would be more straighforward.
I will buy a pint for the first correct answer.
Subscribe to:
Post Comments (Atom)
19 comments:
So you want P(250000, 10) which wikipedia helpfully tells me is:
250000! / (250000 - 10)! = 250000! / 249990!
Almost all of those factors cancel out so you're left with:
250000 * 249999 * ... * 249992 * 249991
mathomatic helpfully tells me:
1-> 250000 * 249999 * 249998 * 249997 * 249996 * 249995 * 249994 * 249993 * 249992 * 249991
answer = 9.5350266830387e+53
I'm not sure whether it says more about you or me that I didn't even ask this last time: why did you need this number...?
I have to say, 'why do you want to know this?' was *my* first thought. My second was that I don't know the answer. Does this mean I am more normal, but also useless?
I'm sure what he says is right.
Interesting. Being a geologist I approximated to n_log_n so got an answer of 10^49ish.
Worryingly seem to be 10^4 out, so glad I asked. James, I owe you a pint.
In answer to question, it's working out how many 10-word phrases there are in English.
Is the factorial thing for if you can only use each object once? Whereas you can use the same word more than once in a phrase ('The teacher gave the boy the book' or whatever). But not too much (no, 'The the the the the'). Although some words can be re-used more than others...
I guess the maths would get complicated.
But James' answer is not correct: I think what he gives is the number of ten-word phrases consisting of ten different words. A lot of ten word phrases will repeat some words. What you want to know is the number of ten-word phrases allowing repetition: which I think would be
(n+k+1)!/k!(n-1)!
Or (250,000 + 10 - 1)!/10!(250,000-1)!
which is 250,009!/10!249,999!
cancelling out gives
=(250,009*250,008...250,000)/10!
= roughly 2*10^47.
Weirdly, that seems to be a lot smaller than James' answer, rather than (as it should be) larger. Hmm. I think I'd better go away and check that.
The reason Alec's answer is smaller than mine is that his formula is the number of combinations with repetition, not the number of permutations with repetition.
Combinations (I think we were taught at school nCr, as opposed to nPr) count the number of ways to make sets (so order is irrelevant). Unless you're restricting yourself to sentences entirely in alphabetical order this isn't so useful. :)
The formula for permutations with repetition is trivial: it's just 250,000!. You select one from 250,000, then one from 250,000, then ..., 10 times.
But this isn't any good either, since as Sophia pointed out you just get junk sentences. I don't know whether there's some sort of linguistic measure for the percentage of random groups of words that will make a sensible sentence, but it's probably vanishingly small. The answer to the question Liam actually wanted to ask is probably way smaller than even Alec's answer.
Good point, James, well made. I feel a bit dense now. Of course 250,000! is what I was after.
Also, even if you could find some way of filtering for sentences that were grammatically well-formed, you'd still be left with the majority being grammatical but nonsensical: "colourless green ideas sleep furiously" being the classic example.
err, thinko. Not 250,000!, that would give you all sentences 250,000 words long. I meant 250,000 * 10.
whoops.
So, we've concluded that:-
1. It's the permutations we are after. Man bites dog is a different utterance to Dog bites man.
2. The number of possible combinations is very big.
3. The number of poss permutations is even bigger. Let's assume it is 9.5350266830387e+53 for the sake of argument.
5. Most permutations will be nonsensical (either grammatically or otherwise).
What we don't know is:-
A) Whether, for Liam's purposes, nonsense phrases count towards the total.
B) What fraction of the 9.5350266830387e+53 phrases will be 'sensical'. (It will have to be orders of magnitude smaller - but how many?) This is obviously a linguistic, rather than a mathematical question and to do the research to even approach an answer would probably require a greater incentive than one pint of beer...
As a sidebar, this conversation suggests a new (and reassuring) theory about the BBC's Have Your Say boards. It's not that the country is awash with illiterate paranoid bigots, as I'd feared. It's just a random phrase generator iterating all possible permutations and publishing them on the internet. And for some reason they've started with sentences containing the phrases 'NuLabour', 'muslim extremists' and 'going to the dogs'. Phew!
I know how to check for sensicalness. If that's a word.
Just write a program that will generate (say) ten thousand random ten-word phrases, and then google them all. That'll give you a minimum figure for the proportion of possible English phrases that are sensical, and then you just multiply them up.
The BBC's Have Your Say boards may in fact be populated by software evolved by genetic algorithm to resemble paranoid bigots. The more realistic the comment sounds, the more replies it gets - the software that sounds best gets retained and bred from.
See "Jipi and the Paranoid Chip".
http://www.vanemden.com/books/neals/jipi.html
Nonsense phrases are fine.
Don't think nPr with repetition can be smaller than nPr without repetition. So James' 250000 * 10 can't be right...
Anyhoo, approx 1*10^52 is good, although would be nice to allow repetition. Hmmm. As soon as you allow repetition this is no longer a permutation. References to permutations with repetitions are unhelpful as they assume knowledge of the number of repetition. It may in fact need to be a sum of the various repetition combinations available within a string of 10 objects, i.e. 10,0 ; 1,9; 1,1,8; 2,8; 1,1,1,7; 1,2,7; 3,7 and so on. Bleaurgh.
Now time to make it into something vaguely understandable.
So how's this:
Assume 10^20 stars in our universe with, between them a thousand billion (10^12) habitable planets in the universe. Assume each planet has a civilisation of 10 billion (10^9) people. Each person has a computer with a terabyte - 1000Gb (10^12 bytes ish) - of storage on it, and we assume we can store one word per byte. That gets you to 10^33 10-word strings. So you would need a hundred billion trillion of these universes to get enough computer storage for every 10 word string in the English language.
P.S. this is for a book on Google I'm co-authoring.
P.P.S. Working out a grammar for cutting down to sensical phrases is hard, but strikes me a quick approximate would be to allow any number of nouns in a row, zero or one verbs in a row; if a verb is present may be preceded or followed by any number of adverbs. This is obviously a very simple grammar, but should approximate near enough for a geologist.
D'oh!
Permutations with repetition, as any fule kno, is n^r.
The rather fab keisan.casio.com tells me that the answer is 9.5367431640625E+53, a result within a few hundredths of a percent of n!/(n-r)!, 9.53502668303866592596E+53
Now I realise that you need to store a 10-word string, not just a word, so a single byte won't cut it. Bother.
I'll wait for you to blow more holes in my analogy before I correct it :)
You're writing a book? Good effort!
You're writing a book *on Google*? Kerching! Are you going to be the new Clay Skirky?
I'm a bit confused here by Liam's recent messages. Surely 250,000^10 is 9.5367431640625E+53, which is
a) Almost exactly what James said to start with.
b) Allowing repetitions.
One thought occurred to me though, does your 250,000 (presumably the number of words in English) include proper nouns? Because if not, considering all the people and place names which can be used in sentences, the list of possible phrases is bigger.
Also - I don't think Alec's methodology (elegant though it is) will be a very effective way of identifying sensical (I've decided it is a word:-)) sentences. I know from frequently googling misremembered poetry, that many perfectly reasonable phrases will not be found by a google search.
The first phrase I tested was not found, but is perfectly sensical...
http://www.google.co.uk/search?hl=en&client=firefox-a&rls=org.mozilla%3Aen-GB%3Aofficial&q=%22Our+science+engagement+event+finished+on+Friday%2C+then+we+rested%22&btnG=Search&meta=
Good point, Soph - it'd give you a minimum percentage of sensicality, but there'd certainly be more sensical phrases that just haven't been written before. Brute force is to generate the 10,000 random phrases and then get humans to go through them and work out which are sensical. Which is a boring job.
Well, if you only need to do 10,000 phrases, assuming you can do one a second (not unreasonable I think, read the phrase, click yes or no, NEXT!) then 3 hrs = 10,800 seconds. So it's only an afternoon's boredom. And the life of a scientist probably contains a few of them...
Post a Comment