R语言 排列中排列数的计数

dzhpxtsq  于 2023-09-27  发布在  其他
关注(0)|答案(3)|浏览(121)

大小为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]

希望你能理解这个问题。
我写了前两个案例,但我不知道如何检查其他案例:

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
polhcujo

polhcujo1#

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)

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

scyqe7ek

scyqe7ek2#

时间复杂度为O(n)。
初始化以下内容:

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)

这是线性时间,恒定的记忆。

7kqas0il

7kqas0il3#

在R中,可以像下面这样使用embed

f1 <- 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))))
}

或使用for循环

f2 <- function(x) {
    res <- c()
    for (i in seq_along(x)) {
        for (j in i:length(x)) {
            v <- x[i:j]
            if (max(v) == length(v)) {
                res <- append(res, list(v))
            }
        }
    }
    res
}

你将获得

> f1(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

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

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

[[3]]
[1] 1

[[4]]
[1] 1 2

相关问题