Можно ли отсортировать список с помощью Reduce?

Question

Мне дали это как упражнение. Конечно, я мог бы отсортировать список, используя sorted () или другими способами из стандартной библиотеки Python, но я не могу в этом случае. Я думаю Я должен использовать только lower () .

from functools import reduce
arr = [17, 2, 3, 6, 1, 3, 1, 9, 5, 3]
sorted_arr = reduce(lambda a,b : (b,a) if a > b else (a,b), arr)

Я получаю ошибку:

TypeError: '>' not supported between instances of 'tuple' and 'int'

Что и ожидается, потому что моя функция Reduce вставляет кортеж в массив int вместо 2 отдельных целых чисел. И тогда кортеж сравнивается с int ...

Есть ли способ вставить обратно 2 числа в список и запускать функцию только для каждого второго числа в списке? Или способ поменять числа с помощью метода limit ()?

Документация очень мало говорит о функции сокращения, так что я сейчас вне идей. https://docs.python.org/3/library/functools.html?highlight=reduce#functools.reduce

Answer 1

Вот один из способов сортировки списка, используя reduce:

arr = [17, 2, 3, 6, 1, 3, 1, 9, 5, 3]
sorted_arr = reduce(
    lambda a, b: [x for x in a if x <= b] + [b] + [x for x in a if x > b],
    arr,
    []
)
print(sorted_arr)
#[1, 1, 2, 3, 3, 3, 5, 6, 9, 17]

На каждом шаге уменьшения строят новый выходной список, который объединяет список всех значений, меньших или равных b, [b], и список всех значений, превышающих b. Используйте необязательный третий аргумент для reduce, чтобы инициализировать вывод в пустой список.

Answer 2

Я думаю, вы не понимаете, как работает Reduce. Редукция является синонимом с правой стороны в некоторых других языках (например, Haskell). Первый аргумент ожидает функцию, которая принимает два параметра: аккумулятор и элемент для накопления.

Давайте взломать это:

arr = [17, 2, 3, 6, 1, 3, 1, 9, 5, 3]
reduce(lambda xs, x: [print(xs, x), xs+[x]][1], arr, [])

Здесь xs - это аккумулятор, а x - это элемент для накопления. Не беспокойтесь слишком о [print(xs, x), xs+[x]][1] - он просто должен напечатать промежуточные значения xs и x. Без печати мы могли бы упростить лямбду до lambda xs, x: xs + [x], которая просто добавляется в список.

Вышеуказанные выходы:

[] 17
[17] 2
[17, 2] 3
[17, 2, 3] 6
[17, 2, 3, 6] 1
[17, 2, 3, 6, 1] 3
[17, 2, 3, 6, 1, 3] 1
[17, 2, 3, 6, 1, 3, 1] 9
[17, 2, 3, 6, 1, 3, 1, 9] 5
[17, 2, 3, 6, 1, 3, 1, 9, 5] 3

Как мы видим, reduce передает накопленный список в качестве первого аргумента, а новый элемент - в качестве второго аргумента. （Если reduce все еще поражает вас, Как уменьшить работу? содержит несколько хороших объяснений.)

Наша конкретная лямбда вставляет новый элемент в аккумулятор на каждой "итерации". Это намекает на вставку сортировки:

def insert(xs, n):
    """
    Finds first element in `xs` greater than `n` and returns an inserted element.
    `xs` is assumed to be a sorted list.
    """
    for i, x in enumerate(xs):
        if x > n:
            return xs[:i] + [n] + xs[i:]

    return xs + [n]

sorted_arr = reduce(insert, arr, [])
print(sorted_arr)

Это печатает правильно отсортированный массив:

[1, 1, 2, 3, 3, 3, 5, 6, 9, 17]

^{Обратите внимание, что третий параметр reduce (т.е. []) был указан, когда мы инициализируем сортировка должна с пустым списком.}

Answer 3

Подумав, я пришел к выводу, что можно также выполнить сортировку на основе свопов, если вам разрешено использовать reduce более одного раза. А именно:

from functools import reduce
arr = [17, 2, 3, 6, 1, 3, 1, 9, 5, 3]
def func(acc,x):
    if not acc:
        return [x]
    if acc[-1]<x:
        return acc+[x]
    else:
        return acc[:-1]+[x]+acc[-1:]

def my_sort(x):
    moresorted = reduce(func,x,[])
    print(moresorted)
    if x==moresorted:
        return moresorted
    else:
        return my_sort(moresorted)

print('arr:',arr)
arr_sorted = my_sort(arr)
print('arr sorted:',arr_sorted)

Выход:

arr: [17, 2, 3, 6, 1, 3, 1, 9, 5, 3]
[2, 3, 6, 1, 3, 1, 9, 5, 3, 17]
[2, 3, 1, 3, 1, 6, 5, 3, 9, 17]
[2, 1, 3, 1, 3, 5, 3, 6, 9, 17]
[1, 2, 1, 3, 3, 3, 5, 6, 9, 17]
[1, 1, 2, 3, 3, 3, 5, 6, 9, 17]
[1, 1, 2, 3, 3, 3, 5, 6, 9, 17]
arr sorted: [1, 1, 2, 3, 3, 3, 5, 6, 9, 17]

Я поместил print(moresorted) внутри func для образовательных целей, вы можете удалить его, если хотите.

Теперь объяснение: my_sort - рекурсивная функция, с каждым прогоном ее список становится все более и более отсортированным. func, который используется как функция в reduce, добавляет новый элемент и затем меняет 2 последних элемента списка, если они не в порядке возрастания. Это означает, что при каждом прогоне my_sort число «путешествует» вправо до тех пор, пока не произойдет, где следующее число будет больше. if not acc требуется для запуска - обратите внимание, что третий аргумент reduce равен [], что означает, что во время первого выполнения func в каждом reduce первый аргумент для func равен [], поэтому спрашиваете acc[-1]<x? приведет к ошибке.

Answer 4

Ninjad!Но да, это сортировка вставки.

def insert(acc, e):
    for i, x in enumerate(acc):
        if x > e:
            acc.insert(i, e)
            return acc
    acc.append(e)
    return acc

reduce(insert, [1, 2, 6, 4, 7, 3, 0, -1], [])

вывод

[-1, 0, 1, 2, 3, 4, 6, 7]