3 ms·

It certainly doesn't mean we have to punt the easy cases, but it seems inappropriate to lambaste the current solution without establishing that we are in fact l

It certainly doesn't mean we have to punt the easy cases, but it seems inappropriate to lambaste the current solution without establishing that we are in fact looking at an easy case. That no one seems to have produced (or pointed at) an asymptotically better solution in any language, I think that's some small evidence that there isn't such a solution and substantially more evidence that it's not easy to find.

TheLoneWolfling 12y ago
There's an easy better method: assign variables starting from the lower order digits, greedily check correctness, and skip over all permutations with that prefix if it fails. Although I don't know how one would go about proving or disproving if this is asymptotically better or just a (substantial) constant-factor speedup.
- dllthomas 12y ago
  Oh! I had misread your original comment to be, "There are b! / (b - n)! ways to choose n of b unique numbers, [so] this solution is O(b^n)." You were contrasting! I believe that b!/(b-n)! is asymptotically the same class as b^n (whether we're varying b or n), hence my confusion. 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.
  - TheLoneWolfling 12y ago
    > 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.
    - dllthomas 12y ago
      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.
      - TheLoneWolfling 12y ago
        Whoops, started with C = 2 and generalized, incorrectly it would seem. I'll edit it. Edit: edited.
        dllthomas 12y ago
        Thanks :) C = 2 was enough, of course. So O(n!) is between O(k^n) and O(n^n)?
        TheLoneWolfling 12y ago
        Yep. Though we often weaken a big Theta of n! to a big O of n^n, as it's easier to deal with.
        dllthomas 12y ago
        That makes sense, and probably contributed to my confusion.

TheLoneWolfling 12y ago

There's an easy better method: assign variables starting from the lower order digits, greedily check correctness, and skip over all permutations with that prefix if it fails. Although I don't know how one would go about proving or disproving if this is asymptotically better or just a (substantial) constant-factor speedup.

dllthomas 12y ago
Oh! I had misread your original comment to be, "There are b! / (b - n)! ways to choose n of b unique numbers, [so] this solution is O(b^n)." You were contrasting! I believe that b!/(b-n)! is asymptotically the same class as b^n (whether we're varying b or n), hence my confusion. 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.
- TheLoneWolfling 12y ago
  > 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.
  - dllthomas 12y ago
    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.
    - TheLoneWolfling 12y ago
      Whoops, started with C = 2 and generalized, incorrectly it would seem. I'll edit it. Edit: edited.
      - dllthomas 12y ago
        Thanks :) C = 2 was enough, of course. So O(n!) is between O(k^n) and O(n^n)?
        TheLoneWolfling 12y ago
        Yep. Though we often weaken a big Theta of n! to a big O of n^n, as it's easier to deal with.
        dllthomas 12y ago
        That makes sense, and probably contributed to my confusion.