A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

Wildcard
Candlestick!
Posts: 253
Joined: Wed Jul 02, 2008 12:42 am UTC
Location: Outside of the box

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). There's no such thing as a funny sig.

Tub
Posts: 472
Joined: Wed Jul 27, 2011 3:13 pm UTC

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.

hotaru
Posts: 1045
Joined: Fri Apr 13, 2007 6:54 pm UTC

Code: Select all

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

Code: Select all

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

EvanED
Posts: 4331
Joined: Mon Aug 07, 2006 6:28 am UTC
Contact:

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 1isPrime n = factorial (n - 1) `mod` n == n - 1`
Very nice

Wildcard
Candlestick!
Posts: 253
Joined: Wed Jul 02, 2008 12:42 am UTC
Location: Outside of the box

hotaru wrote:

Code: Select all

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

Wow. Perfect example. It's not merely inefficient, it's actually elegantly bad. 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. There's no such thing as a funny sig.

LucasBrown
Posts: 299
Joined: Thu Apr 15, 2010 2:57 am UTC
Location: Poway, CA

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 redef isprime(n): return not re.match(r'^1?\$|^(11+?)\1+\$', '1'*n)` https://pypi.python.org/pypi/labmath
3239×21412529+1 is prime!

PM 2Ring
Posts: 3713
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Sydney, Australia

hotaru wrote:

Code: Select all

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

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

benneh
Posts: 74
Joined: Tue Aug 26, 2008 8:24 am UTC

There's the obvious:

Code: Select all

`fib 0 = 0fib 1 = 1fib 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 assort [] = []`
EDIT: Actually, I think this is O(n!). In which case, I name this algorithm 'stupider sort'.

Wildcard
Candlestick!
Posts: 253
Joined: Wed Jul 02, 2008 12:42 am UTC
Location: Outside of the box

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 There's no such thing as a funny sig.

Flumble
Yes Man
Posts: 2248
Joined: Sun Aug 05, 2012 9:35 pm UTC

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.

 Forgot the code tag
Last edited by Flumble on Wed Jun 03, 2015 10:51 pm UTC, edited 1 time in total.

Thesh
Posts: 6579
Joined: Tue Jan 12, 2010 1:55 am UTC

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;         }      }   }}`
Last edited by Thesh on Wed Jun 03, 2015 10:04 pm UTC, edited 2 times in total.
Summum ius, summa iniuria.

somehow
Posts: 99
Joined: Wed Aug 14, 2013 8:31 pm UTC

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 Yes, your psuedocode correctly translates benneh's code, which was written in Haskell (as was hotaru's factorial-based primality tester).
Xenomortis wrote:O(n2) takes on new meaning when trying to find pairs of socks in the morning.

Derek
Posts: 2181
Joined: Wed Aug 18, 2010 4:15 am UTC

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 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)

EvanED
Posts: 4331
Joined: Mon Aug 07, 2006 6:28 am UTC
Contact:

Flumble wrote:That reminds me of SlowSort (not an alias of bogosort)

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)`

Thesh
Posts: 6579
Joined: Tue Jan 12, 2010 1:55 am UTC

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 Truedef is_sorted(a):    for i in range(1, len(a)):        if a[i] < a[i-1]:            return False;    return Truedef 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.
Summum ius, summa iniuria.

Derek
Posts: 2181
Joined: Wed Aug 18, 2010 4:15 am UTC

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).

Nitrodon
Posts: 497
Joined: Wed Dec 19, 2007 5:11 pm UTC

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 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.

Wildcard
Candlestick!
Posts: 253
Joined: Wed Jul 02, 2008 12:42 am UTC
Location: Outside of the box

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 1234123 is sorted = false3214    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 1243124 is sorted = false2143    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 1342134 is sorted = false1432    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 2341234 is sorted = truereturn 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. There's no such thing as a funny sig.

Thesh
Posts: 6579
Joined: Tue Jan 12, 2010 1:55 am UTC

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 Truedef 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 Truedef 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.
Summum ius, summa iniuria.

phlip
Restorer of Worlds
Posts: 7572
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

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 itertoolsdef 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)).

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 + firstimport timeit, itertools, pprintresults = []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) # yes, using the "real" sort here... so sue mepprint.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 + firstimport itertools, pprintresults = []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)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)]`

Code: Select all

`enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}`
[he/him/his]

Thesh
Posts: 6579
Joined: Tue Jan 12, 2010 1:55 am UTC

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.
Summum ius, summa iniuria.

benneh
Posts: 74
Joined: Tue Aug 26, 2008 8:24 am UTC

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] -> BoolisSorted [] = TrueisSorted [_] = TrueisSorted (a:as) = a <= minimum as && isSorted asminimum :: (Ord a) => [a] -> aminimum = head . sortfind' :: (a -> Bool) -> [a] -> afind' 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.

phlip
Restorer of Worlds
Posts: 7572
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

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...

Code: Select all

`enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}`
[he/him/his]

benneh
Posts: 74
Joined: Tue Aug 26, 2008 8:24 am UTC

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`

Flumble
Yes Man
Posts: 2248
Joined: Sun Aug 05, 2012 9:35 pm UTC

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.)

benneh
Posts: 74
Joined: Tue Aug 26, 2008 8:24 am UTC

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.

hotaru
Posts: 1045
Joined: Fri Apr 13, 2007 6:54 pm UTC

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 =<<)`

Code: Select all

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

Flumble
Yes Man
Posts: 2248
Joined: Sun Aug 05, 2012 9:35 pm UTC

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.

Derek
Posts: 2181
Joined: Wed Aug 18, 2010 4:15 am UTC

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.

benneh
Posts: 74
Joined: Tue Aug 26, 2008 8:24 am UTC

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?

hotaru
Posts: 1045
Joined: Fri Apr 13, 2007 6:54 pm UTC

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.

Code: Select all

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

LucasBrown
Posts: 299
Joined: Thu Apr 15, 2010 2:57 am UTC
Location: Poway, CA

Could you explain that for people who don't know Haskell? https://pypi.python.org/pypi/labmath
3239×21412529+1 is prime!

phlip
Restorer of Worlds
Posts: 7572
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

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 xloeb 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 =  ++ (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.

Code: Select all

`enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}`
[he/him/his]

Derek
Posts: 2181
Joined: Wed Aug 18, 2010 4:15 am UTC

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.

hotaru
Posts: 1045
Joined: Fri Apr 13, 2007 6:54 pm UTC

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.

Code: Select all

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

DR6
Posts: 171
Joined: Thu Nov 01, 2012 1:44 pm UTC

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.

phlip
Restorer of Worlds
Posts: 7572
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

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.

Code: Select all

`enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}`
[he/him/his]

Yakk
Poster with most posts but no title.
Posts: 11128
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

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) = 1S(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?
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

hotaru
Posts: 1045
Joined: Fri Apr 13, 2007 6:54 pm UTC

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 (>>=)".

Code: Select all

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

Derek
Posts: 2181
Joined: Wed Aug 18, 2010 4:15 am UTC