3

С помощью какого алгоритма можно перебрать все n! возможные варианты перестановок цифр заданного числа?

P.S. Под перестановками подразумевается полное множество размещений без повторений при n = k , где

  • n - размер набора символов;
  • k - число позиций, в которых происходят перестановки символов.
6
  • каких еще перестановок?
    – DreamChild
    3 окт 2013 в 18:48
  • Был недавно почти такой же вопрос, только про буквы ABCDE -> AB AC AD AE ABC ABD ... IMHO автор по этому поводу спрашивал, как узнать, какие биты в числе установлены. Вот нашел (там даже есть 2 программки).
    – avp
    3 окт 2013 в 18:59
  • 1
    как-то не очень хочется гадать. Тем более, скорее всего это очередной хреновый студент со своей лабораторной
    – DreamChild
    3 окт 2013 в 19:02
  • 1
    @bananya, Согласно правилам форума, вопросы не должны сводиться к решению либо завершению учебных заданий за учащихся. Пожалуйста, уточните, что вы сделали сами и что не получилось.
    – ReinRaus
    3 окт 2013 в 19:08
  • 2
    @dzhioev: не всё так просто: цифры могут повторяться, и содержать нули (которым нельзя попадать на первое место). Например, случай числа 1122, перестановки (1<->3)(2<->4) и (1<->4)(2<->3) дают 2211. То есть придётся запоминать все промежуточные результаты, что есть не айс.
    – VladD
    3 окт 2013 в 19:37

2 ответа 2

2

Да это можно посчитать и без перебора.

Имея алфавит ABCDE получаем 5^1+5^2+5^3+5^4+5^5 5^1 - A-Z 5^2 - AA - EE и т.д. т.е. размер алфавита в степени равной количеству символов

1
  • 3
    Угу, а теперь учтите, что нули не могут находиться на начальной позиции, а также повторяющиеся цифры, которые не дают нового варианта, если их переставить.
    – VladD
    6 окт 2013 в 11:35
1

Тасование Фишера–Йетса

Цитата: "Современная версия алгоритма очень эффективна и требует время, пропорциональное числу элементов множества, и не требует дополнительного пространства."

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.