Re:Using Monads in C++ to Solve Constraints: 1. The List Monad
by TheLoneWolfling on Wednesday May 13, 2015 @04:06PM
(#9541605)
> I believe that b!/(b-n)! is asymptotically the same class as b^n
Nope. It looks like it at first glance, but it isn't.
Look at what happens when n == b/C:
b^(b/C) / (b!/(b - b/C)!) ==
b^(b/C) / (b!/(b*(C-1)/C)!) ==
e^(log(b^(b/C)) + log((b/C)!) - log((b*(C-1)/C)!)) ~=
e^(b/C log(b) + [b*(C-1)/C] log (b*(C-1)/C) - [b*(C-1)/C] - b log b + b) ==
e^((b+b (-1+C) log((-1+C)/C))/C) ==
e^(b/C* (1+(C-1)log((C-1)/C)))
(I used Stirling's Approximation, namely the form ln(x!) ~= x ln x - x for large x)However, note that (1+(C-1)log((C-1)/C)) / C is greater than zero for all C > 1, as 1+(C-1)log((C-1)/C) > 0 for all C > 1. As such, this diverges for all C > 1.
Re:Using Monads in C++ to Solve Constraints: 1. The List Monad
by dllthomas on Wednesday May 13, 2015 @04:27PM
(#9541726)
b!/(b-n)! only = b!/(b/C)! when C = 2, but interesting regardless. I'll revisit when I have the chance.
In any case, I make the assertion that the algorithm proposed in the article is in fact O(b!/(b-n)!), with the intended definition of StateL.
Re:Using Monads in C++ to Solve Constraints: 1. The List Monad
by TheLoneWolfling on Wednesday May 13, 2015 @04:52PM
(#9541888)
Whoops, started with C = 2 and generalized, incorrectly it would seem. I'll edit it.
Edit: edited.
Re:Using Monads in C++ to Solve Constraints: 1. The List Monad
by dllthomas on Wednesday May 13, 2015 @05:35PM
(#9542130)
Thanks :) C = 2 was enough, of course. So O(n!) is between O(k^n) and O(n^n)?
Re:Using Monads in C++ to Solve Constraints: 1. The List Monad
by TheLoneWolfling on Wednesday May 13, 2015 @08:12PM
(#9542800)
Yep. Though we often weaken a big Theta of n! to a big O of n^n, as it's easier to deal with.
I had initially skimmed the article, and assumed he was already handling uniqueness. With the correct definition of StateL, the solution presented is equivalent to what you describe here, but apparently that definition is deferred to a future article.
The idea would be that, for StateL, for_each would pick one value and pass that value to the lambda, interpreting the result in a context where the sel only sees the remaining values in the list.