"If I'm still interested in the morning ... "

Post #169,166 by drewk 8/13/04 10:42:02 AM Reply	"If I'm still interested in the morning ... " Post #169093 By ben_tilly 2004-08-13 03:02:48 With timezone conversion that was 2 minutes after midnight your time. Yeah, I guess that counts as "tomorrow morning." === Implicitly condoning stupidity since 2001.
Post #169,169 by mmoffitt 8/13/04 10:44:45 AM Reply	I knew he couldn't resist ;-) bcnu, Mikem If you can read this, you are not the President.
Post #169,181 by ben_tilly 8/13/04 12:17:17 PM Reply	Well, it is not so technically morning now... So time for a redo. And the much faster version goes like this: \n#! /usr/bin/ruby -w\n\nclass RepeatedSequence\n attr_reader :value, :repeat;\n\n def to_s\n "<#{@value}x#{@repeat}>"\n end\n\n def initialize(value, repeat)\n @value = value;\n @repeat = repeat;\n end\nend\n\n# With one argument, the product 12..n\n# With two arguments with m <= n, the product m(m+1)..n\n# With two arguments with n < m, 1.\n@known_factorials = { "0\|1"=>1 };\ndef factorial(n, m=1)\n unless @known_factorials.has_key?(n.to_s + "\|" + m.to_s)\n n = n.to_i;\n m = m.to_i;\n product = 1;\n (m..n).each {\|i\| product = i}\n @known_factorials[n.to_s + "\|" + m.to_s] = product\n end\n @known_factorials[n.to_s + "\|" + m.to_s]\nend\n\n# Sums an array.\ndef sum(numbers)\n ans = 0;\n numbers.each{\|i\| ans += i}\n ans\nend\n\n# The number of ways to divide a set of n things into a combination of\n# groups of sizes. The sizes arguments are expected to be constant sequences.\n# The familiar "n choose m" function is a special case.\ndef choose(n, sizes)\n n = n.to_i\n ans = factorial(n, n + 1 - sum(sizes.collect {\|i\| i.valuei.repeat}));\n sizes.each { \|i\| ans /= (factorial(i.value)i.repeat) };\n ans\nend\n\n# This calls the function with each descending sequence whose terms sum to\n# total and whose maximimum element is max (that optionally starts with the\n# initial subsequence).\ndef call_with_each_descending_sequence(total, max, function, initial=[])\n if 1 == max\n function[initial + [RepeatedSequence.new(1, total)]];\n return;\n end\n\n call_with_each_descending_sequence(\n total, max - 1, function, initial\n );\n\n (1..(total/max)).each {\|count\|\n subsequence = RepeatedSequence.new(max, count);\n call_with_each_descending_sequence(\n total - maxcount, max - 1, function, initial + [ subsequence ]\n )\n }\nend\n\n# Calculate the number of possible birthday assignments to some number of\n# people with a given maximimum number of people getting the same day.\ndef possible_birthday_assignments(people, max_one_day)\n ans = 0;\n call_with_each_descending_sequence(\n people.to_i,\n\n max_one_day.to_i,\n proc {\|duplicate_sequence\| \n people_to_duplicate_sequence = choose(people, duplicate_sequence);\n\n day_groupings = duplicate_sequence.collect {\|i\|\n RepeatedSequence.new(i.repeat, 1)\n }\n days_to_day_groupings = choose(365, day_groupings);\n\n ans += days_to_day_groupings * people_to_duplicate_sequence;\n }\n );\n ans;\nend\n\ncount = possible_birthday_assignments(ARGV);\nprob = ( count 1_000_000 / 365*(ARGV[0].to_i) ).to_f / 1_000_000;\nputs "Odds #{prob} that #{ARGV[0]} people have at most #{ARGV[1]} birthdays together";\n With this version, I've been able to show that to get even odds of 5 people with the same birthday you need 313 or 314 people. At that point the possibility of leap day births is significant. Skipping leap day, the odds of not having 5 with 312 people are 0.498929, and with 313 is 0.498929. Taking into account a rough estimate of the odds that 1 person will be born on leap day out of 313 (i.e. 3131/(3654+1)), my odds are 0.499973404517454. That's close enough that I'd have to really do the leap day calculation right to figure out whether the answer is 313 or 314. And I don't have the energy at the moment. Cheers, Ben To deny the indirect purchaser, who in this case is the ultimate purchaser, the right to seek relief from unlawful conduct, would essentially remove the word consumer from the Consumer Protection Act* - [link\|http://www.techworld.com/opsys/news/index.cfm?NewsID=1246&Page=1&pagePos=20\|Nebraska Supreme Court]
Post #169,246 by ben_tilly 8/13/04 5:52:09 PM Reply	And a better answer and algorithm improvements The answer for 5 really is 313. The probability of not having any group of 5 with 313 people is 0.499972. I'm including a program with a different algorithm that can answer that. It scales worse than the previous one for up to 3 people on the same birthday, but better for 4 or more after that. It takes leap years into account. It does not take into account the 3 missing leap days every 400 years, but there aren't many people around who are 104 (and even fewer who are 204) so I think that is a reasonable omission. \n#! /usr/bin/ruby -w\n\n# With one argument, the product 12..n\n# With two arguments with m <= n, the product m(m+1)..n\n# With two arguments with n < m, 1.\ndef factorial(n, m=1)\n n = n.to_i;\n m = m.to_i;\n product = 1;\n (m..n).each {\|i\| product = i}\n product\nend\n\n# Sums an array.\ndef sum(numbers)\n ans = 0;\n numbers.each{\|i\| ans += i}\n ans\nend\n\n# The number of ways to find m things in n.\n@choose_cache = Hash.new\ndef choose(n, m)\n key = "#{n} #{m}";\n unless @choose_cache.has_key?(key)\n if (m > n/2)\n m = n - m;\n end\n @choose_cache[key] = factorial(n, n + 1 - m) / factorial(m);\n end\n return @choose_cache[key]\nend\n\n# Calculate the number of possible birthday assignments to some number of\n# people using some number of days with a given maximimum number of people\n# getting the same day.\n@birthday_assignments = Hash.new();\ndef possible_birthday_assignments(people, days, max_one_day)\n if (people > daysmax_one_day)\n return 0;\n elsif days < 2\n return 1;\n else \n key = "#{people}\|#{days}\|#{max_one_day}";\n ans = 0;\n unless @birthday_assignments.has_key?(key)\n if (days/22 == days)\n # Divide the days in half\n (0..people).each {\|people_in_first\|\n ans += possible_birthday_assignments(\n people_in_first,\n days/2,\n max_one_day\n ) possible_birthday_assignments(\n people - people_in_first,\n days/2,\n max_one_day\n ) * choose(people, people_in_first);\n }\n else\n # Divide people in 1 day, people in the rest\n limit = people < max_one_day ? people : max_one_day\n (0..limit).each{ \|people_in_first\|\n ans += possible_birthday_assignments(\n people - people_in_first,\n days - 1,\n max_one_day\n ) * choose(people, people_in_first)\n }\n end\n @birthday_assignments[key] = ans;\n end\n return @birthday_assignments[key];\n end\nend\n\ndef fraction_to_float(a, b)\n precision = 100_000_000;\n return ( (a * precision + a/2)/b ).to_f / precision;\nend\n\n# Calculate birthday probability but ignore leap day.\ndef basic_birthday_probability(people, max_one_day)\n count = possible_birthday_assignments(people.to_i, 365, max_one_day.to_i)\n return fraction_to_float(count, 365*(people.to_i));\nend\n\n# Calculate birthday probability and include leap day.\ndef birthday_probability(people, max_one_day)\n people = people.to_i;\n max_one_day = max_one_day.to_i;\n limit = people < max_one_day ? people : max_one_day;\n ans = 0;\n (0..limit).each {\|i\|\n ans += basic_birthday_probability(\n people - i, max_one_day\n ) fraction_to_float(\n choose(people, i) * (3654)(people-i),\n (3654 + 1)*people\n );\n }\n return ans;\nend\n\nprob = birthday_probability(ARGV);\nputs "Odds #{prob} that #{ARGV[0]} people have at most #{ARGV[1]} birthdays together";\n Cheers, Ben To deny the indirect purchaser, who in this case is the ultimate purchaser, the right to seek relief from unlawful conduct, would essentially remove the word consumer from the Consumer Protection Act - [link\|http://www.techworld.com/opsys/news/index.cfm?NewsID=1246&Page=1&pagePos=20\|Nebraska Supreme Court]
Post #169,378 by drewk 8/15/04 10:49:34 AM Reply	It's nice to see there's at least one person in the world... ... with a more keenly-developed distaste for not-quite-rightness than me. === Implicitly condoning stupidity since 2001.

Welcome to IWETHEY!