permute2.py

#!/usr/bin/env python
"""
Permute the characters of an encoding space.
"""

import math
import sys

def permute_arbitrary(chars, _len, arr, s):
    """Permutes an arbitrary encoding space, each permutation being a string of chars of length _len"""
    if len(s) == _len:
        arr.append(s)
        return arr
    
    for char in chars:
        arr = permute_arbitrary(chars, _len, arr, s+char)
    
    return arr

def permute_standard(base, n):
    """Permutes the standard bin, oct, and hex encoding spaces.  Returns n permutations, padded for consistency."""
    if n == 0:
        return []

    f_str = '{:0{:d}BASE}'    
    if base is 'binary':
        f_str = f_str.replace('BASE', 'b')
        base = 2
    elif base is 'oct':
        f_str = f_str.replace('BASE', 'o')
        base = 8
    elif base is 'hex':
        f_str = f_str.replace('BASE', 'x')
        base = 16
    else:
        print('Error: base "%s" not recognized' % base)
        return []
    
    # int() needed because math.ceil(math.log(1, 2)) returns 0.0, at least in the tests
    padding = int(math.ceil(math.log(n, base)))

    arr = []
    for i in range(n):
        arr.append(f_str.format(i, padding))
    return arr

test_standard_perms = [
    ('binary', 0, []),
    ('binary', 1, ['0']),
    ('binary', 2, ['0', '1']),
    ('binary', 4, ['00', '01', '10', '11']),
    ('binary', 8, ['000', '001', '010', '011', '100', '101', '110', '111']),
    ('binary', 9, ['0000', '0001', '0010', '0011', '0100', '0101', '0110', '0111', '1000']),
    ('oct', 8, ['0', '1', '2', '3', '4', '5', '6', '7']),
    ('oct', 9, ['00', '01', '02', '03', '04', '05', '06', '07', '10']),
    ('hex', 8, ['0', '1', '2', '3', '4', '5', '6', '7']),
    ('hex', 17, ['00', '01', '02', '03', '04', '05', '06', '07', '08', '09', '0a', '0b', '0c', '0d', '0e', '0f', '10']),
]

test_bogus_standard_perms = [
    ('foo', 1, []),
    ('bar', 1<32, []),
]

test_arbitrary_perms = [
    ('01', 4, 16), # binary: 2**4
    ('01234567', 2, 64), # oct: 8**2
    ('0123456789abcdef', 2, 256), # hex: 16**2

    (' .', 4, 16), # "binary": 2**4
    ('abc', 3, 27), # 3**3
    ('abc', 4, 81), # 3**4
]

if __name__ == '__main__':
    # Test arbitrary encoding
    trunc = 20
    for e, _len, cnt in test_arbitrary_perms:
        perms = permute_arbitrary(e, _len, [], '')
        if len(perms) != cnt:
            print('Error: len(perms) = %d want %d' % (len(perms), cnt))
            # sys.exit(1)
        print('permute(\'%s\', %d, [], \'\')[:%d] =' % (e, _len, trunc))
        and_more = ', ...]' if len(perms) > trunc else ']'
        print(str(perms[:trunc]).replace(']', and_more))
        print('')

    # Test standard encoding
    for base, _len, want in test_standard_perms:
        perms = permute_standard(base, _len)
        if perms != want:
            print('permute_standard(\'%s\', %d) = %s want %s' % (base, _len, perms, want))
    
    # Test bogus standard encoding
    print('Testing bogus encodings, expect Error msgs')
    for base, _len, want in test_bogus_standard_perms:
        perms = permute_standard(base, _len)
        if perms != want:
            print('permute_standard(\'%s\', %d) = %s want %s' % (base, _len, perms, want))