- 計算子序列
如果滿足以下兩個條件，則稱一個數字序列是好的：
- 序列中的所有元素都是唯一的。
- 如果序列中的最小元素是a，而序列中的最大元素是b，那么[a, b] 范圍內的所有數字都存在于序列中。例如，(4, 2, 5, 1, 3) 是一個好的序列，而 (2, 2, 1) 或 (3, 7) 則不是。陣列 arr 的子序列是可以從陣列 arr 派生的序列，方法是洗掉一些元素或不洗掉元素，而不改變其余元素的順序。
給定一個包含 n 個整數的陣列，找出不同的好子序列的數量。如果兩個子序列包括至少一個不同的索引，則它們被認為是不同的。例如，對于序列 (2, 2, 1)，由索引 1 和 2 形成的 (2, 1) 和由索引 0 和 2 形成的 (2, 1) 都被認為是不同的子序列。示例 考慮陣列 arr = [13, 11, 4, 12, 5, 4]。我們可以形成以下好的子序列： ? 長度為 1 的子序列：[13]、[11]、[4]、[12]、[5]、[4]、
? 長度為 2 的子序列：[13, 12], [11, 12], [4, 5], [5, 4]
? 長度為 3 的子序列：[13, 11, 12] 因此，答案是 6 4 1 = 11。 函式說明 在下面的編輯器中完成函式 countGoodSubsequences。countGoodSubsequences 有以下引數： int arr[n]：給定的整數陣列回傳 long int：可以從陣列中匯出的好子序列的數量，
這是我的代碼：
import itertools
def is_good_sequence(array):
minimum = min(array)
maximum = max(array)
good_sequence_list = list(range(minimum, maximum 1))
checked = []
if sorted(array) != good_sequence_list:
return False
for i in array:
if i in checked:
return False
else:
checked.append(i)
return True
def countGoodSubsequences(arr):
good_sequences = []
for i in range(1, len(arr) 1):
t = list(itertools.permutations(arr, i))
for j in t:
if is_good_sequence(j):
good_sequences.append(j)
return good_sequences
但是它不會回傳例外的答案
uj5u.com熱心網友回復：
為了解決您的問題，您可以使用內置set獲取唯一編號和sorted連續編號。
numbers = [13, 11, 4, 12, 5, 4]
unique_numbers = sorted(set(numbers))
gaps = [
i for i in range(1, len(unique_numbers))
if unique_numbers[i] - unique_numbers[i-1] > 1
]
consecuteves = []
i0 = i1 = 0
for i1 in gaps:
consecuteves.append(tuple(unique_numbers[i0:i1]))
i0 = i1
consecuteves.append(tuple(unique_numbers[i1:len(unique_numbers)]))
consecuteves
從這一點開始，您可以使用遞回函式將連續數字拆分為較小的塊。
可能的遞回看起來像這樣
def split(consecutive):
result = []
c1 = consecutive[:-1]
c2 = consecutive[1:]
if len(consecutive) > 1:
result.extend([c1, c2])
if len(consecutive) > 2:
sub_1 = split(c1)
sub_2 = split(c2)
if sub_1:
result.extend(sub_1)
if sub_2:
result.extend(sub_2)
return result
所以你可以得到你的塊如下：
result = set()
for consecutive in consecuteves:
result.update(split(consecutive))
sorted(result, key=lambda s: (len(s), s))
但是，注意如果你只需要好的序列的數量，你不需要像我上面那樣創建它們，你可以只計算連續數字的子序列的數量。我把這個組合練習留給你。
因為我喜歡數學謎語，所以我得到了你的解決方案：
from collections import defaultdict
def frequency_count(sequence):
frequency = defaultdict(int)
for n in sequence:
frequency[n] = 1
return sorted(frequency.items())
def split(frequency):
sequence = [n for n, m in frequency]
gaps = [i for i in range(1, len(sequence)) if sequence[i] - sequence[i-1] > 1]
i0 = i1 = 0
for i1 in gaps:
yield frequency[i0:i1]
yield frequency[i1:len(frequency)]
def count_unique_consecutive(n):
return n*(n 1)//2
def _count_subsets(frequency):
for i, (n, m) in enumerate(frequency):
if m > 1:
f_new = frequency.copy()
f_new[i] = (n, 1)
n_single = _count_subsets(f_new)
n_left = count_unique_consecutive(i)
n_right = _count_subsets(frequency[i 1:])
return m*n_single - (m-1)*n_left - (m-1)*n_right
return count_unique_consecutive(len(frequency))
def count_subsets(sequence):
frequency = frequency_count(sequence)
consecutive = split(frequency)
return sum(map(_count_subsets, consecutive))
count_subsets([1,2,2,2,3,8,9,10])
The combinatoric part, counting subsets in a consecutive sequences, is basically the second diagonal of Pascal's triangle. I leave it to you to understand why. Counting frequencies is done with a default dictionary. In order to take care of multiplicity, you need to multiply the number of possible subsets where the multiple value appears. This is done by multiplying the entire consecutive range and subtracting the subsets left and right which do not overlap with the multi-count number so they only count once.
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/430964.html