Блог

Главная - Вопросы по программированию - Как мне найти следующую перестановку списка

Как мне найти следующую перестановку списка

#python #python-3.x

#python #python-3.x

Вопрос:

Если мне предоставлен список чисел от 1 до N, как мне найти следующую перестановку данного списка?

Например:

 lst = [2, 1, 4, 3]

следующая перестановка будет

 [2, 3, 1, 4]

Что я сделал, так это использовал intertools

 import itertools
lst2 = list(itertools.permutations([1, 2, 3, 4]))

затем найдите индекс данного списка и верните 1 этому индексу

Однако есть ли другой способ сделать это без использования intertools? Я думал, что есть шаблон того, как эти списки расположены в порядке возрастания.

Комментарии:

1. Перестановки являются случайными, если вы не определяете правило, по которому позиционируется любой новый элемент последовательности, поэтому next с точки зрения легитимности его нет.

2. Как вы думаете, почему [2, 3, 1, 4] следующая после [2, 1, 4, 3] ?

3. Предполагая, что перестановки генерируются алгоритмом perm , вы всегда можете просто сделать что-то вроде next(islice(perm([2, 1, 4, 3]), 1, 2)) получения следующей перестановки в последовательности перестановок, которая perm будет генерироваться достаточно эффективно. Предположение здесь заключается в том, что perm выдает итератор. Другой вариант — просто перетасовать список.

4. Я хочу, чтобы они были в порядке последовательности intertools.permutations. Например: перестановка (1,2,3) будет указана в этом порядке: [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)] . итак, если мне дано (2, 3, 1), я должен иметь возможность вернуть (3, 2, 1)

5. Проблема называется «следующая лексикографическая перестановка», для нее существует простой алгоритм, который можно найти путем поиска.