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

Code: Select all

factorial product enumFromTo 1
isPrime n
factorial (1) `mod== 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 1
isPrime 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 1
isPrime 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 re
def isprime(n): return not re.match(r'^1?\$|^(11+?)\1+\$', '1'*n)

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

hotaru wrote:

Code: Select all

factorial = product . enumFromTo 1
isPrime 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 = 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'.

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: 2227
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: 6568
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: 2180
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: 6568
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 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.
Summum ius, summa iniuria.

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

Thesh
Posts: 6568
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 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.
Summum ius, summa iniuria.

phlip
Restorer of Worlds
Posts: 7569
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 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)).

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

Code: Select all

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

Thesh
Posts: 6568
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] -> Bool
isSorted [] = True
isSorted [_] = True
isSorted (a:as) = a <= minimum as && isSorted as

minimum :: (Ord a) => [a] -> a

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:
else:

minimum(list):

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

phlip
Restorer of Worlds
Posts: 7569
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: 2227
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 1
isPrime n
factorial (1) `mod== 1

Flumble
Yes Man
Posts: 2227
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: 2180
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 1
isPrime n
factorial (1) `mod== 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?

phlip
Restorer of Worlds
Posts: 7569
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 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.

Code: Select all

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

Derek
Posts: 2180
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 1
isPrime n
factorial (1) `mod== 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: 7569
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: 11115
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:
else:

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

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