Want more features on Pastebin? Sign Up, it's FREE!
Guest

finding k missing numbers in a permutation of 0..n-1

By: hieuza on Oct 21st, 2012  |  syntax: Python  |  size: 0.94 KB  |  views: 273  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #!/usr/bin/env python
  2. # @ hieuza [x] gmail.com
  3.  
  4. # find k missing numbers in an array of (n - k) elements
  5. # the element values are in range 0 .. n-1
  6.  
  7. # complexity: time O(n), space O(k)
  8.  
  9. def find_k_missing(a, n):
  10.         if len(a) == n: # not missing any number
  11.                 return []
  12.  
  13.         if len(a) == 0: # missing all the number
  14.                 return range(n)
  15.  
  16.         a.extend([a[0]]*(n - len(a)))
  17.  
  18.         for i in xrange(n):
  19.                 while a[i] != a[a[i]]:
  20.                         # swap a[i] and a[a[i]]
  21.                         t = a[i]
  22.                         a[i] = a[t]
  23.                         a[t] = t # always one element is put in correct position
  24.  
  25.         return [i for i in xrange(n) if a[i] != i]
  26.  
  27.  
  28. def test(n, k):
  29.         import random
  30.         a = range(n)
  31.         random.shuffle(a)
  32.         a = a[:n-k]
  33.  
  34.         print 'a:', a
  35.         print 'n:', n
  36.  
  37.         res = find_k_missing(a, n)
  38.  
  39.         print '>:', res
  40.  
  41.  
  42. if __name__ == '__main__':
  43.         import sys
  44.  
  45.         n = 5
  46.         k = 3
  47.  
  48.         print 'usage: [n] [k]'
  49.  
  50.         if len(sys.argv) > 1:
  51.                 n = int(sys.argv[1])
  52.  
  53.         if len(sys.argv) > 2:
  54.                 k = int(sys.argv[2])
  55.  
  56.         test(n, k)
clone this paste RAW Paste Data