Download:
child 6:15484103f89b
parent 4:d783d7b930fe
5:cb085cd3f4f8
Anton Shestakov <engored@ya.ru>, Tue, 15 Jan 2013 22:17:13 +0900
Bitarrays and sets.

1 файлов изменено, 50 вставок(+), 0 удалений(-) [+]
using-bitarray-to-represent-sets/example.py file | annotate | diff | comparison | revisions
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/using-bitarray-to-represent-sets/example.py Tue Jan 15 22:17:13 2013 +0900
@@ -0,0 +1,50 @@
+#!/usr/bin/env python
+
+import string
+from bitarray import bitarray
+
+
+PARTLEN = 5 # 5 bits per character
+CHARS = (string.ascii_lowercase + string.digits)[:2 ** PARTLEN]
+# 'abcdefghijklmnopqrstuvwxyz012345'
+
+
+PARTS = {}
+for i, char in enumerate(CHARS):
+ PARTS[char] = bitarray(bin(i).lstrip('-0b').rjust(PARTLEN, '0'), endian='big')
+# {
+# 'a': bitarray('00000'),
+# ...
+# '5': bitarray('11111')
+# }
+
+
+def encode_set(ids):
+ times, more = divmod(max(ids) + 1, PARTLEN)
+ length = PARTLEN * (times + bool(more))
+ ba = bitarray(length, endian='big')
+ ba.setall(0)
+
+ for id in ids:
+ ba[id] = 1
+
+ return ''.join(ba.decode(PARTS))
+
+
+def decode_set(string):
+ result = bitarray(endian='big')
+ result.encode(PARTS, string)
+ return set(result.search(bitarray('1')))
+
+
+print(encode_set({1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 15, 16})) # Buttons in an elevator in Shanghai
+# 'o52y'
+
+print(encode_set({1, 4, 11, 16, 24, 29, 33, 35, 39, 45, 47, 51, 56, 58, 62, 64})) # Aronson's sequence
+# 'jaiibbcrauikf'
+
+print(decode_set('5'))
+# {0, 1, 2, 3, 4}
+
+print(decode_set('choices'))
+# {3, 7, 8, 9, 11, 12, 13, 16, 23, 27, 30, 33}