I am looking to take a product of a large number of transpositions, and boil it down to a smaller number of products. I have the following code, and would like some input on efficient ways to boil these products down. Before I give the code, it is important to recognize the following:

Transpositions, a cyclic permutation of two elements, have the following properties:

  1. The product of identical transpositions cancel. For example, (1,2)(1,2)(2,3) = (2,3).
  2. Any product of the form (x,y)(y,z)(x,y) is equal to (y,z)(x,y)(y,z).
  3. Any transpositions which share no elements commute. That is, (u,v)(x,y)=(x,y)(u,v).

The code I have is below. This is a procedure which gets an input of a list that contains a number of 2-tuples which represent transpositions. For example, valid input is [(1,2)(2,3)(1,2)]. I have a small explanation at the bottom of the given code.

count = 1
while count != 0:
    count = 0
    repeatCount = 0
    swappedCount = 0
    for i in range(len(route)-1):
        if len(route) > 1 and repeatCount == 0:
            if route[i] == route[i+1]:
                count += 1
                repeatCount += 1

    for i in range(len(route)-3):
        if len(route) > 3 and swappedCount == 0:
            if route[i] == route[i+2] and route[i+1] == route[i+3]:
                count += 1
                swappedCount += 1

The first for loop searches of instances of property (1) above, and the second for loop search for instances of property (2). The counters repeatCounter and swappedCounter are my gross attempt to avoid an IndexError.

Any way to accomplish this completely, i.e. always be able to reduce any product to the absolute minimum, in a timely way would be greatly appreciated, as run time is a problem for the rest of the whole program.

For clarification, I will explain some of the context in which this problem appears. Consider a graph G with labeled vertices. On each vertex lies a pebble, p-i. A transposition in the given product corresponds to selecting an edge in G and swapping the pebbles that are incident to that edge.

Therefore, a product of transpositions corresponds to a process of exchanging pebbles of edges, and the end result is a permutation of the pebbles on G which is described by the permutation given by the product of transpositions.

Hence, this process of boiling down a product of transpositions is an attempt to reduce the number of exchanges needed to achieve any permutation of pebbles on a graph G.


1 Answer 1


I would have thought it would be easier to computer the composition of all of your permutations and then try to factor that down again. I don't know whether that will be optimal but I imagine that the rules your talking about are the kind of thing that would cancel out when you multiply the permutations out. In this approach you basically want two functions: one to multiply out (hopefully resulting in cancellations) and another to factor back into transpositions. In your example

(1,2)(2,3)(1,2) -> (2,3)

Multiplying out gives a transposition which is clearly optimal for this permutation.

Here's some code for multiplying permutations. The code converts them to dicts and then multiplies the dict permutations and simplifies the parts the redundant swaps:

def to_dict(p):
    d = {p[i]: p[i+1] for i in range(len(p)-1)}
    d[p[-1]] = p[0]
    return d

def perm_prod2(d1, d2):
    keys = d1.keys() | d2.keys()
    d3 = {}
    for n in keys:
        newn = n
        newn = d2.get(newn, newn)
        newn = d1.get(newn, newn)
        if n != newn:
            d3[n] = newn
    return d3

def perm_prodn(ps):
    ds = [to_dict(p) for p in ps]
    d = ds[0]
    for di in ds[1:]:
        d = perm_prod2(d, di)
    return d

print(perm_prodn([(1, 2),(1, 2), (2, 3)]))

That gives you:

{2: 3, 3: 2}

which is the dict representation for

(2, 3)

To finish this off you just need some code that can turn the dict back into a product of transpositions. It is straight-forward to partition it into cycles and then each cycle can be factored to transpositions as described here.

Not the answer you're looking for? Browse other questions tagged or ask your own question.