#!/usr/bin/python
# -*- coding: utf-8 -*-
"""Some operations on matrices over GF(2) represented as lists of integers.

The row corresponding to the LSB is last, and correspondingly, the
column corresponding to the LSB is printed last.

"""
import operator
import random
import sys


def mxor(matrix, vector):
    return reduce(operator.xor, [row for ii, row in enumerate(reversed(matrix))
                                 if vector & (1 << ii)],
                  0)

def random_matrix(n):
    return [random.randrange(1<<n) for ii in range(n)]

def permutations(matrix):
    "Generate the permutation of all possible bitvectors."
    return (mxor(matrix, vector) for vector in range(1<<len(matrix)))

def is_nonsingular(matrix):
    # This is a ridiculously inefficient way to detect singularity:
    # test all possible bitvectors to see if two of them map to the
    # same thing.
    permutation = list(permutations(matrix))
    return len(permutation) == len(set(permutation))

def random_nonsingular_matrix(n):
    while True:
        matrix = random_matrix(n)
        if is_nonsingular(matrix):
            return matrix

def invert(matrix):
    # This is also ridiculously inefficient.
    p = list(permutations(matrix))
    return [p.index(1<<ii) for ii in reversed(range(len(matrix)))]

def show(matrix):
    for row in matrix:
        yield ' '.join('1' if row & (1 << ii) else '0'
                       for ii in reversed(range(len(matrix))))

def to_int(matrix):
    accumulator = 0
    for row in matrix:
        accumulator = (accumulator << len(matrix)) | row
    return accumulator

if __name__ == '__main__':
    n = 8 if len(sys.argv) == 1 else int(sys.argv[1])
    matrix = random_nonsingular_matrix(n)
    print 'The numbers', matrix, 'represent the matrix:'
    print '\n'.join(show(matrix))
    print 'It generates the index permutation', list(permutations(matrix))
    print 'It can be represented as the number', to_int(matrix)
    imatrix = invert(matrix)
    print 'Inverted, it is', imatrix, 'which is to say:'
    print '\n'.join(show(imatrix))
    print 'This generates the inverse permutation', list(permutations(imatrix))