tag:blogger.com,1999:blog-786333285568106173.post1854109930913796148..comments2024-01-25T01:05:59.968-05:00Comments on WebDiarios de Motocicleta: Puzzle: Short-hop permutationsMihaihttp://www.blogger.com/profile/11599372864611039927noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-786333285568106173.post-79639651806755799802009-04-13T17:34:00.000-04:002009-04-13T17:34:00.000-04:00@Andrei: Yes. I used k!=O(k^k). For some strange r...@Andrei: Yes. I used k!=O(k^k). For some strange reason I thought at the time that the formula will be easier to read :Prgrighttps://www.blogger.com/profile/02991214367108471744noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-39459608957970307562009-04-13T15:26:00.000-04:002009-04-13T15:26:00.000-04:00Shouldn't there be O(k!*2^k) such configurations? ...Shouldn't there be O(k!*2^k) such configurations? You can get all of them by starting from a permutation of 1..K and adding a zero between some consecutive values.Anonymoushttps://www.blogger.com/profile/09851688703780264888noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-86311476391923891202009-04-10T11:32:00.000-04:002009-04-10T11:32:00.000-04:00Actually, they seem to just do bruteforce :o Not e...Actually, they seem to just do bruteforce :o Not even the simple (but slow) solution where you keep track of the count C(n,S) of permutations of 1..n that have the n-k+1..n numbers in a certain configuration S. A configuration being something like 012036504: here k=6; 1 stands for n-k+1; 6 stands for n; 0 means "a string of stuff <=n-k that I don't really remember". There are O(n(2k)^k) such numbers and you do about O(k) operations for each. Hence, too slow :(rgrighttps://www.blogger.com/profile/02991214367108471744noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-82893433968666962302009-04-10T09:58:00.000-04:002009-04-10T09:58:00.000-04:00At least these guys don't seem to know a close...At least these guys don't seem to know a closed form solution: http://scholar.google.com/scholar?hl=en&lr=&cluster=2621410177201314710rgrighttps://www.blogger.com/profile/02991214367108471744noreply@blogger.com