Enumerating Oriented Gene Orderings

This is yet another problem with permutations. As in the previous problems of this type we get a positive integer n and are supposed to find some permutations. This time we are looking at signed permutations, that is, for all the positive integers in the range 1 to n we should also take into account their corresponding negative value. As in Enumerating Gene Orders, we should print the total number of permutations followed by each of the permutations.

Sample dataset:

2

Expected output:

8

-1 -2

-1 2

1 -2

1 2

-2 -1

-2 1

2 -1

2 1

Note that we should not count permutations of the same integer (i. e. -1 1, 2 -1 and so on should not be included).

For this problem we can once again utilise the itertools function permutations. However, this time we need to pair it to the itertools function product. The following is my code:

import itertools                                                           

n = 3                                                                      

permutation = []                                                           

nr = 0                                                                     

for i in itertools.permutations(list(range(1, n + 1))):                    

    for j in itertools.product([-1, 1], repeat=len(list(range(1, n + 1)))):

        perm = [a * sign for a, sign in zip(i, j)]                         

        permutation.append(perm)                                           

        nr += 1                                                            

print(nr)                                                                  

for i in range(len(permutation)):                                          

    print(*permutation[i], sep=' ')                                        

Partial Permutations

We are back with the permutations once again. This time we are set the task to find the number of partial permutations that can be formed from a set of numbers. We are given two integers, n and k, where the range of 1 to n is the set of numbers and k is the length of the partial mutations and should return the number of partial mutations modulo 1 000 000.

Sample data:
21 7

Expected output:
51200

I wrote two programs that solve this problem. The first uses the math module permutations to find all possible permutations and count them. You can have a look at the code below. However, this program is inefficient which is why I chose to write a second, faster program.

Slow approach:

import itertools
n = 21
k = 7
count = 0
for p in itertools.permutations(range(1, n + 1), k):
    count += 1
print(count % 1000000)

Faster approach:

n = 21
k = 7

partial_perm = 1

for i in range(k):
    partial_perm *= (n - i)
print(partial_perm % 1000000)

Both of the programs work and complete the problem within the time limits of Rosalind, but the second program is much faster than the first one. 

Longest Increasing Subsequence

This problem had me going for quite a while, and I ended up getting a lot of help from various places on the internet. But I have now managed to solve it and I will try to explain my solution here. Let's start with the description.

In this problem we are given a permutation of length n (where n is smaller than or equal to 10 000) and we are asked to find the longest increasing and decreasing subsequence of the permutation. A subsequence of a permutation is a collection of elements from the permutation in the order that they appear (note that they don't have to come directly after one another). The subsequence is said to be increasing if the elements increase (from left to right) and it is said to be decreasing if the elements decrease (again, left to right). For example, in the permutation (5, 1, 4, 2, 3) the subsequence (1, 2, 3) is increasing and the subsequence (5, 4, 2) is decreasing.

The fact that the subsequence can 'skip' numbers messed up my initial solution for this problem, but after spending some time trying to figure out how the algorithm described in this Wikipedia page works and looking through a very good explanation of it on Stack Overflow (as well as working through the algorithm with pen and paper to figure out how it operates. I know, I'm a tad bit old-school), I managed to adapt the code on Stack Overflow to also find the longest decreasing subsequence. The code below is what I ended up with. The function for finding the decreasing subsequence is talmost he same as for finding the increasing subsequence, so I have highlighted the differences. I would highly recommend having a look at the thread on Stack Overflow if you would like a good explanation of the algorithm.

data = []                                #This first bit reads the file which
with open('sampledata.txt', 'r') as f:   #contains the the length of the 
    for line in f:                       #permutation and then the permutation, 
        for nr in line.split():          #separated by spaces. The numbers are 
            data.append(int(nr))         #appended to a list as integers.
perm = data[1:]


def increasing(seq):
    P = [None] * len(seq)
    M = [None] * len(seq)

    L = 1
    M[0] = 0
    for i in range(1, len(seq)):
        lo = 0
        hi = L
        if seq[M[hi - 1]] < seq[i]:
            j = hi
        else:
            while hi - lo > 1:
                mid = (hi + lo) // 2
                if seq[M[mid - 1]] < seq[i]:
                    lo = mid
                else:
                    hi = mid

            j = lo
        P[i] = M[j - 1]
        if j == L or seq[i] < seq[M[j]]:
            M[j] = i
            L = max(L, j + 1)

    result = []
    pos = M[L - 1]
    for k in range(L):
        result.append(seq[pos])
        pos = P[pos]

    return (result[::-1])


def decreasing(seq):
    P = [None] * len(seq)
    M = [None] * len(seq)

    L = 1
    M[0] = 0
    for i in range(1, len(seq)):
        lo = 0
        hi = L
        if seq[M[hi - 1]] > seq[i]:
            j = hi
        else:
            while hi - lo > 1:
                mid = (hi + lo) // 2
                if seq[M[mid - 1]] > seq[i]:
                    lo = mid
                else:
                    hi = mid

            j = lo
        P[i] = M[j - 1]
        if j == L or seq[i] > seq[M[j]]:
            M[j] = i
            L = max(L, j + 1)

    result = []
    pos = M[L - 1]
    for k in range(L):
        result.append(seq[pos])
        pos = P[pos]

    return (result[::-1])

incr = increasing(perm)
decr = decreasing(perm)

print(*incr)
print(*decr)

Enumerating Gene Orders

In this problem we are given the task to find all the possible permutations of a list from 1 to n, where n ≤ 7. We are given n and are supposed to return the total number of permutations and a list of all the different permutations. To clarify, if we are told that n = 3, then the total number of permutations is 3! which is equal to 6 and we should print the following:

6      

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

It was fairly easy to make this program since Python3 has a built in library for factorials and another built in library for making permutations. The following is the final code:

import math                                         

import itertools                                    

n = 3                                               

print(math.factorial(n))                            

perm = itertools.permutations(list(range(1, n + 1)))

for i, j in enumerate(list(perm)):                  

    permutation = ''                                

    for item in j:                                  

        permutation += str(item) + ' '              

    print(permutation)