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

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

大小为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]也是一个置换?举例来说:

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

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

  1. numbers = int(input("Amount of elements in permutation: "))
  2. perm = list(input("Permutation: "))
  3. perm = [ int(x) for x in perm if x != " "]
  4. amount = 1
  5. first = 1
  6. if len(perm) == numbers and int(max(perm)) == numbers and int(min(perm)) == 1:
  7. if first in perm and len(perm) > 1:
  8. amount += 1
polhcujo

polhcujo1#

  1. l = [6, 3, 4, 1, 2, 7, 5]
  2. left_bound = right_bound = l.index(1)
  3. permutations = []
  4. for i in range(1,len(l)+1):
  5. new_index = l.index(i)
  6. # special case if i == 1
  7. if new_index == left_bound == right_bound:
  8. pass
  9. # if new index if further to the left, update the left index
  10. elif new_index < left_bound:
  11. left_bound = new_index
  12. # same with the right one
  13. elif new_index > right_bound:
  14. right_bound = new_index
  15. # Because we always have all numbers up to and including i
  16. # in the list l[left_bound:right_bound+1], we know that if
  17. # it has not the length i, numbers that are not in the order
  18. # are in there -> no permutation.
  19. if len(l[left_bound:right_bound+1])==i:
  20. permutations.append(l[left_bound:right_bound+1])
  21. print(permutations)

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

展开查看全部
scyqe7ek

scyqe7ek2#

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

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

重复执行以下操作:

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

思想:我们总是添加最小的邻居,因为它必须包含在任何包含较大邻居的排列中。如果我们考虑的元素总数等于我们看到的最大元素,那么我们必须有从1到最大元素的所有元素,所以我们找到了另一个排列。
示例:[6、3、4、1、2、7、5]
将按此顺序考虑置换候选项

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

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

展开查看全部
7kqas0il

7kqas0il3#

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

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

或使用for循环

  1. f2 <- function(x) {
  2. res <- c()
  3. for (i in seq_along(x)) {
  4. for (j in i:length(x)) {
  5. v <- x[i:j]
  6. if (max(v) == length(v)) {
  7. res <- append(res, list(v))
  8. }
  9. }
  10. }
  11. res
  12. }

你将获得

  1. > f1(c(6, 3, 4, 1, 2, 7, 5))
  2. [[1]]
  3. [1] 1
  4. [[2]]
  5. [1] 1 2
  6. [[3]]
  7. [1] 3 4 1 2
  8. [[4]]
  9. [1] 6 3 4 1 2 7 5

  1. > f2(c(6, 3, 4, 1, 2, 7, 5))
  2. [[1]]
  3. [1] 6 3 4 1 2 7 5
  4. [[2]]
  5. [1] 3 4 1 2
  6. [[3]]
  7. [1] 1
  8. [[4]]
  9. [1] 1 2
展开查看全部

相关问题