Алгоритм поиска всех перестановок числа

Question

Мне нужно написать программу, которая дает все перестановки числа. Например, пользователь вводит номер 4. Мне нужно вернуть все возможные комбинации чисел 1,2,3,4. У меня проблема с хорошим методом для получения всех перестановок. У меня это так, поэтому моя программа помещает число 1-n в массив. Тем не менее, я не могу придумать хороший способ получить перестановку. Я знаю, что мне нужно использовать рекурсию, но моя проблема - это способ получить перестановки в первую очередь. Я знаю, что переключение числа вокруг - это, пожалуй, лучший способ, но каков наилучший способ для этого?

Answer 1

Самый простой способ понять алгоритм - это. Для того, чтобы получить все перестановки 1 до 4, вы хотите

• 1, а затем перестановки 2,3,4
• 2, а затем перестановки 1,3,4
• 3, с последующими перестановками 1,2,4
• 4, а затем перестановками 1,2,3

это довольно стандартный бит рекурсии. Для каждого числа рекурсивно найдите все перестановки других чисел и добавьте это число в начале.

Answer 2

Мы можем просто использовать recursion, чтобы получить возможности путем рекурсивного выбора одного элемента, а затем применения рекурсии к подмножеству этого массива. это пример для чисел от 1 до 3

Answer 3

Рекурсия является вашим другом. Если у вас есть один элемент, ваше решение очевидно [[1]]. Для двух элементов вы можете взять все свои «одни» -решения (ну, есть только одно) и придерживать 2 до или после 1, так что вы получите [[2,1], [1,2]]. Для трех элементов возьмите все ваши «два» решения и поместите их в первую, вторую или третью позицию. Из [2,1] вы получаете [3,2,1], [2,3,1] и [2,1,3]. Из [1,2] вы получаете [3,1,2], [1,3,2] и [1,2,3]. Все вместе, ваше решение - [[3,2,1], [2,3,1], [2,1,3], [3,1,2], [1,3,2], [1, 2,3]].

Answer 4

Обратите внимание, как chiastic-security's algorithm для генерации всех перестановок n чисел зависит от возможности генерации всех перестановок n-1 чисел? Чтобы использовать его алгоритм, все, что нам нужно, это способность и еще одна вещь: способ генерации всех перестановок набора, содержащего только одно число.

Создание всех перестановок одного числа тривиально: есть только один, состоящий только из этого числа.

Как насчет другого требования - возможность генерации всех перестановок чисел n-1? Это кажется сложнее, но этого оказалось не так. Предположим, что n = 2 для задачи, которую мы хотим решить: тогда n-1 = 1, и тогда мы в порядке, потому что знаем, как сгенерировать все перестановки из 1 числа. Таким образом, применение алгоритма хиастической безопасности дает нам способ генерации всех перестановок из 2 чисел. Если вместо n = 3 для задачи мы хотим решить, тогда n-1 = 2, и мы только что установили, что можем сгенерировать все перестановки из 2 чисел, поэтому мы все еще в порядке - мы знаем, как сгенерировать все перестановки 3-х чисел. Если вместо n = 4, то n-3 = 3, и мы только что установили, что можем сгенерировать все перестановки из 3 чисел, поэтому мы можем также сгенерировать все перестановки из 4 чисел. Ясно, что это рассуждение может продолжаться вечно - так что вы можете генерировать все перестановки любого числа чисел таким образом.

Это рассуждение является неофициальным, но его можно сделать полностью точным с помощью mathematical induction.Если индукция может быть применена, то удивительным результатом является то, что нам никогда не приходится решать любые «большие» проблемы «трудным путем» - мы всегда можем разбить их на одну или несколько мелких проблем, которые, в свою очередь, могут быть разбиты меньших проблем, до тех пор, пока не будет достигнут один или несколько «базовых случаев», которые легко решить, а затем решения более крупных проблем могут быть собраны вместе из этих решений в более простые подзадачи.