News for hackers. Stuff that matters.
Re:Bogo-bogosort by ChristianMarks on Sunday December 29, 2013 @01:05AM (#6978618)
There is also the slightly less pointless ordersort, which works only on permutations. The complexity of ordersort is given by the Landau function. It is more efficient than bogosort, however.

  #!/usr/bin/python

  def gcd(a,b):
    while b:
      a, b = b, a % b
    return a

  def order(a):
    """compute the order of the permutation a"""
    lcm = 1 
    for i in range(len(a)):
      j = a[i]
      while j > i:
        j = a[j]
      if j == i: # i is a cycle leader
        j = a[j]	# get next element of cycle
        cyc = 1;	# the cycle has length at least 1
        while j != i:   # the cycle hasn't closed
          cyc += 1
          j = a[j]
        lcm = (lcm/gcd(lcm,cyc))*cyc
    return lcm

  def ordersort(a):
    ord = order(a)
    print ord
    b = range(len(a))
    while ord > 0:
      b = map((lambda i: a[i]), b)
      ord -= 1
    return b

  if __name__ == '__main__':
    from random import shuffle
    a = range(50);
    shuffle(a)
    print a, ordersort(a)

There are no comments on this comment yet.