4 ms·
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 e
by ChristianMarks 13y ago
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)