Page 1 of 4

Deliberately bad algorithms

Posted: Tue Jun 02, 2015 2:15 pm UTC
by Wildcard
We've all experienced that warm fuzzy feeling that comes from taking a O(lg n) algorithm and replacing it with an elegant, 5-line implementation of a O(n!) algorithm....

Or maybe not.

Truthfully, I think we all strive so much for efficiency and good practices that we could have a lot of fun with this idea and perhaps get some benefit in the process.

Get the bad algorithms out of your system! Seize the bull by the horns!

Or if seizing the bull by the horns seems like too straightforward of an algorithm, then try throwing peanuts in the bull's face using a teaspoon until he stomps you into the dust and has a heart attack from overexertion.
Maybe that's still too efficient, though? :)

Rube Goldberg approaches are welcome, but what I really want to shoot for here is very simple algorithms which are astonishingly, elegantly inefficient.

I'll get the ball rolling:

Code: Select all

Stupid sort:
Start at the beginning of the list and move forward.
Compare each item to the previous item.
    If an item is smaller than the previous one, move it to the very beginning of the list and restart.
When you get all the way through the list, it will be sorted smallest to biggest.
Runs in O(2^n).

:)

Re: Deliberately bad algorithms

Posted: Tue Jun 02, 2015 9:30 pm UTC
by Tub
You cannot beat the simplicity and inefficiency of bogosort.

Code: Select all

bogosort:
  while the list is not sorted
    shuffle the list
  return list

Guaranteed to terminate successfully with P = 1, but it's impossible to derive an O notation since the running time has no upper bound.


A more practical example, I once replaced a sequential O(n*k) algorithm (for a small fixed k) with an OpenCL kernel that ended up being O(n*n). Initial testing proved the GPU to be faster. But as n grew larger than the amount of shaders on our GPU, performance became slightly sluggish. Oops.

Now it's a sequential O(n) step on the CPU with some O(n*k) postprocessing on the GPU and everything is fine.

Re: Deliberately bad algorithms

Posted: Tue Jun 02, 2015 11:03 pm UTC
by hotaru

Code: Select all

factorial = product . enumFromTo 1
isPrime n = factorial (n - 1) `mod` n == n - 1

Re: Deliberately bad algorithms

Posted: Wed Jun 03, 2015 12:18 am UTC
by EvanED
Tub wrote:Guaranteed to terminate successfully with P = 1, but it's impossible to derive an O notation since the running time has no upper bound.
You can still talk about the complexity of the average case, which would be n! iterations of the outer loop.

hotaru wrote:

Code: Select all

factorial = product . enumFromTo 1
isPrime n = factorial (n - 1) `mod` n == n - 1
Very nice

Re: Deliberately bad algorithms

Posted: Wed Jun 03, 2015 3:07 am UTC
by Wildcard
hotaru wrote:

Code: Select all

factorial = product . enumFromTo 1
isPrime n = factorial (n - 1) `mod` n == n - 1

Wow. Perfect example. It's not merely inefficient, it's actually elegantly bad. :lol: It took me several seconds to think it through and check that it's correct.

Finding a median in O(n^2):

Code: Select all

for each number in list
   if count of smaller numbers in list == (length of list - 1) / 2
      then return number
But I feel I could improve on its badness, given time. :)

Re: Deliberately bad algorithms

Posted: Wed Jun 03, 2015 3:48 am UTC
by LucasBrown
Or you could just bogosort the list and then extract the middle element.

Elegantly bad: deterministic primality test via trial division implemented in regular expressions. Uses O(n2) time and O(n) memory.

Code: Select all

import re
def isprime(n): return not re.match(r'^1?$|^(11+?)\1+$', '1'*n)

Re: Deliberately bad algorithms

Posted: Wed Jun 03, 2015 8:34 am UTC
by PM 2Ring
hotaru wrote:

Code: Select all

factorial = product . enumFromTo 1
isPrime n = factorial (n - 1) `mod` n == n - 1


<voice="Tom Hanks">Wilson!</voice>

Re: Deliberately bad algorithms

Posted: Wed Jun 03, 2015 5:46 pm UTC
by benneh
There's the obvious:

Code: Select all

fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

Or, another (slightly less) stupid sort:

Code: Select all

sort (a:as) = if isSorted as' then as' else sort (as ++ [a]) where
    as' = a : sort as
sort [] = []
EDIT: Actually, I think this is O(n!). In which case, I name this algorithm 'stupider sort'.

Re: Deliberately bad algorithms

Posted: Wed Jun 03, 2015 8:22 pm UTC
by Wildcard
Hmmm, I'm not getting the syntax. What language is that? Can you write it in Java or C?

Edit: Wait, maybe I get it. I'm not sure how to do linked lists in Java, though—I'm still learning. So would the following pseudocode capture your algorithm?

Code: Select all

sort(list)
    if the list is empty return the empty list
    else
        set a = first item of the list
        set as = the rest of the list
        set as' = a followed by sort(as)
        if as' is sorted then return as'
        else return sort(as followed by a)
If so, I think you're right, that's O(n!). Nicely done :P

Re: Deliberately bad algorithms

Posted: Wed Jun 03, 2015 8:57 pm UTC
by Flumble
That reminds me of SlowSort (not an alias of bogosort)
http://www.c2.com/cgi/wiki?SlowSort wrote:

Code: Select all

   def slowsort(A, i, j):
      # This procedure sorts the subarray A[i]...A[j]
      if i >= j:
         return
      m = (i+j)/2
      slowsort(A, i, m)
      slowsort(A, m+1, j)
      if A[m] > A[j]:
         A[m],A[j] = A[j],A[m]
      slowsort(A, i, j-1)


It has an alledged complexity of O(nlog n)=O(e(log n)^2), which is the weirdest time complexity I've seen so far. Today I learned: that's called quasi-polynomial time.


[edit] Forgot the code tag

Re: Deliberately bad algorithms

Posted: Wed Jun 03, 2015 9:50 pm UTC
by Thesh
Not the worst in terms of performance(O(n^2)), but certainly the least clever. Basically selection sort, but with a hell of a lot more swaps.

Code: Select all

void dumbsort(int *a, size_t len)
{
   int temp;
   size_t i, j;
   for(i=0; i<len-1; i++)
   {
      for (j=i+1; j<len; j++)
      {
         if (a[j] < a[i])
         {
            temp = a[j];
            a[j] = a[i];
            a[i] = temp;
         }
      }
   }
}

Re: Deliberately bad algorithms

Posted: Wed Jun 03, 2015 9:52 pm UTC
by somehow
Wildcard wrote:Hmmm, I'm not getting the syntax. What language is that? Can you write it in Java or C?

Edit: Wait, maybe I get it. I'm not sure how to do linked lists in Java, though—I'm still learning. So would the following pseudocode capture your algorithm?

Code: Select all

sort(list)
    if the list is empty return the empty list
    else
        set a = first item of the list
        set as = the rest of the list
        set as' = a followed by sort(as)
        if as' is sorted then return as'
        else return sort(as followed by a)
If so, I think you're right, that's O(n!). Nicely done :P


Yes, your psuedocode correctly translates benneh's code, which was written in Haskell (as was hotaru's factorial-based primality tester).

Re: Deliberately bad algorithms

Posted: Wed Jun 03, 2015 10:00 pm UTC
by Derek
Wildcard wrote:Hmmm, I'm not getting the syntax. What language is that? Can you write it in Java or C?

Edit: Wait, maybe I get it. I'm not sure how to do linked lists in Java, though—I'm still learning. So would the following pseudocode capture your algorithm?

Code: Select all

sort(list)
    if the list is empty return the empty list
    else
        set a = first item of the list
        set as = the rest of the list
        set as' = a followed by sort(as)
        if as' is sorted then return as'
        else return sort(as followed by a)
If so, I think you're right, that's O(n!). Nicely done :P

I believe it's basically the same as your stupid sort, but it works back to front instead of front to back, and uses an inefficient O(n) swap. Therefore, based on your analysis in the OP, I believe it is O(n*2^n)

Re: Deliberately bad algorithms

Posted: Wed Jun 03, 2015 10:09 pm UTC
by EvanED
Flumble wrote:That reminds me of SlowSort (not an alias of bogosort)

For purposes of readability...

Code: Select all

def slowsort(A, i, j):
      # This procedure sorts the subarray A[i]...A[j]
      if i >= j:
         return
      m = (i+j)/2
      slowsort(A, i, m)
      slowsort(A, m+1, j)
      if A[m] > A[j]:
         A[m],A[j] = A[j],A[m]
      slowsort(A, i, j-1)

Re: Deliberately bad algorithms

Posted: Wed Jun 03, 2015 10:33 pm UTC
by Thesh
I forgot I had already written a quickperm implementation in python:

Code: Select all

class quickperm: #Based on the QuickPerm algorithm from http://www.quickperm.org/
    def __init__(self, size):
        self.permutation = [x for x in range(size)]
        self._p = [x for x in range(size+1)]
        self._i = 1
   
    def next_permutation(self):
        if self._i >= len(self.permutation):
            return False
        self._p[self._i] -= 1
        if self._i%2 == 1:
            j = self._p[self._i]
        else:
            j = 0
        self.permutation[self._i],self.permutation[j] = self.permutation[j],self.permutation[self._i]
        self._i = 1
        while self._i < len(self._p) and self._p[self._i] == 0:
            self._p[self._i] = self._i
            self._i += 1
        return True

def is_sorted(a):
    for i in range(1, len(a)):
        if a[i] < a[i-1]:
            return False;
    return True

def permsort(a):
    perm = quickperm(len(a))
    b = [a[x] for x in perm.permutation]
    while not is_sorted(b):
        perm.next_permutation()
        b = [a[x] for x in perm.permutation]
    return b

O(n!) in the worst case.

Re: Deliberately bad algorithms

Posted: Wed Jun 03, 2015 11:05 pm UTC
by Derek
Stooge sort is fun. Sort the first two thirds of the array, sort the second two thirds, sort the first two thirds again. Runs in O(n^2.7095).

Re: Deliberately bad algorithms

Posted: Wed Jun 03, 2015 11:21 pm UTC
by Nitrodon
Derek wrote:
Wildcard wrote:Hmmm, I'm not getting the syntax. What language is that? Can you write it in Java or C?

Edit: Wait, maybe I get it. I'm not sure how to do linked lists in Java, though—I'm still learning. So would the following pseudocode capture your algorithm?

Code: Select all

sort(list)
    if the list is empty return the empty list
    else
        set a = first item of the list
        set as = the rest of the list
        set as' = a followed by sort(as)
        if as' is sorted then return as'
        else return sort(as followed by a)
If so, I think you're right, that's O(n!). Nicely done :P

I believe it's basically the same as your stupid sort, but it works back to front instead of front to back, and uses an inefficient O(n) swap. Therefore, based on your analysis in the OP, I believe it is O(n*2^n)

I thought the same thing at first, but the "as" in the last line is not sorted.

Re: Deliberately bad algorithms

Posted: Wed Jun 03, 2015 11:32 pm UTC
by Wildcard
EDIT: Ninja'd. Nice to see this topic so active. :) I'll post what I wrote anyways. As an additional note, I have a good intuitive grasp on this stuff but I'm actually only now working through Cormen from the very beginning. I haven't done any formal analysis of algorithm running times yet, so the following may look a little will probably look very peculiar to you.

Derek wrote:I believe it is O(n*2^n)
Try sorting a reverse sorted list with stupider-sort.
Spoiler:

Code: Select all

4321
    321
        21
            1
                []
                return []
            1 is sorted = true
            return 1
        21 is sorted = false
        12
            2
                []
                return []
            2 is sorted = true
            return 2
        12 is sorted = true
        return 12
    312 is sorted = false
    213
        13
            3
                []
                return []
            3 is sorted = true
            return 3
        13 is sorted = true
        return 13
    213 is sorted = false
    132
        32
            2
                []
                return []
            2 is sorted = true
            return 2
        32 is sorted = false
        23
            3
                []
                return []
            3 is sorted = true
            return 3
        23 is sorted = true
        return 23
    123 is sorted = true
    return 123
4123 is sorted = false
3214
    214
        14
            4
                []
                return []
            4 is sorted = true
            return 4
        14 is sorted = true
        return 14
    214 is sorted = false
    142
        42
            2
                []
                return []
            2 is sorted = true
            return 2
        42 is sorted = false
        24
            4
                []
                return []
            4 is sorted = true
            return 4
        24 is sorted = true
        return 24
    124 is sorted = true
    return 124
3124 is sorted = false
2143
    143
        43
            3
                []
                return []
            3 is sorted = true
            return 3
        43 is sorted = false
        34
            4
                []
                return []
            4 is sorted = true
            return 4
        34 is sorted = true
        return 34
    134 is sorted = true
    return 134
2134 is sorted = false
1432
    432
        32
            2
                []
                return []
            2 is sorted = true
            return 2
        32 is sorted = false
        23
            3
                []
                return []
            3 is sorted = true
            return 3
        23 is sorted = true
        return 23
    423 is sorted = false
    324
        24
            4
                []
                return []
            4 is sorted = true
            return 4
        24 is sorted = true
        return 24
    324 is sorted = false
    243
        43
            3
                []
                return []
            3 is sorted = true
            return 3
        43 is sorted = false
        34
            4
                []
                return []
            4 is sorted = true
            return 4
        34 is sorted = true
        return 34
    234 is sorted = true
    return 234
1234 is sorted = true
return 1234
I've shown each recursive call in its own indentation level, unless the recursive call is in a return statement (i.e. return sort(as followed by a)).
If you're sorting 54321, after you sort 4321 and check if 51234 is sorted, you then throw away all that work by just rotating the list to 43215. Then after you sort 3215 and check if 41235 is sorted, you just rotate the original list again, to 32154, and so on.

Simply put, you have 5 top-level recursive calls to sort a 4 item list before your 5 item list is sorted (worst case). You have 17 calls to sort a 16 item list before your 17 item list is sorted. And so on. Doesn't that make it O(n!)?

I can see that not all the recursive calls will be worst case running time themselves, because due to the rotation based iteration, the worst case input must have the smallest item at the end of the list. And after the first top level recursive call completes, the smallest item will become the 2nd to last item in the list and will never move backwards in the list again.

...Hmmm. Actually, I think that 23451 is the worst case running time. Or is it? Not sure. :?

Re: Deliberately bad algorithms

Posted: Thu Jun 04, 2015 12:01 am UTC
by Thesh
How about this one:

Code: Select all

def is_permutation(a,b):
   for i in a:
      counta = 0
      countb = 0
      for j in a:
         if i == j:
            counta += 1
      for j in b:
         if i == j:
            countb += 1
      if counta != countb:
         return False
   return True

def next_sorted_array(a, bound):
   i = len(a)-1
   a[i] += 1

   while a[i] > bound and i > 0:
      i -= 1
      a[i] += 1

   if a[i] > bound:
      return False

   while i<len(a)-1:
      a[i+1] = a[i]
      i += 1

   return True

def reallydumbsort(a):
   lbound = min(a)
   ubound = max(a)
   s = [lbound for x in range(len(a))]
   while not is_permutation(a,s):
      next_sorted_array(s,ubound)
   return s


Sorting the array [0,100,100,100,100] takes 4,598,125 iterations.

Re: Deliberately bad algorithms

Posted: Thu Jun 04, 2015 2:26 am UTC
by phlip
Why make sure your iterator is only generating sorted arrays? Have it generate everything, and just make sure the sorted permutation comes first...

Code: Select all

import itertools

def sort(tosort):
  for candidate in itertools.product(range(min(tosort), max(tosort) + 1), repeat=len(tosort)):
    if any(list(tosort) == list(i) for i in itertools.permutations(candidate)):
      return list(candidate)
  else:
    raise ValueError("Could not find sorted list")
Spoiler:
Intentionally looping through the permutations of candidate to see if tosort is one, instead of vice-versa, to avoid "well, if we're looping through the permutations if tosort anyway...".

By my eye, this is something like O(2knn!n) to sort a list of n ints where each int is k bits long (ie max(a)-min(a) is O(2k)).


[edit]
Wildcard wrote:...Hmmm. Actually, I think that 23451 is the worst case running time. Or is it? Not sure. :?

5,4,3,2,1 is the slowest, it seems:
Spoiler:

Code: Select all

def issorted(a):
   return all(i<j for i,j in zip(a[:-1], a[1:]))
def stupidersort(a):
   if not a:
      return []
   while True:
      first, rest = a[0:1], a[1:]
      candidate = first + stupidersort(rest)
      if issorted(candidate):
         return candidate
      a = rest + first

import timeit, itertools, pprint
results = []
timer = timeit.Timer("stupidersort(i)", "from __main__ import stupidersort, i")
for i in itertools.permutations([1,2,3,4,5]):
   i = list(i)
   results.append((i, min(timer.repeat(number=100000))))
results.sort(key=lambda x:x[1]) # yes, using the "real" sort here... so sue me
pprint.pprint(results)

Code: Select all

[([1, 2, 3, 4, 5], 0.009999990463256836),
 ([1, 2, 3, 5, 4], 0.019999980926513672),
 ([1, 2, 4, 3, 5], 0.019999980926513672),
 ([1, 2, 5, 3, 4], 0.019999980926513672),
 ([1, 5, 2, 3, 4], 0.019999980926513672),
 ([1, 4, 2, 3, 5], 0.029999971389770508),
 ([4, 1, 2, 3, 5], 0.029999971389770508),
 ([5, 1, 2, 3, 4], 0.029999971389770508),
 ([1, 2, 4, 5, 3], 0.030000925064086914),
 ([1, 4, 2, 5, 3], 0.030000925064086914),
 ([1, 2, 5, 4, 3], 0.039999961853027344),
 ([1, 3, 2, 4, 5], 0.039999961853027344),
 ([1, 4, 5, 2, 3], 0.039999961853027344),
 ([4, 1, 2, 5, 3], 0.039999961853027344),
 ([4, 1, 5, 2, 3], 0.039999961853027344),
 ([5, 1, 2, 4, 3], 0.039999961853027344),
 ([1, 5, 2, 4, 3], 0.04000091552734375),
 ([1, 3, 2, 5, 4], 0.04999995231628418),
 ([1, 5, 4, 2, 3], 0.04999995231628418),
 ([3, 1, 2, 4, 5], 0.04999995231628418),
 ([4, 5, 1, 2, 3], 0.04999995231628418),
 ([5, 1, 4, 2, 3], 0.04999995231628418),
 ([3, 1, 2, 5, 4], 0.05000019073486328),
 ([5, 4, 1, 2, 3], 0.05000019073486328),
 ([1, 3, 4, 2, 5], 0.05000114440917969),
 ([1, 3, 5, 2, 4], 0.059999942779541016),
 ([3, 1, 4, 2, 5], 0.06000018119812012),
 ([3, 1, 5, 2, 4], 0.06000113487243652),
 ([1, 5, 3, 2, 4], 0.06999993324279785),
 ([3, 4, 1, 2, 5], 0.06999993324279785),
 ([3, 5, 1, 2, 4], 0.06999993324279785),
 ([1, 3, 4, 5, 2], 0.07000017166137695),
 ([3, 1, 4, 5, 2], 0.07000088691711426),
 ([5, 1, 3, 2, 4], 0.07000088691711426),
 ([5, 3, 1, 2, 4], 0.07000088691711426),
 ([1, 3, 5, 4, 2], 0.07999992370605469),
 ([4, 3, 1, 2, 5], 0.07999992370605469),
 ([3, 1, 5, 4, 2], 0.08000016212463379),
 ([1, 4, 3, 2, 5], 0.0800008773803711),
 ([4, 1, 3, 2, 5], 0.0800008773803711),
 ([3, 4, 1, 5, 2], 0.0800011157989502),
 ([1, 4, 3, 5, 2], 0.08999991416931152),
 ([1, 5, 3, 4, 2], 0.08999991416931152),
 ([3, 4, 5, 1, 2], 0.09000015258789062),
 ([5, 1, 3, 4, 2], 0.09000015258789062),
 ([2, 1, 3, 4, 5], 0.09000086784362793),
 ([4, 1, 3, 5, 2], 0.09000110626220703),
 ([1, 4, 5, 3, 2], 0.10000085830688477),
 ([2, 1, 3, 5, 4], 0.10000085830688477),
 ([3, 5, 1, 4, 2], 0.10000085830688477),
 ([5, 3, 1, 4, 2], 0.10000085830688477),
 ([4, 3, 1, 5, 2], 0.10000109672546387),
 ([3, 5, 4, 1, 2], 0.1100008487701416),
 ([4, 1, 5, 3, 2], 0.1100008487701416),
 ([5, 3, 4, 1, 2], 0.1100008487701416),
 ([1, 5, 4, 3, 2], 0.1100010871887207),
 ([2, 1, 5, 3, 4], 0.1100010871887207),
 ([4, 3, 5, 1, 2], 0.1100010871887207),
 ([4, 5, 1, 3, 2], 0.1100010871887207),
 ([5, 1, 4, 3, 2], 0.1100010871887207),
 ([2, 3, 1, 4, 5], 0.12000083923339844),
 ([2, 5, 1, 3, 4], 0.12000083923339844),
 ([2, 1, 4, 3, 5], 0.12000107765197754),
 ([2, 4, 1, 3, 5], 0.12000107765197754),
 ([4, 5, 3, 1, 2], 0.12000107765197754),
 ([5, 4, 1, 3, 2], 0.12000107765197754),
 ([5, 2, 1, 3, 4], 0.13000106811523438),
 ([5, 4, 3, 1, 2], 0.13000106811523438),
 ([2, 1, 4, 5, 3], 0.1400008201599121),
 ([2, 3, 1, 5, 4], 0.1400008201599121),
 ([2, 3, 4, 1, 5], 0.1400010585784912),
 ([2, 4, 1, 5, 3], 0.1400010585784912),
 ([4, 2, 1, 3, 5], 0.14000201225280762),
 ([2, 1, 5, 4, 3], 0.15000104904174805),
 ([2, 3, 5, 1, 4], 0.15000200271606445),
 ([2, 3, 4, 5, 1], 0.16000103950500488),
 ([2, 4, 5, 1, 3], 0.16000103950500488),
 ([2, 5, 1, 4, 3], 0.16000103950500488),
 ([2, 5, 3, 1, 4], 0.16000103950500488),
 ([4, 2, 1, 5, 3], 0.1600019931793213),
 ([2, 5, 4, 1, 3], 0.17000198364257812),
 ([5, 2, 1, 4, 3], 0.17000198364257812),
 ([2, 4, 3, 1, 5], 0.18000102043151855),
 ([4, 2, 5, 1, 3], 0.18000102043151855),
 ([3, 2, 1, 4, 5], 0.18000197410583496),
 ([5, 2, 3, 1, 4], 0.18000197410583496),
 ([5, 2, 4, 1, 3], 0.18000197410583496),
 ([2, 3, 5, 4, 1], 0.1900019645690918),
 ([2, 5, 3, 4, 1], 0.20000195503234863),
 ([3, 2, 4, 1, 5], 0.20000195503234863),
 ([4, 2, 3, 1, 5], 0.20000195503234863),
 ([4, 5, 2, 1, 3], 0.20000195503234863),
 ([2, 4, 3, 5, 1], 0.21000194549560547),
 ([3, 2, 1, 5, 4], 0.21000194549560547),
 ([3, 2, 5, 1, 4], 0.2200019359588623),
 ([5, 2, 3, 4, 1], 0.2200019359588623),
 ([5, 4, 2, 1, 3], 0.2200019359588623),
 ([2, 4, 5, 3, 1], 0.23000192642211914),
 ([3, 2, 4, 5, 1], 0.23000192642211914),
 ([4, 2, 3, 5, 1], 0.23000192642211914),
 ([3, 5, 2, 1, 4], 0.24000310897827148),
 ([2, 5, 4, 3, 1], 0.2500019073486328),
 ([3, 4, 2, 1, 5], 0.2500019073486328),
 ([3, 2, 5, 4, 1], 0.2500021457672119),
 ([4, 2, 5, 3, 1], 0.2500030994415283),
 ([5, 2, 4, 3, 1], 0.26000189781188965),
 ([5, 3, 2, 1, 4], 0.26000213623046875),
 ([4, 5, 2, 3, 1], 0.2700018882751465),
 ([3, 4, 2, 5, 1], 0.2700028419494629),
 ([3, 5, 2, 4, 1], 0.29000210762023926),
 ([4, 3, 2, 1, 5], 0.29000282287597656),
 ([5, 4, 2, 3, 1], 0.29000282287597656),
 ([5, 3, 2, 4, 1], 0.3000028133392334),
 ([3, 4, 5, 2, 1], 0.31000280380249023),
 ([4, 3, 2, 5, 1], 0.31000304222106934),
 ([3, 5, 4, 2, 1], 0.330003023147583),
 ([5, 3, 4, 2, 1], 0.34000277519226074),
 ([4, 3, 5, 2, 1], 0.34000396728515625),
 ([4, 5, 3, 2, 1], 0.37000298500061035),
 ([5, 4, 3, 2, 1], 0.3900032043457031)]
Alternatively, counting iterations:

Code: Select all

def issorted(a):
   return all(i<j for i,j in zip(a[:-1], a[1:]))
def stupidersort(a):
   if not a:
      return []
   while True:
      global count
      count += 1
      first, rest = a[0:1], a[1:]
      candidate = first + stupidersort(rest)
      if issorted(candidate):
         return candidate
      a = rest + first

import itertools, pprint
results = []
for i in itertools.permutations([1,2,3,4,5]):
   count = 0
   stupidersort(list(i))
   results.append((i, count))
results.sort(key=lambda x:x[1])
pprint.pprint(results)

Code: Select all

[((1, 2, 3, 4, 5), 5),
 ((1, 2, 3, 5, 4), 7),
 ((1, 2, 5, 3, 4), 8),
 ((1, 5, 2, 3, 4), 9),
 ((1, 2, 4, 3, 5), 10),
 ((5, 1, 2, 3, 4), 10),
 ((1, 4, 2, 3, 5), 11),
 ((4, 1, 2, 3, 5), 12),
 ((1, 2, 4, 5, 3), 13),
 ((1, 4, 2, 5, 3), 14),
 ((1, 2, 5, 4, 3), 15),
 ((4, 1, 2, 5, 3), 15),
 ((1, 4, 5, 2, 3), 16),
 ((1, 5, 2, 4, 3), 16),
 ((1, 3, 2, 4, 5), 17),
 ((4, 1, 5, 2, 3), 17),
 ((5, 1, 2, 4, 3), 17),
 ((1, 5, 4, 2, 3), 18),
 ((3, 1, 2, 4, 5), 18),
 ((4, 5, 1, 2, 3), 19),
 ((5, 1, 4, 2, 3), 19),
 ((1, 3, 2, 5, 4), 21),
 ((5, 4, 1, 2, 3), 21),
 ((3, 1, 2, 5, 4), 22),
 ((1, 3, 4, 2, 5), 23),
 ((1, 3, 5, 2, 4), 23),
 ((3, 1, 4, 2, 5), 24),
 ((3, 1, 5, 2, 4), 24),
 ((1, 5, 3, 2, 4), 26),
 ((3, 4, 1, 2, 5), 26),
 ((3, 5, 1, 2, 4), 26),
 ((5, 1, 3, 2, 4), 27),
 ((1, 3, 4, 5, 2), 28),
 ((3, 1, 4, 5, 2), 29),
 ((5, 3, 1, 2, 4), 29),
 ((1, 4, 3, 2, 5), 30),
 ((3, 4, 1, 5, 2), 31),
 ((4, 1, 3, 2, 5), 31),
 ((1, 3, 5, 4, 2), 32),
 ((2, 1, 3, 4, 5), 33),
 ((3, 1, 5, 4, 2), 33),
 ((4, 3, 1, 2, 5), 33),
 ((1, 4, 3, 5, 2), 35),
 ((1, 5, 3, 4, 2), 35),
 ((3, 4, 5, 1, 2), 35),
 ((3, 5, 1, 4, 2), 35),
 ((4, 1, 3, 5, 2), 36),
 ((5, 1, 3, 4, 2), 36),
 ((4, 3, 1, 5, 2), 38),
 ((5, 3, 1, 4, 2), 38),
 ((2, 1, 3, 5, 4), 39),
 ((3, 5, 4, 1, 2), 39),
 ((1, 4, 5, 3, 2), 40),
 ((4, 1, 5, 3, 2), 41),
 ((4, 3, 5, 1, 2), 42),
 ((5, 3, 4, 1, 2), 42),
 ((2, 1, 5, 3, 4), 43),
 ((4, 5, 1, 3, 2), 43),
 ((1, 5, 4, 3, 2), 44),
 ((2, 1, 4, 3, 5), 45),
 ((2, 5, 1, 3, 4), 45),
 ((5, 1, 4, 3, 2), 45),
 ((2, 3, 1, 4, 5), 46),
 ((2, 4, 1, 3, 5), 47),
 ((4, 5, 3, 1, 2), 47),
 ((5, 4, 1, 3, 2), 47),
 ((5, 2, 1, 3, 4), 50),
 ((5, 4, 3, 1, 2), 51),
 ((2, 1, 4, 5, 3), 53),
 ((2, 3, 1, 5, 4), 54),
 ((2, 3, 4, 1, 5), 54),
 ((2, 4, 1, 5, 3), 55),
 ((4, 2, 1, 3, 5), 56),
 ((2, 3, 5, 1, 4), 58),
 ((2, 1, 5, 4, 3), 59),
 ((2, 4, 5, 1, 3), 59),
 ((2, 5, 1, 4, 3), 61),
 ((2, 3, 4, 5, 1), 63),
 ((2, 5, 3, 1, 4), 64),
 ((4, 2, 1, 5, 3), 64),
 ((2, 5, 4, 1, 3), 65),
 ((5, 2, 1, 4, 3), 66),
 ((2, 4, 3, 1, 5), 68),
 ((4, 2, 5, 1, 3), 68),
 ((5, 2, 3, 1, 4), 69),
 ((3, 2, 1, 4, 5), 70),
 ((5, 2, 4, 1, 3), 70),
 ((2, 3, 5, 4, 1), 71),
 ((4, 5, 2, 1, 3), 76),
 ((2, 4, 3, 5, 1), 77),
 ((2, 5, 3, 4, 1), 77),
 ((4, 2, 3, 1, 5), 77),
 ((3, 2, 4, 1, 5), 78),
 ((3, 2, 1, 5, 4), 80),
 ((5, 2, 3, 4, 1), 82),
 ((5, 4, 2, 1, 3), 82),
 ((3, 2, 5, 1, 4), 84),
 ((4, 2, 3, 5, 1), 86),
 ((2, 4, 5, 3, 1), 87),
 ((3, 2, 4, 5, 1), 87),
 ((3, 5, 2, 1, 4), 92),
 ((3, 4, 2, 1, 5), 94),
 ((2, 5, 4, 3, 1), 95),
 ((4, 2, 5, 3, 1), 96),
 ((3, 2, 5, 4, 1), 97),
 ((5, 2, 4, 3, 1), 100),
 ((5, 3, 2, 1, 4), 100),
 ((3, 4, 2, 5, 1), 103),
 ((4, 5, 2, 3, 1), 104),
 ((3, 5, 2, 4, 1), 105),
 ((4, 3, 2, 1, 5), 110),
 ((5, 4, 2, 3, 1), 112),
 ((5, 3, 2, 4, 1), 113),
 ((3, 4, 5, 2, 1), 116),
 ((4, 3, 2, 5, 1), 119),
 ((3, 5, 4, 2, 1), 126),
 ((4, 3, 5, 2, 1), 132),
 ((5, 3, 4, 2, 1), 134),
 ((4, 5, 3, 2, 1), 144),
 ((5, 4, 3, 2, 1), 154)]

Re: Deliberately bad algorithms

Posted: Thu Jun 04, 2015 3:28 am UTC
by Thesh
I really should learn more of the Python library functions, but yeah, that does make a lot more sense; a lot cleaner than my function to check if it's a permutation.

Re: Deliberately bad algorithms

Posted: Thu Jun 04, 2015 8:42 am UTC
by benneh
For anyone confused by my 'stupider sort' algorithm, it is essentially just this:

Code: Select all

stupiderSort list:
    for perm in permutations(list):
        if perm is sorted:
            return perm

I was originally going for something O(n^n), by doing something similar to phlip. After seeing phlip's solution, I've come up with this, which I'm fairly sure is O(n^n) (phlip, are you sure yours isn't at least as bad as this?):

Code: Select all

stupidestSort list:
    for candidate in list^(length list):
        if candidate is sorted and candidate is a permutation of list:
            return candidate
"list^n" is the collection of all lists of length n consisting of elements of 'list'.

If you want to go really over the top, you could provide a method of determining whether a list is sorted which then recalls your list sorting algorithm:
Spoiler:

Code: Select all

import Prelude hiding (minimum)

import Control.Applicative (liftA2)
import Data.List (permutations)

stupidesterSort :: (Ord a) => [a] -> [a]
stupidesterSort as = find' (\ bs -> isSorted bs && bs `elem` permutations as) (listPower (length as) as)

listPower :: Int -> [a] -> [[a]]
listPower n as = foldr (liftA2 (:)) [[]] (replicate n as)

isSorted :: (Ord a) => [a] -> Bool
isSorted [] = True
isSorted [_] = True
isSorted (a:as) = a <= minimum as && isSorted as

minimum :: (Ord a) => [a] -> a
minimum = head . sort

find' :: (a -> Bool) -> [a] -> a
find' condition = head . filter condition
This is essentially the same as stupidestSort, but with a small modification. In order to check that a list is sorted, it checks that the first element is less than or equal to the minimum of the rest of the list, then checks that the rest of the list is sorted. But to find the minimum of a list, it sorts the list (!) and returns the first element. I have no idea how to work out the running time of that monstrosity. It can sort a 5 element list in less than a second, but I started sorting a 6 element list when I started writing this post, and it hasn't finished yet.

EDIT: For a maximum balance of simplicity and inefficiency:

Code: Select all

sort(list):
    if length(list) < 2:
        return list
    else:
        if head(list) <= minimum(tail(list)):
            return head(list) followed by sort(tail(list))
        else:
            return sort(tail(list) followed by head(list))

minimum(list):
    return head(sort(list))

EDIT: The 6 element list took just over 3 hours to sort.

Re: Deliberately bad algorithms

Posted: Thu Jun 04, 2015 2:19 pm UTC
by phlip
benneh wrote:O(n^n) (phlip, are you sure yours isn't at least as bad as this?)

Well, in mine the "n"s aren't quite measuring the same thing... so it's O(k'^n) loops of the main loop where k' is the range of the list (max minus min) and n is the length. Except complexities are usually given in terms of the length, not just the number of values, so k'=2k (ie max minus min is k bits long), and the outer loop runs O(2kn) times. Inside that it loops through every permutation of a list of length n, O(n!), and inside that it checks if two lists of length n are equal, O(n). Hence the full O(2knn!n) I came up with.

benneh wrote:<horrific sort/minimum recursive mess>
I like it. Essentially an inefficient selection sort, but where the "selection" step is in turn defined recursively using sort...

Re: Deliberately bad algorithms

Posted: Thu Jun 04, 2015 5:15 pm UTC
by benneh
phlip wrote:Well, in mine the "n"s aren't quite measuring the same thing... so it's O(k'^n) loops of the main loop where k' is the range of the list (max minus min) and n is the length. Except complexities are usually given in terms of the length, not just the number of values, so k'=2k (ie max minus min is k bits long), and the outer loop runs O(2kn) times. Inside that it loops through every permutation of a list of length n, O(n!), and inside that it checks if two lists of length n are equal, O(n). Hence the full O(2knn!n) I came up with.
Ah, I see. So if the length of the list is significantly larger than the range, duplicates become inevitable, which don't inconvenience your algorithm as much, and your algorithm performs better than mine; whereas if the range is significantly larger than the length of your list, your algorithm produces far more unnecessary 'permutations' to check, and my algorithm performs better than yours.

In a similar vein, a number is prime if it has no non-trivial prime factors, right?

Code: Select all

isPrime n = length (filter (\ k -> isPrime k && n `mod` k == 0) [2 .. n-1]) == 0

Re: Deliberately bad algorithms

Posted: Thu Jun 04, 2015 6:28 pm UTC
by Flumble
benneh wrote:In a similar vein, a number is prime if it has no non-trivial prime factors, right?

Code: Select all

isPrime n = length (filter (\ k -> isPrime k && n `mod` k == 0) [2 .. n-1]) == 0

You're evil.

Then again, real-life Haskell will optimize the shit out of that line. The only inefficiency left is that it checks for factors larger than √n.

A quick test to see if an integer is even:

Code: Select all

isEven n = (lcm n 2) == n
   where lcm a b = minimum (intersect [a,2*a..b*a] [b,2*b..a*b])

(Sorry for the finite lists; haskell wants to iterate over one of the lists completely, instead of doing a 'diagonal' search.)

Re: Deliberately bad algorithms

Posted: Thu Jun 04, 2015 7:07 pm UTC
by benneh
Flumble wrote:You're evil.

Then again, real-life Haskell will optimize the shit out of that line. The only inefficiency left is that it checks for factors larger than √n.
Thank you :). My tests indicate that GHC doesn't optimise it much at all, though. I wrote a quick program to print out a list of prime numbers using that algorithm; after 2 hours, it's got up to 37.

Re: Deliberately bad algorithms

Posted: Thu Jun 04, 2015 11:56 pm UTC
by hotaru
benneh wrote:My tests indicate that GHC doesn't optimise it much at all, though.

speaking of things that GHC doesn't optimize much at all...

Code: Select all

loeb = fix (fmap . flip id =<<)

Re: Deliberately bad algorithms

Posted: Fri Jun 05, 2015 12:48 am UTC
by Flumble
benneh wrote:My tests indicate that GHC doesn't optimise it much at all, though. I wrote a quick program to print out a list of prime numbers using that algorithm; after 2 hours, it's got up to 37.

I was promised (maybe not exactly promised) by my professor that GHC would cache all the intermediate results of isPrime and short-cut the list-building. Although, it appears that GHCi doesn't know that a list, once non-empty, can never reach a length of 0. (not.).any /= (((==0).length).).filter in manner of execution.

Re: Deliberately bad algorithms

Posted: Fri Jun 05, 2015 1:58 am UTC
by Derek
Flumble wrote:
benneh wrote:My tests indicate that GHC doesn't optimise it much at all, though. I wrote a quick program to print out a list of prime numbers using that algorithm; after 2 hours, it's got up to 37.

I was promised (maybe not exactly promised) by my professor that GHC would cache all the intermediate results of isPrime and short-cut the list-building. Although, it appears that GHCi doesn't know that a list, once non-empty, can never reach a length of 0. (not.).any /= (((==0).length).).filter in manner of execution.

Memoization is not free. It can result in significant speedups, but can also consume significant memory if applied naively. I sort of doubt that any compiler could decide automatically whether to memoize or not in all situations.

I was doing an Euler problem once, one of the harder ones, and wrote some code to memoize the results of a function. It very quickly consumed all the memory on my system. I had to go back and break up the function so that it had one part that could be effectively memoized, and the rest was not.

Re: Deliberately bad algorithms

Posted: Sat Jun 06, 2015 5:17 pm UTC
by benneh
hotaru wrote:speaking of things that GHC doesn't optimize much at all...

Code: Select all

loeb = fix (fmap . flip id =<<)
What is this supposed to do?

Re: Deliberately bad algorithms

Posted: Sun Jun 07, 2015 3:18 am UTC
by hotaru
benneh wrote:
hotaru wrote:speaking of things that GHC doesn't optimize much at all...

Code: Select all

loeb = fix (fmap . flip id =<<)
What is this supposed to do?

if you replace fmap with map and look at the type signature, it's usual use (as a "spreadsheet" function) should become apparent:

Code: Select all

loeb $ const 0 : const 1 : map (\n xs -> (xs !! n) + (xs !! succ n)) [0..]


but it can also be used with other things, not just lists.

Re: Deliberately bad algorithms

Posted: Sun Jun 07, 2015 9:51 am UTC
by LucasBrown
Could you explain that for people who don't know Haskell?

Re: Deliberately bad algorithms

Posted: Sun Jun 07, 2015 10:18 am UTC
by phlip
Spoilered for offtopic (ie not deliberately bad)
Spoiler:
It's kinda the "fix" function lifted over a list of functions... a more readable version (for people that don't Haskell) could be written like how "fix" is written:

Code: Select all

fix f = x
  where x = f x

loeb fs = x
  where x = [f x | f <- fs]

That is, fix calls a function with the parameter being the return value from the same function (thanks to lazy evaluation)... essentially finding a fixed point of the function. So, for instance:

Code: Select all

f x = [0] ++ (map (+1) x)
fix f -- returns [0, 1, 2, 3, 4, ...]
You can see that if you take that resulting list, and pass it to f, you get the same list back out.

"loeb" does the same thing, to a list of functions:

Code: Select all

fs = [const 1, head, length]
loeb fs -- returns [1, 1, 3]
Those three functions, when passed the resulting list, return 1, 1 and 3, so that's the list.

Re: Deliberately bad algorithms

Posted: Sun Jun 07, 2015 8:10 pm UTC
by Derek
One thing that has always bugged me about Haskell is the community's fetish for point free function definitions, resulting in the most unreadable mess of symbols since APL. This,

Code: Select all

loeb = fix (fmap . flip id =<<)


is unreadable, and should never be used outside of a golf competition. This,

Code: Select all

loeb fs = x
  where x = [f x | f <- fs]


Is perfectly readable to anyone who has seen list comprehensions before (and can probably be understood by many people who haven't), and didn't even need to use helper functions that the reader also needs to understand.

Re: Deliberately bad algorithms

Posted: Sun Jun 07, 2015 10:14 pm UTC
by hotaru
Derek wrote:One thing that has always bugged me about Haskell is the community's fetish for point free function definitions, resulting in the most unreadable mess of symbols since APL. This,

Code: Select all

loeb = fix (fmap . flip id =<<)


is unreadable, and should never be used outside of a golf competition. This,

Code: Select all

loeb fs = x
  where x = [f x | f <- fs]


Is perfectly readable to anyone who has seen list comprehensions before (and can probably be understood by many people who haven't), and didn't even need to use helper functions that the reader also needs to understand.

that doesn't actually work, tho:

Code: Select all

f g = loeb . flip (,) (g . fst)


also, this happened.

Re: Deliberately bad algorithms

Posted: Sun Jun 21, 2015 10:47 pm UTC
by DR6
Derek wrote:One thing that has always bugged me about Haskell is the community's fetish for point free function definitions, resulting in the most unreadable mess of symbols since APL. This,

Code: Select all

loeb = fix (fmap . flip id =<<)


is unreadable, and should never be used outside of a golf competition. This,

Code: Select all

loeb fs = x
  where x = [f x | f <- fs]


Is perfectly readable to anyone who has seen list comprehensions before (and can probably be understood by many people who haven't), and didn't even need to use helper functions that the reader also needs to understand.


Only your example only works for lists. Try:

Code: Select all

loeb fs = x
    where x = fmap ($x) fs


As long as you know what the ($x) means, it's pretty understandable. Otherwise, I get your point: I have no idea what on earth fmap . flip id =<< is supposed to do.

Re: Deliberately bad algorithms

Posted: Mon Jun 22, 2015 12:36 am UTC
by phlip
DR6 wrote:Only your example only works for lists.

That's because I was explicitly trying to write something that would be readable to someone unfamiliar with Haskell, and a list comprehension fills that role better than map. Agreed that "fmap ($x)" is better if you have a passing familiarity for the language.

DR6 wrote:Otherwise, I get your point: I have no idea what on earth fmap . flip id =<< is supposed to do.

You can get a bit of a head-start by recognising that ($) is equivalent to "id" restricted to functions. So the ($x) in your version is equivalent to "flip id x".

From there you some manipulations to make it point-free, so it can use "fix" rather than explicit self reference, and that's where you end up.

Re: Deliberately bad algorithms

Posted: Mon Jun 22, 2015 5:30 pm UTC
by Yakk
benneh wrote:I have no idea how to work out the running time of that monstrosity. It can sort a 5 element list in less than a second, but I started sorting a 6 element list when I started writing this post, and it hasn't finished yet.

EDIT: For a maximum balance of simplicity and inefficiency:

Code: Select all

sort(list):
    if length(list) < 2:
        return list
    else:
        if head(list) <= minimum(tail(list)):
            return head(list) followed by sort(tail(list))
        else:
            return sort(tail(list) followed by head(list))

minimum(list):
    return head(sort(list))

EDIT: The 6 element list took just over 3 hours to sort.

Strange. I'm getting merely n! from that:

Code: Select all

Let S(n) be the cost of sorting n elements.

Let S(n,m) be the cost where the first element is m away from the right place.
S(n) <= S(n, n-1)

S(1) = 1
S(n,0) <= 1 + 2S(n-1) (the case where head(list)<=min(tail(list)))
S(n,k) <= 1 + S(n-1) + S(n, k-1) (otherwise)

So S(n) <= n + (n+1) S(n-1)

which works out to (n+1)! no?

So the n=6 case should be only 7 times slower than the n=5 case.

What did I miss?

Re: Deliberately bad algorithms

Posted: Mon Jun 22, 2015 9:14 pm UTC
by hotaru
DR6 wrote:

Code: Select all

loeb fs = x
    where x = fmap ($x) fs


As long as you know what the ($x) means, it's pretty understandable.

why not just write it as

Code: Select all

loeb fs = fmap ($loeb fs) fs

? once someone goes through the process of figuring out how that works, they're 99% of the way to understanding "fix". from there, "flip id" is the same as "flip ($)", and "(=<<)" is just "flip (>>=)".

Re: Deliberately bad algorithms

Posted: Mon Jun 22, 2015 9:26 pm UTC
by Derek
And if you need two posts on a forum, hell if you need even one post, to explain how your single line of code works, your code is unreadable and should be rewritten.