Перечислите все перестановки чисел 1, ..., n в лексикографическом порядке - PullRequest
Новая
       8

Перечислите все перестановки чисел 1, ..., n в лексикографическом порядке

2 голосов
/ 15 марта 2009

Я пытаюсь запрограммировать Matlab для перечисления всех перестановок чисел от 1 до n в лексикографическом порядке. То, что я пока имею, ниже. Я использую рекурсию, чтобы попытаться написать программу, которая сначала будет работать для n = 3, а затем посмотреть, смогу ли я получить представление о написании программы для любого n. Пока у меня есть 2 из 6 столбцов для n = 3: P=[1 2 3;1 3 2]. Мне нужны следующие две колонки, чтобы просто поменять местами две и две. Я не знаю, как начать это делать. 

function [P] = shoes(n)

if n == 1
    P = 1;
elseif n == 2
    P = [1 2; 2 1];
else 
    T = shoes(n-1) + 1;
    G = ones(factorial(n-1),1);
    P(1:2,1:3) = [G T];               
end

Ответы [ 2 ]

2 голосов
/ 15 марта 2009

См. документацию для начала. Если под лексикографическим порядком вы подразумеваете алфавитное имя по-английски, вы можете заполнить введенные данные именами, отсортировать их, а затем переставить.

Если я неправильно понял, что вы хотите, прокомментируйте или отредактируйте вопрос, и я проверю позже.

Советы:

  • Перестановки пустого списка легко найти.
  • Индукция является важной концепцией в математике. Вы должны быть знакомы с этим.
  • Среда, в которой вы работаете, поддерживает рекурсию
  • Перестановки из более длинного списка могут быть произведены в порядке, который вы хотите, путем рекурсии; сначала выясните, каким должен быть первый элемент, а затем выясните остальное.

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

Подсказки после просмотра вашего кода.

  • Ваша основная функция переставляет вектор и поэтому должна принимать вектор в качестве аргумента, а не целое число
  • Не начинайте решать дело n = 3; попробуйте случай n = 0 (это []), а затем перейдите прямо к случаю n = 20.
  • Подумайте о случае n = 20, прежде чем писать какой-либо код. Как будет выглядеть первая колонка? Есть ли примеры случая n = 19, скрытого в ответе на случай n = 20? (Ответ - да, и все они разные).
  • Перечитайте первый набор подсказок
1 голос
/ 15 марта 2009

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

Если у вас есть следующая матрица: 

A = [1 2 3; 1 3 2];

и вы хотите, чтобы все стали по двое, а двое - по одному, самый простой способ сделать это будет следующим: 

B = A;
B(A == 1) = 2;
B(A == 2) = 1;
...