Generating specific permutation patterns in python

Question

I'm trying to model a probabilistic system. The system I am working with involves three elements - call them 'X', 'Y' and 'Z'. These elements form strings in a specific type of alternating pattern, where X must be alternating with either Y or Z (i.e. XX, YY, ZZ, YZ and ZY connections are forbidden). I would like to permute lists of all possible sequences for different string lengths.

My initial attempt at this was to generate all possible permutations of these three characters, and filter out any patterns that are forbidden. Unfortunately permutations scale very poorly for long sequence lengths. I solved this problem by generating each sequence, one character at a time, and checking the conditions I set forth as the sequence is being constructed. This prevents the generation of unproductive sequences very early on and drastically decreases the number of permutations being generated. The problem is that I'm not much of a coder, and I had to hardcode a bunch of nested for-loops in order to achieve this goal. The code below is shown for a string length of 5.

Length = 5
Units = ['X','Y','Z']
Sequences = []

#aij is the j'th character in the sequence

for i1 in range(len(Units)):
    ai1 = n[i1]
    for i2 in range(len(Units)):
        ai2 = Units[i2]

#If the two most recent sequential units are identical OR (Y and Z) OR (Z and Y), pass

    if ai2 == ai1 or ai2==Units[1] and ai1==Units[2] or ai2==Units[2] and ai1==Units[1]:
        pass
    else:

#repeat for the other characters in the sequence until the final character is reached

        for i3 in range(len(Units)):
            ai3 = Units[i3]
            if ai3 == ai2 or ai3==Units[1] and ai2==Units[2] or ai3==Units[2] and ai2==Units[1]:
                pass
            else:
                for i4 in range(len(Units)):
                    ai4 = Units[i4]
                    if ai4 == ai3 or ai4==Units[1] and ai3==Units[2] or ai4==Units[2] and ai3==Units[1]:
                        pass
                    else:
                        for i5 in range(len(Units)):
                            ai5 = Units[i5]
                            if ai5 == ai4 or ai5==Units[1] and ai4==Units[2] or ai5==Units[2] and ai4==Units[1]:
                                pass
                            else:

#Append the valid sequence to my list of Sequences

                                a = ai1 + ai2 + ai3 + ai4 + ai5
                                Sequences.append(a)

print(Sequences)

Output:

['XYXYX', 'XYXZX', 'XZXYX', 'XZXZX', 'YXYXY', 'YXYXZ', 'YXZXY', 'YXZXZ', 'ZXYXY', 'ZXYXZ', 'ZXZXY', 'ZXZXZ']

My question is, how can i generalize this type of algorithm to a function that simply takes the input "Length" (i.e. number of characters in the string) and generates all of my sequence patterns in a list?

Ajax1234 · Answer 1 · 2018-12-07T20:29:47.223

2

You can use a generator with recursion:

def combinations(d, _len, current = []):
  if len(current) == _len:
     yield current
  else:
     for i in d:
       if not current or ('X' in current and current[-1] != i):
         yield from combinations(d, _len, current+[i])


results = list(map(''.join, combinations(['X','Y','Z'], 5)))
final_results = [a for i, a in enumerate(results) if a not in results[:i]]

Output:

['XYXYX', 'XYXYZ', 'XYXZX', 'XYXZY', 'XYZXY', 'XYZXZ', 'XYZYX', 'XYZYZ', 'XZXYX', 'XZXYZ', 'XZXZX', 'XZXZY', 'XZYXY', 'XZYXZ', 'XZYZX', 'XZYZY']

edited Dec 07 '18 at 20:29

answered Dec 07 '18 at 20:13

Ajax1234

69,937
8
61
102

Close to what I need, but ZY and YZ sequences are forbidden. – user8273394 Dec 10 '18 at 15:50

score 0 · Accepted Answer · answered Dec 07 '18 at 21:47

For ['X','Y','Z'] there are 9 pair that can be create. But pair XX, YY, ZZ, YZ, ZY are forbidden. So it remains XY,XZ,YX,ZX. Divide it into two units (units1 and units2) to avoid XX in permutation. If the length is even, it simply do permutation for each units using itertools product (see: generating permutations with repetitions in python). It will produce list of tuple that can be join to string (see: Why can't I join this tuple in Python?). Append that two list.

For odd case, combinations of units 1 will produce any combination with X prefix, so append 'X' to the last of each string and Y,Z to the begin. For units 2 combination do the reverse. It will produce not unique list, so casting to the set is just for make it unique

import itertools

def combine(length):
    units1 = ['XY','XZ']
    units2 = ['YX','ZX']

    combine1 = ["".join(map(str,p)) for p in itertools.product(units1,repeat=int(length/2))]
    combine2 = ["".join(map(str,p)) for p in itertools.product(units2,repeat=int(length/2))]

    if (length%2 == 1):
        combine1_odd = [item + 'X' for item in combine1] + ['Y' + item for item in combine1] + ['Z' + item for item in combine1]
        combine2_odd = ['X' + item for item in combine2] + [item + 'Y' for item in combine2] + [item + 'Z' for item in combine2]
        return list(set(combine1_odd + combine2_odd))

    return list(set(combine1 + combine2))

print(combine(5))

Generating specific permutation patterns in python

2 Answers2