Counting number of permutations in permutation-CodePudding

A permutation of size n is a sequence of n integers in which each of the values from 1 to n occurs exactly once. For example, the sequences [3, 1, 2], [1], and [1, 2, 3, 4] are permutations, while [2], [4, 1, 2], [3, 1] are not.

So i recieve 2 inputs: 1 - number of numbers in permutation,2 - the permutation by itself.

The question is: how many intervals are there [l;r](1 ≤ l ≤ r ≤ n) for which the sequence p[l..r] is also a permutation? For example:

input - 7; [6, 3, 4, 1, 2, 7, 5]
The answer is 4:
permutation is [6, 3, 4, 1, 2, 7, 5];
permutation is [1];
permutation is [1, 2];
permutation is [3, 4, 1, 2]

Hope u undestood the question.

I wrote the first 2 cases, but i don't know how to check for others:

numbers = int(input("Amount of elements in permutation: "))
perm = list(input("Permutation: "))
perm = [ int(x) for x in perm if x != " "]
amount = 1
first = 1
if len(perm) == numbers and int(max(perm)) == numbers and int(min(perm)) == 1:
    if first in perm and len(perm) > 1:
        amount  = 1

CodePudding user response：

l = [6, 3, 4, 1, 2, 7, 5]

left_bound = right_bound = l.index(1)

permutations = []

for i in range(1,len(l) 1):
    new_index = l.index(i)

    # special case if i == 1
    if new_index == left_bound == right_bound:
        pass

    # if new index if further to the left, update the left index
    elif new_index < left_bound:
        left_bound = new_index

    # same with the right one
    elif new_index > right_bound:
        right_bound = new_index

    # Because we always have all numbers up to and including i
    # in the list l[left_bound:right_bound 1], we know that if
    # it has not the length i, numbers that are not in the order
    # are in there -> no permutation.
    if len(l[left_bound:right_bound 1])==i:
        permutations.append(l[left_bound:right_bound 1])

print(permutations)

Actually just tried it with that one example, if there is an error pls tell me.

CodePudding user response：

In O(n), find '1' in the permutation.

Initialize the following:

count = 1
max_elt = 1
`l` and `r` point to the left and right indices adjacent to 1.

Repeatedly do the following:

Consider whichever pointer points to the smaller value
Set max_elt to the greater of itself and that value
if `r` - `l` = max_elt then increment count
update the relevant pointer to be one further from 1.

Idea: We always add the smallest neighbor since it must be included in any permutation which contains the larger neighbor. If the total number of elements we're considering is equal to the max element we've seen, then we must have all the elements from 1 to the max elements, so we've found another permutation.

Example: [6, 3, 4, 1, 2, 7, 5]

Permutation candidates will be considered in this order

[1] count = 1
[1, 2] count = 2
[4, 1, 2]
[3, 4, 1, 2] count = 3
[6, 3, 4, 1, 2]
[6, 3, 4, 1, 2, 7]
[6, 3, 4, 1, 2, 7, 5] count = 4

This is linear time, constant memory.