Проверьте, есть ли порядок возрастания в списке списка целых чисел (Python)
Учитывая список списков, как это:
[[2, 7], [1, 4], [0, 5, 6]]
Как я могу проверить, есть ли в этом списке допустимый порядок возрастания. Например, это будет True, потому что я могу сформировать такой порядок:
[2,4,5]
Мне нужен алгоритм, который каким-то образом может найти допустимый порядок для произвольно большого списка со списками любого размера. Ни одно целочисленное значение не будет повторяться, а подсписки будут отсортированы.
редактировать: Это то, что я сейчас пробовал, но он не будет масштабироваться до больших списков.
allNumbers = [[2, 7], [1, 4], [0, 5, 6]]
smallest = min(allNumbers[0])
largest = max(allNumbers[2])
for n in allNumbers[1]:
if smallest < n < largest:
return True
Я только что добавил то, что пробовал, но застрял, думая, как это будет масштабироваться для списков длиной более 3
Что вы на самом деле имеете в виду? Что считается «действительным порядком возрастания в этом списке»? Не понятно, о чем вы спрашиваете.
Ответы 5
Вы можете решить это, используя жадный алгоритм, подобный этому.
a = [[2, 7], [1, 4], [0, 5, 6]]
current = min(a[0])
possible = True
for l in a[1:]:
possible = False
for i in l:
if i >= current:
possible = True
current = i
break
if not possible:
break
print(possible) #returns True
Рад помочь. :)
Для каждого подсписка найдите наименьший элемент, который все еще больше, чем предыдущий наименьший элемент. Если такого элемента нет, то нет и восходящего пути.
from math import inf
def ascend(xss):
smallest = -inf
path = []
for xs in xss:
smallest = min(x for x in xs if x > smallest)
path.append(smallest)
return path
>>> ascend([[2, 7], [1, 4], [0, 5, 6]])
[2, 4, 5]
>>> ascend([[2, 7], [1, 4], [0, 5, 6], [0]])
Traceback (most recent call last):
...
ValueError: min() arg is an empty sequence
Вот мой ответ.
def tell_if_the_lists_are_in_order(lists):
min_first = min(lists[0]) # for empty input, return True.
prev_min = min_first
for sublist in lists[1:]:
min_num = min(sublist)
max_num = max(sublist)
if max_num <= prev_min:
return False
prev_min = min(x for x in sublist if x > prev_min)
return True
Вот мой ответ:
def IsAscending(list):
ascend = True
int a;
for i in list:
if i == 0:
a = list[i]
else:
if list[i] >= a:
a = list[i]
else:
ascend = False
return ascend
Вот окончательное решение, которое я получил
def validList(chLocations):
ascendingOrder = []
smallest = min(chLocations[0])
maximum = max(chLocations[-1])
ascendingOrder.append(smallest)
chLocations = chLocations[1:]
for i in range(len(chLocations)-1):
for number in chLocations[i]:
if number > max(ascendingOrder):
ascendingOrder.append(number)
break
ascendingOrder.append(maximum)
if sorted(ascendingOrder) == ascendingOrder:
return True
else:
return False
>>> validList([[2, 7], [1, 4], [0, 5, 6]])
True
>>> validList([[1, 3], [7], [2]])
False
Объяснение:
[[2, 7], [1, 4], [0, 5, 6]] --> [2,4,5] == True
[[1, 3], [7], [2]] --> [1,7,2] == False
Итак, для [[2], [1], [3]] вы хотите True? Потому что это то, что говорит ваше решение (после того, как вы добавите недостающее :).
Добро пожаловать в СО. Можете ли вы также опубликовать то, что вы пробовали?