计算排列中的排列数

Question

大小为 n 的排列是 n 个整数的序列，其中从 1 到 n 的每个值恰好出现一次。例如，序列 [3, 1, 2]、[1] 和 [1, 2, 3, 4] 是排列，而 [2]、[4, 1, 2]、[3, 1] 不是排列.

所以我收到 2 个输入：1 - 排列中的数字数量，2 - 排列本身。

问题是：有多少个区间 [l;r](1 ≤ l ≤ r ≤ n) 使得序列 p[l..r] 也是一个排列？ 例如：

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]

希望你能理解这个问题。

我写了前2个案例，但我不知道如何检查其他案例：

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

Answer 1

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)

实际上只是用这个例子尝试了一下，如果有错误请告诉我。

Answer 2

在 O(n) 中，在排列中找到“1”。

初始化以下内容：

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

重复执行以下操作：

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.

想法：我们总是添加最小的邻居，因为它必须包含在任何包含较大邻居的排列中。如果我们考虑的元素总数等于我们看到的最大元素，那么我们必须拥有从 1 到最大元素的所有元素，因此我们找到了另一种排列。

示例：[6, 3, 4, 1, 2, 7, 5]

排列候选者将按此顺序考虑

[1] count = 1
[1, 2] count = 2 (max elt = size = 2 so we increment count)
[4, 1, 2] (max elt = 4, size = 3 so we don't increment count)
[3, 4, 1, 2] count = 3 (max elt = size = 4, increment count)
[6, 3, 4, 1, 2]
[6, 3, 4, 1, 2, 7]
[6, 3, 4, 1, 2, 7, 5] count = 4 (max elt = size = 7, increment count)

这是线性时间，恒定内存。

Answer 3

在 R 中，您可以使用

embed

，如下所示

f <- function(x) {
    helper <- function(m) {
        m[do.call(pmax, asplit(m, 2)) == ncol(m), ncol(m):1]
    }
    Filter(length, lapply(seq_along(x), \(k) helper(embed(x, k))))
}

你将获得

> f(c(6, 3, 4, 1, 2, 7, 5))
[[1]]
[1] 1

[[2]]
[1] 1 2

[[3]]
[1] 3 4 1 2

[[4]]
[1] 6 3 4 1 2 7 5