大小為 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
uj5u.com熱心網友回復：
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)
實際上只是用那個例子試了一下，如果有錯誤請告訴我。
uj5u.com熱心網友回復：
在 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)
這是線性時間，恒定記憶。
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/520469.html
標籤：Pythonr算法排列