@tumur4

Как сгенерировать размещение по его номеру в лексикографическом порядке?

Имеем: n = колво эл-ов в перестановке, К = колво эл-ов в размещении, и m = номер размещения. m номер размещения из N по M
  • Вопрос задан
  • 88 просмотров
Решения вопроса 1
hint000
@hint000
у админа три руки
1. Организуем список из N элементов по возрастанию;
2. Генерировать будем рекурсивно (это для простоты объяснения, после усвоения идеи можно обойтись циклом);
2.1. Если M==0, то выход из рекурсии;
2.2. Первый элемент размещения - это элемент, находящийся на L-ом месте в списке, где L=((N*m-1)\A(N,M))+1 (нумерация с единицы только для ясности); A(N,M)=число размещений из N по M; удаляем из списка выбранный элемент;
2.3. Для следующего шага рекурсии берём m=m-(L-1)*A(N,M)/N; N=N-1; M=M-1;
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы