Skip to content

Instantly share code, notes, and snippets.

@isnowfy
Last active December 14, 2015 12:38
Show Gist options
  • Save isnowfy/5087654 to your computer and use it in GitHub Desktop.
Save isnowfy/5087654 to your computer and use it in GitHub Desktop.
stable partition
import random
def partition(arr):
index = odd = 0
maxn = arr[0]
for i in range(len(arr)):
if arr[i] % 2 == 1:
odd += 1
maxn = max(maxn, arr[i])
maxn += 1
for i in range(len(arr)):
arr[i] *= maxn
for i in range(len(arr)):
if (arr[i]/maxn) % 2 == 1:
arr[index] += arr[i]/maxn
index += 1
else:
arr[odd] += arr[i]/maxn
odd += 1
for i in range(len(arr)):
arr[i] %= maxn
return arr
if __name__ == '__main__':
#arr = [5, 6, 8, 2, 3, 9, 4]
arr = []
nodd = neven = 0
for i in range(10):
tmp = random.randint(0, 1)
arr.append(tmp*(neven*2) + (1-tmp)*(nodd*2+1))
neven += tmp
nodd += (1-tmp)
print arr
print partition(arr)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment