Массив всех подмассивов python

Алгоритм Кадане в Python – пример использования

Далее мы обсудим алгоритм Кадане в Python и его свойство для решения задачи «Максимальная сумма подмассива». Мы узнаем концепцию алгоритма и поработаем над кодом Python для него, используя пример с соответствующими выходными данными. Наконец, мы обсудим временную сложность алгоритма и реальное применение алгоритма Кадане.

Что такое алгоритм Кадане в Python?

Алгоритм Кадане в Python – это один из популярных подходов, используемых для решения проблемы с помощью динамического программирования. Как мы уже знаем, задача определения максимума подмассива считается одной из популярных задач в области динамического программирования.

Проблема кажется простой, и решением должна быть сумма всех элементов данных в массиве. Однако это не так. Мы также встретим отрицательные целые числа как элементы данных в массиве, которые могут уменьшить сумму всего массива. Таким образом, мы воспользуемся помощью алгоритма Кадане для решения этой проблемы.

Алгоритм Кадане используется для поиска непрерывного подмассива в одномерном целочисленном массиве, который имеет максимально возможную сумму. Основным подходом будет применение метода грубой силы для решения проблемы. Однако при этом временная сложность решения будет O (n ^ 2), что совсем не впечатляет.

Следовательно, мы будем использовать алгоритм Кадане для решения задачи путем обхода всего массива с помощью двух переменных, чтобы отслеживать текущую и максимальную сумму. Наиболее важным аспектом, на который следует обращать внимание при использовании этогои алгоритма, является условие, с помощью которого мы будем обновлять обе переменные.

Понимание алгоритма максимальной суммы подмассива

Давайте теперь рассмотрим основные шаги алгоритма максимальной суммы подмассива, как показано ниже:

1. Шаг 1: мы должны инициализировать max_till_now = 0.
2. Шаг 2: мы должны инициализировать max_ending = 0.
3. Шаг 3: мы должны повторить шаги с 4 по 6 для каждого элемента данных в массиве.
4. Шаг 4. Мы должны установить max_ending = max_ending + a [i].
5. Шаг 5: Если(max_ending <0), мы должны установить max_ending = 0.
6. Шаг 6: Если(max_till_now
7. Шаг 7: мы должны вернуть max_till_now.

Мы использовали max_ending для поиска всех положительных элементов данных массива и max_till_now, чтобы найти максимальную сумму элементов данных среди всех положительных сегментов. Таким образом, каждый раз, когда мы получаем положительную сумму при сравнении с max_till_now, мы сможем обновить ее на большую сумму.

Следовательно, всякий раз, когда max_ending становится отрицательным, мы устанавливаем его равным нулю, и для каждой итерации мы будем проверять условие, при котором max_till_now меньше max_ending, чтобы обновить max_till_now, если условие возвращает True.

Использование графического представления в алгоритме Кадане

Давайте рассмотрим следующий пример с целочисленным массивом.

Рис.1: Целочисленный массив.

Рис. 2. Мы инициализируем max_till_now = 0 и max_ending = 0(n = 0).

Рис. 3. Тогда мы получим max_till_now = 0 и max_ending = 0 для n = 1; однако мы получим max_till_now = 4 и max_ending = 4 для n = 2.

Рис. 4. Затем мы присвоим значение n = 3 и 4 и получим max_till_now = 4 и max_ending = 3, а также max_till_now = 4 и max_ending = 1 соответственно.

Рис. 5. Мы получим max_till_now = 6(6> 4) для n = 5 и max_ending = 6.

Рис. 6: Мы также получим max_till_now = 6 и max_ending = 4 для n = 6.

Следовательно, из приведенного выше примера мы найдем максимальный подмассив в диапазоне от n = 2 до n = 5, а максимальная сумма будет равна 6.

Понимание алгоритма Кадане с использованием кода Python

Давайте рассмотрим следующий фрагмент кода, демонстрирующий работу алгоритма Кадане.

# defining the function to find the maximum subarray sum def max_Subarray_Sum(my_array, array_size): # assigning the variables maxTillNow = my_array[0] maxEnding = 0 # using the for-loop for n in range(0, array_size): maxEnding = maxEnding + my_array[n] # using the if-elif-else statement if maxEnding < 0: maxEnding = 0 elif(maxTillNow < maxEnding): maxTillNow = maxEnding return maxTillNow # defining the array my_array = [-2, -3, 4, -1, -2, 5, -3] # printing the maximum subarray sum for the users print("Maximum Subarray Sum:", max_Subarray_Sum(my_array, len(my_array)))

В приведенном выше фрагменте кода мы определили функцию как max_Subarray_Sum, принимающую два параметра как my_array и array_sum соответственно. Затем мы присвоили переменной maxTillNow первому значению индекса массива, а maxEnding – нулю. Затем мы использовали цикл for для перебора всего массива.

Мы также использовали условный оператор if-elif-else и возвращаем maxTillNow. Наконец, мы определили массив и распечатали максимальную сумму подмассивов для пользователей, которая в приведенном выше примере равна 6.

Временная сложность

Временная сложность алгоритма Кадана для массива, состоящего из n элементов данных в виде целого числа, определяется как O(n), поскольку в программе должен выполняться только один цикл for. Аналогично, сложность алгоритма во вспомогательном пространстве равна O(1).

Применение

Существуют различные применения алгоритма Кадане, некоторые из которых описаны ниже:

1. Алгоритм Кадане состоит в том, чтобы найти максимальную сумму подмассива для заданного массива целых чисел.
2. Он используется в качестве алгоритма обработки изображений.
3. Его также можно использовать для решения таких задач, как «Station Travel in Order» и «Hostels Along the Coast».
4. Он также используется для бизнес-анализа.

Заключение

Мы можем сделать вывод, что решение не кажется простым при постановке задачи нахождения максимальной суммы подмассива. Однако алгоритм Кадане ее упростил и достиг решения с наименьшими временными сложностями.

Это стало возможным, поскольку алгоритм Кадане использует метод сбора информации, необходимой для достижения решения, избегая нежелательного хранения данных. Следовательно, мы можем рассматривать этот алгоритм как простой пример подхода динамического программирования с множеством практических приложений в реальном мире.

Источник

Разница между подмассивом, подпоследовательностью и подмножеством

Подмассивы представляет собой срез непрерывного массива (т. е. занимает последовательные позиции) и по своей природе поддерживает порядок элементов. Например, подмассивы массива находятся , , , , , а также .

Ниже приведена программа на C, Java и Python для создания всех подмассивов указанного массива:

C

Java

Python

Обратите внимание, что есть именно n×(n+1)/2 подмассивы в массиве размером n . Кроме того, не существует такого понятия, как непрерывный подмассив. Префикс смежный иногда применяется, чтобы сделать контекст более ясным. Таким образом, непрерывный подмассив — это просто другое название подмассива.

2. Подстрока

А подстрока строки s это строка s' что происходит в s . Подстрока почти аналогична подмассиву, но в контексте строк.

Например, подстроки строки 'apple' находятся 'apple', 'appl', 'pple', 'app', 'ppl', 'ple', 'ap', 'pp', 'pl', 'le', 'a', 'p', 'l', 'e', '' . Ниже приведена программа на C++, Java и Python, которая генерирует все непустые подстроки указанной строки:

C++

результат:

't', 'te', 'tec', 'tech', 'techi', 'techie', 'e', 'ec', 'ech', 'echi', 'echie', 'c', 'ch', 'chi', 'chie', 'h', 'hi', 'hie', 'i', 'ie', 'e'

Java

результат:

't', 'te', 'tec', 'tech', 'techi', 'techie', 'e', 'ec', 'ech', 'echi', 'echie', 'c', 'ch', 'chi', 'chie', 'h', 'hi', 'hie', 'i', 'ie', 'e'

Python

результат:

t te tec tech techi techie e ec ech echi echie c ch chi chie h hi hie i ie e

3. Последующие действия

А последующая последовательность последовательность, которая может быть получена из другой последовательности путем удаления некоторых элементов без изменения порядка оставшихся элементов. Например, является подпоследовательностью последовательности полученный после удаления а также .

Люди часто путают подмассив/подстроку и подпоследовательность. Подмассив или подстрока всегда будут непрерывными, но подпоследовательность не обязательно должна быть непрерывной. То есть, подпоследовательности не обязаны занимать последовательные позиции в исходных последовательностях. Но мы можем сказать, что и непрерывная подпоследовательность, и подмассив одинаковы.

Другими словами, подпоследовательность — это обобщение подстроки, или подстрока — это уточнение подпоследовательности. Например, является следствием , но не подстрока, и является одновременно подмассивом и подпоследовательностью.

Обратите внимание, что подпоследовательность может быть в контексте как массивов, так и строк. Генерация всех подпоследовательностей массива/строки эквивалентна создание набора мощности массива/строки. Для заданного множества S , мы можем найти набор мощности, сгенерировав все двоичные числа между 0 а также 2 n -1 , куда n - это размер заданного набора. Этот подход демонстрируется ниже на C++, Java и Python:

Источник

Python разбивает массив на подмассивы эквивалентного ранга

У меня есть массив из n отсортированных значений.

Я хочу создать m подмассивов так, чтобы мой лучший элемент попадал в мой первый подмассив, мой второй элемент входил в мой второй подмассив и т. Д., А мой n+1-й лучший элемент помещался в мой первый под массив.

Если у меня есть только два массива, это легко, но если мне нужно больше двух подмассивов, я не знаю, как это сделать.

например, если у меня есть начальный массив:

a = [50, 45, 40, 35, 30, 25, 20, 10, 9, 8] 

И я хочу получить 3 подмассива:

x1: [50, 35, 20, 8] x2: [45, 30, 10] x3: [40, 25, 9] 

Какой самый эффективный / питонный способ сделать это?

5 ответов

ДЛЯ Х СУБЛИСТОВ:

Одна возможность будет сделать:

def get_sublists(original_list, number_of_sub_list_wanted): sublists = list() for sub_list_count in range(number_of_sub_list_wanted): sublists.append(original_list[sub_list_count::number_of_sub_list_wanted]) return sublists 

Затем вы можете распаковать вложенные списки, хранящиеся в sublist ,

a = [5,4,3,2,1,0] x1, x2 = get_sublists(a, 2) 

предоставит вам ожидаемый результат.

Это тривиальное решение. Их, вероятно, что-то более питоническое в itertools или другой библиотеке.

Если вы не понимаете, как работает этот код, взгляните на документацию среза.

Для 2 массивов

x1, x2 = map(list, zip(*zip(*[iter(a)] * 2))) print(x1, x2, sep='\n') [5, 3, 1] [4, 2, 0] 

Для 3 массивов

x1, x2, x3 = map(list, zip(*zip(*[iter(a)] * 3))) print(x1, x2, x3, sep='\n') [5, 2] [4, 1] [3, 0] 

Почему это работает

1. iter(a) создает итератор в списке a , Когда вы выполняете итерацию, элементы израсходованы, и в итоге итератор истощается.
2. [iter(a)] * 2 создает список, который выглядит следующим образом i = iter(a); [i, i] , Обратите внимание, что один и тот же итератор появляется дважды. Это означает, что когда я беру элемент из первого i Я тоже со второго i потому что они указывают на один и тот же итератор.
3. Так! когда я использую zip в распакованном списке того же итератора zip(*[iter(a)] * 2) Когда я объединяю вещи в пару, я извлекаю из одного и того же итератора и, следовательно, естественно исчерпываю их в том порядке, в котором мы хотим.
4. Я тогда использую другой zip транспонировать результаты, а затем map с list составить их списки вместо кортежей.

Ниже дадим желаемый ответ,

a = [5, 4, 3 ,2, 1, 0] a.sort(reverse=True) x1 = [] x2 = [] for i in range(len(a)): x1.append(a[i]) if (i%2==0) else x2.append(a[i]) print x1, x2 

a = [5, 4, 3 ,2, 1, 0] def get_original_val(original, x): return [original[index] for index in x] def get_index(a): index_x1, index_x2 = [], [] local_list = a if not len(a) % 2 else a + [0] for idx, x in enumerate(local_list): target = index_x2 if idx % 2 else index_x1 target.append(idx) get_x1 = get_original_val(a, index_x1) get_x2 = get_original_val(a, index_x2) return get_x1, get_x2 >>>x1, x2 = get_index(a) >>>x1 [5, 3, 1] >>>x2 [4, 2, 0] 

Вот мое решение проблемы. Он делит список размера l на n частей, где n-1 частей имеют равный размер l/n , а последний n имеет размер l/n + по модулю деления .

def get_sublists(original_list, sublists_number): list_size = len(original_list) sublist_size_except_last = list_size//sublists_number last_sublist_size = list_size%sublists_number sublists = list() l_index = 0 r_index = list_size-1 for i in range(sublists_number): l_index = (i*sublist_size_except_last) r_index = ((i+1)*sublist_size_except_last)-1 if i != sublists_number-1: sublists.append(text_list[l_index:r_index]) print(l_index,r_index) else: r_index = r_index+last_sublist_size print(l_index,r_index) sublists.append(text_list[l_index:r_index]) return sublists 

Для списка строк размером 6538434. Мы получаем 5 подсписков внутри одного списка, нарезанного следующим образом:

 original_list[0:1307685] original_list[1307686:2615371] original_list[2615372:3923057] original_list[3923058:5230743] original_list[5230744:6538433] 

Источник