Нахождение всех перестановок списка, когда дана функция, которая возвращает следующую перестановку списка - PullRequest
Новая
       15

Нахождение всех перестановок списка, когда дана функция, которая возвращает следующую перестановку списка

0 голосов
/ 25 февраля 2019

В моем задании на этой неделе меня попросили написать скрипт на python, который принимает число n и возвращает все перестановки [0,1,2, ..., n-1].До сих пор я написал скрипт, который принимает список и возвращает следующую перестановку списка.Я ищу идеи о том, как я могу написать сценарий на основе того, что я написал до сих пор.

def next_permutation(p):
    a = len(p)
    i = a -2 
    while i >= 0 and p[i] >= p[i+1]:
        i = i-1
    if i == -1:
        return []

    j = i+1
    while j < a and p[j] >= p[i]:
        j += 1
    j-=1

    p[i], p[j] = p[j], p[i]

    k = i + 1
    l = a - 1

    while k < l:
        p[k], p[l] = p[l], p[k]
        k += 1
        l -= 1
    return p

РЕДАКТИРОВАТЬ: это код, который возвращает следующую перестановку списка.Я написал это полностью на основе инструкций, предоставленных моим инструктором.

1 Ответ

0 голосов
/ 25 февраля 2019

Поскольку вы хотите иметь все перестановки в списке с номерами от 0 до n-1, у вас уже есть четкие шаги, которые необходимо предпринять:

  1. Создать список, содержащий все числаот 0 до n-1:

Это легко сделать с помощью встроенной функции range(), поскольку она в основном используется именно для этой цели:

диапазон (стоп)

Это универсальная функция для создания итераций, дающая арифметические прогрессии.

Вычислите количество перестановок, которые будет иметь такой список:

Математика говорит нам, что, имея N элементов, будет N!различные сочетания этих элементов, где ! означает факториал.Мы можем импортировать факториальную функцию из математического модуля, которая быстро позволит нам вычислить количество перестановок, которые будут иметь ваш список: 

from math import factorial
print(factorial(4)) # 24
Вызовите свою функцию next_permutation(p), которую вы уже много раз написали, и получите каждую и каждую перестановку.

To вернуть что-то более одного раза из функции, вы можетеиспользуйте yield insted.

Имея в виду эти шаги, вы можете создать нечто похожее на это: 

def all_permutations(n):

    # Constructing a list that contains all numbers from 0 to n-1
    integer_list = list(range(n))

    # Calculating the amount of permutations such list would have
    permutation_count = factorial(n)

    # Output that many permutations
    for _ in range(permutation_count):
        yield integer_list
        integer_list = next_permutation(integer_list)

Эта функция генератора выдаст все перестановки списка, содержащегочисла от 0 до n-1, это именно то, что вам нужно.

Чтобы создать список, который будет содержать все перестановки, вы можете написать что-то простое, например: 

n = 4
all_permutations = list(all_permutations(n))
...