Ask Your Question

Revision history [back]

To start to follow the suggestion at https://ask.sagemath.org/question/60560/partitioning-a-1-1square-matrix-into-0-11summand-matrices/, consider this function:

def sum_list(length, total):
    """
    INPUT:

    - length -- how many terms
    - total -- desired total

    Return list of lists, each of which has ``length`` entries chosen
    from {0, 1, -1} and adds up to ``total``.
    """
    C = IntegerListsLex(length=length, n=length+total, min_part=0, max_part=2)
    return [[a-1 for a in L] for L in C]

(It's only two lines long; everything between the """ lines is a comment.)

Sample use to get all lists of length 4 that add up to 1:

sage: sum_list(4, 1)
[[1, 1, 0, -1],
 [1, 1, -1, 0],
 [1, 0, 1, -1],
 [1, 0, 0, 0],
 [1, 0, -1, 1],
 [1, -1, 1, 0],
 [1, -1, 0, 1],
 [0, 1, 1, -1],
 [0, 1, 0, 0],
 [0, 1, -1, 1],
 [0, 0, 1, 0],
 [0, 0, 0, 1],
 [0, -1, 1, 1],
 [-1, 1, 1, 0],
 [-1, 1, 0, 1],
 [-1, 0, 1, 1]]

Now try to build up matrices using sum_list(LENGTH, 1) and sum_list(LENGTH, -1) based on the entries of your given matrix.

To start to follow the suggestion at https://ask.sagemath.org/question/60560/partitioning-a-1-1square-matrix-into-0-11summand-matrices/, consider this function:

def sum_list(length, total):
    """
    INPUT:

    - length -- how many terms
    - total -- desired total

    Return list of lists, each of which has ``length`` entries chosen
    from {0, 1, -1} and adds up to ``total``.
    """
    C = IntegerListsLex(length=length, n=length+total, min_part=0, max_part=2)
    return [[a-1 for a in L] for L in C]

(It's only two lines long; everything between the """ lines is a comment.)

Sample use to get all lists of length 4 that add up to 1:

sage: sum_list(4, 1)
[[1, 1, 0, -1],
 [1, 1, -1, 0],
 [1, 0, 1, -1],
 [1, 0, 0, 0],
 [1, 0, -1, 1],
 [1, -1, 1, 0],
 [1, -1, 0, 1],
 [0, 1, 1, -1],
 [0, 1, 0, 0],
 [0, 1, -1, 1],
 [0, 0, 1, 0],
 [0, 0, 0, 1],
 [0, -1, 1, 1],
 [-1, 1, 1, 0],
 [-1, 1, 0, 1],
 [-1, 0, 1, 1]]

Now try to build up matrices using sum_list(LENGTH, 1) and sum_list(LENGTH, -1) based on the entries of your given matrix.

The following is a draft, and it could probably be sped up, but it seems to work. It treats a solution (A,B) as different from (B,A): the order matters.

def sum_list(length, total):
    """
    INPUT:

    - length -- how many terms
    - total -- desired total

    Return list of lists, each of which has ``length`` entries chosen
    from {0, 1, -1} and adds up to ``total``.
    """
    C = IntegerListsLex(length=length, n=length+total, min_part=0, max_part=2)
    return [[a-1 for a in L] for L in C]

def mat_list(mat, length):
    """
    INPUT:

    - mat -- matrix, assumed to have entries in {1, -1}
    - length -- how many terms

    Return list of lists, each of which has ``length`` entries and
    adds up to ``mat``, and each entry is either a `(0, 1)` or a `(0,
    -1)` matrix.
    """
    sum_plus = sum_list(length, 1)
    sum_minus = sum_list(length, -1)
    old_attempts = []
    for x in mat.list():
        if x == 1:
            sums = sum_plus
        elif x == -1:
            sums = sum_minus
        else:
            raise ValueError('each entry of matrix should be 1 or -1')
        if not old_attempts: # initial step
            new_attempts = [[[s] for s in S] for S in sums]
        else:
            new_attempts = []
            for mats in old_attempts:
                NEW = []
                for S in sums:
                    new_M = [M + [s] for (M, s) in zip(mats, S)]
                    # keep only entries that correspond to (0,1) or (0,-1) matrices
                    if all(max(entries) - min(entries) < 2 for entries in new_M):
                        NEW.append([M + [s] for (M, s) in zip(mats, S)])
                new_attempts.extend(NEW)
        old_attempts = new_attempts

    matrices = [[matrix(mat.base_ring(), mat.nrows(), mat.ncols(), entries) for entries in L] for L in old_attempts]
    return matrices

With this code:

sage: mat = matrix(ZZ, [[1, 1, 1, 1], [1, -1, 1, -1], [1, 1, -1, -1], [1, -1, -1, 1]])
sage: %time L = mat_list(mat, 3)
CPU times: user 8.04 s, sys: 141 ms, total: 8.18 s
Wall time: 8.18 s
sage: len(L)
179328

To start to follow the suggestion at https://ask.sagemath.org/question/60560/partitioning-a-1-1square-matrix-into-0-11summand-matrices/, consider this function:

def sum_list(length, total):
    """
    INPUT:

    - length -- how many terms
    - total -- desired total

    Return list of lists, each of which has ``length`` entries chosen
    from {0, 1, -1} and adds up to ``total``.
    """
    C = IntegerListsLex(length=length, n=length+total, min_part=0, max_part=2)
    return [[a-1 for a in L] for L in C]

(It's only two lines long; everything between the """ lines is a comment.)

Sample use to get all lists of length 4 that add up to 1:

sage: sum_list(4, 1)
[[1, 1, 0, -1],
 [1, 1, -1, 0],
 [1, 0, 1, -1],
 [1, 0, 0, 0],
 [1, 0, -1, 1],
 [1, -1, 1, 0],
 [1, -1, 0, 1],
 [0, 1, 1, -1],
 [0, 1, 0, 0],
 [0, 1, -1, 1],
 [0, 0, 1, 0],
 [0, 0, 0, 1],
 [0, -1, 1, 1],
 [-1, 1, 1, 0],
 [-1, 1, 0, 1],
 [-1, 0, 1, 1]]

Now try to build up matrices using sum_list(LENGTH, 1) and sum_list(LENGTH, -1) based on the entries of your given matrix.

The following is a draft, and it could probably be sped up, but it seems to work. It treats a solution (A,B) as different from (B,A): the order matters.

def sum_list(length, total):
    """
    INPUT:

    - length -- how many terms
    - total -- desired total

    Return list of lists, each of which has ``length`` entries chosen
    from {0, 1, -1} and adds up to ``total``.
    """
    C = IntegerListsLex(length=length, n=length+total, min_part=0, max_part=2)
    return [[a-1 for a in L] for L in C]

def mat_list(mat, length):
    """
    INPUT:

    - mat -- matrix, assumed to have entries in {1, -1}
    - length -- how many terms

    Return list of lists, each of which has ``length`` entries and
    adds up to ``mat``, and each entry is either a `(0, 1)` or a `(0,
    -1)` matrix.
    """
    sum_plus = sum_list(length, 1)
    sum_minus = sum_list(length, -1)
    old_attempts = []
    for x in mat.list():
        if x == 1:
            sums = sum_plus
        elif x == -1:
            sums = sum_minus
        else:
            raise ValueError('each entry of matrix should be 1 or -1')
        if not old_attempts: # initial step
            new_attempts = [[[s] for s in S] for S in sums]
        else:
            new_attempts = []
            for mats in old_attempts:
                NEW = []
                for S in sums:
                    new_M = [M + [s] for (M, s) in zip(mats, S)]
                    # keep only entries that correspond to (0,1) or (0,-1) matrices
                    if all(max(entries) - min(entries) < 2 for entries in new_M):
                        NEW.append([M + [s] for (M, s) in zip(mats, S)])
                new_attempts.extend(NEW)
        old_attempts = new_attempts

    matrices = [[matrix(mat.base_ring(), mat.nrows(), mat.ncols(), entries) for entries in L] for L in old_attempts]
    return matrices

With this code:

sage: mat = matrix(ZZ, [[1, 1, 1, 1], [1, -1, 1, -1], [1, 1, -1, -1], [1, -1, -1, 1]])
sage: %time L = mat_list(mat, 3)
CPU times: user 8.04 s, sys: 141 ms, total: 8.18 s
Wall time: 8.18 s
sage: len(L)
179328

EDIT: here is a modification, in case you don't want to distinguish the same lists with a different ordering:

def mat_list_NEW(mat, length):
    """
    INPUT:

    - mat -- matrix, assumed to have entries in {1, -1}
    - length -- how many terms

    Return list of lists, each of which has ``length`` entries and
    adds up to ``mat``, and each entry is either a `(0, 1)` or a `(0,
    -1)` matrix.
    """
    sum_plus = sum_list(length, 1)
    sum_minus = sum_list(length, -1)
    old_attempts = []
    for x in mat.list():
        if x == 1:
            sums = sum_plus
        elif x == -1:
            sums = sum_minus
        else:
            raise ValueError('each entry of matrix should be 1 or -1')
        if not old_attempts: # initial step
            new_attempts = set(tuple([(s,) for s in S]) for S in sums)
        else:
            new_attempts = set()
            for mats in old_attempts:
                NEW = set()
                for S in sums:
                    new_M = tuple(sorted(M + (s,) for (M, s) in zip(mats, S)))
                    # keep only entries that correspond to (0,1) or (0,-1) matrices
                    if all(max(entries) - min(entries) < 2 for entries in new_M):
                        NEW.add(new_M)
                new_attempts.update(NEW)
        old_attempts = new_attempts

    matrices = [[matrix(mat.base_ring(), mat.nrows(), mat.ncols(), entries) for entries in L] for L in old_attempts]
    return matrices

The differences: use the set structure so that duplicates are automatically removed, and sort the lists before adding them to the set, so that it's easy to recognize duplicates. Elements of a set have to be hashable so use tuples instead of lists. With this new version:

sage: mat = matrix(ZZ, [[1, 1, 1, 1], [1, -1, 1, -1], [1, 1, -1, -1], [1, -1, -1, 1]])
sage: %time L = mat_list_NEW(mat, 3)
CPU times: user 1.47 s, sys: 41 ms, total: 1.51 s
Wall time: 1.53 s
sage:  len(L)
29889

But the lengths of the lists are still going to get large as the number of summands increases...
Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.
about | faq | help | privacy policy | terms of service
Powered by Askbot version 0.7.59