4 ms·

There is actually a better version of BogoSort that is deterministic. The C++ implementation is very elegant: while(!std::next_permutation(v.begin(),v.end

There is actually a better version of BogoSort that is deterministic. The C++ implementation is very elegant: while(!std::next_permutation(v.begin(),v.end())); The complexity is O(N!)

skulk 5y ago
it's even better, isn't it? next_permutation returns false once it rolls over and returns the sorted version so you can drop the negation.
olliej 5y ago
Strictly speaking that is the “correct” implementation of bogosort because it is deterministic (per my algorithms lecturer: for it to be an algorithm you must take the same steps each time for a given input. Obviously you could get around this by having the sort function take a seed and implement an RNG)
- kadoban 5y ago
  There are various definitions of "algorithm", but that one seems needlessly restrictive. Randomized algorithms are a thing, and there doesn't seem to be much reason to exclude them, to me.
  - olliej 5y ago
    I think the specific issue with the "randomly sort and see if its sorted" is that it is not guaranteed to ever complete.
    - psYchotic 5y ago
      Can't the same be said about the algorithm to generate the Collatz sequence for any given number? By that definition, I shouldn't be calling that an algorithm.
      - olliej 5y ago
        Is collatz the 2n+1&n/3 one? Any way the algorithm to get the next number in a collatz sequence is deterministic and has best and worst case complexity of O(1). You’re then just choosing to run that algorithm against its own output a (potentially) infinite amount of times. That said I take you point. I realize in another reply that what I had totally failed to recognize was my lecturer not clearly explaining that the definition he used was that an algorithm must be executable on a Turing machine.
        kadoban 5y ago
        Yeah, Collatz operation is: if it's even divide by 2, otherwise multiply by 3 and add 1. The gp post is asking: what if you make a procedure that runs that on a given input number, repeatedly, until you end up with the output 1, and give the sequence of numbers you visited on the way. Is that an algorithm? Every number we've tried so far does go to 1, but it's unproven if they all do. It's possible that there exist cycles not containing 1, or maybe some inputs go to infinity. We haven't been able to prove either way. > [...] the definition he used was that an algorithm must be executable on a Turing machine Yeah, that's a pretty good reason to choose a certain definition of an algorithm (that otherwise might be awkward) when you have a model you're fitting it into.
- mkbosmans 5y ago
  It is an overly strict interpretation of that rule to assume it prohibits any randomized algorithm. Aren't these the same steps for any given input? 1) Roll dice to get random number N 2) Get the Nth permutation of the input sequence (for some ordering of permutations) 3) Permute input sequence 4) If sorted: done, else goto step 1
  - olliej 5y ago
    You have to specify the output of rolling the die. If you use an RNG you would provide the seed state for the RNG as an input to the algorithm. Think of it as “can I run this algorithm on a Turing machine”

There is actually a better version of BogoSort that is deterministic. The C++ implementation is very elegant: while(!std::next_permutation(v.begin(),v.end())); The complexity is O(N!)

skulk 5y ago

it's even better, isn't it? next_permutation returns false once it rolls over and returns the sorted version so you can drop the negation.

olliej 5y ago

Strictly speaking that is the “correct” implementation of bogosort because it is deterministic (per my algorithms lecturer: for it to be an algorithm you must take the same steps each time for a given input. Obviously you could get around this by having the sort function take a seed and implement an RNG)

kadoban 5y ago
There are various definitions of "algorithm", but that one seems needlessly restrictive. Randomized algorithms are a thing, and there doesn't seem to be much reason to exclude them, to me.
- olliej 5y ago
  I think the specific issue with the "randomly sort and see if its sorted" is that it is not guaranteed to ever complete.
  - psYchotic 5y ago
    Can't the same be said about the algorithm to generate the Collatz sequence for any given number? By that definition, I shouldn't be calling that an algorithm.
    - olliej 5y ago
      Is collatz the 2n+1&n/3 one? Any way the algorithm to get the next number in a collatz sequence is deterministic and has best and worst case complexity of O(1). You’re then just choosing to run that algorithm against its own output a (potentially) infinite amount of times. That said I take you point. I realize in another reply that what I had totally failed to recognize was my lecturer not clearly explaining that the definition he used was that an algorithm must be executable on a Turing machine.
      - kadoban 5y ago
        Yeah, Collatz operation is: if it's even divide by 2, otherwise multiply by 3 and add 1. The gp post is asking: what if you make a procedure that runs that on a given input number, repeatedly, until you end up with the output 1, and give the sequence of numbers you visited on the way. Is that an algorithm? Every number we've tried so far does go to 1, but it's unproven if they all do. It's possible that there exist cycles not containing 1, or maybe some inputs go to infinity. We haven't been able to prove either way. > [...] the definition he used was that an algorithm must be executable on a Turing machine Yeah, that's a pretty good reason to choose a certain definition of an algorithm (that otherwise might be awkward) when you have a model you're fitting it into.
mkbosmans 5y ago
It is an overly strict interpretation of that rule to assume it prohibits any randomized algorithm. Aren't these the same steps for any given input? 1) Roll dice to get random number N 2) Get the Nth permutation of the input sequence (for some ordering of permutations) 3) Permute input sequence 4) If sorted: done, else goto step 1
- olliej 5y ago
  You have to specify the output of rolling the die. If you use an RNG you would provide the seed state for the RNG as an input to the algorithm. Think of it as “can I run this algorithm on a Turing machine”