Мобильная версия форумов
Открыть
 −14°C
завтра: −15°C
Погода в Перми
−14°C
вечером−14°C
ночью−16°C
завтра−15°C
Подробно
 66,25
−0.4574
Курс USD ЦБ РФна 19 февраля
66,2470
−0.4574
 74,91
−0.3437
Курс EUR ЦБ РФна 19 февраля
74,9055
−0.3437
PRM.Форум /Компьютеры Интернет Связь / Программирование /

Люди помогите с алгоритмом перебора

  • activist

    Сообщений: 248

    Люди помогите с алгоритмом перебора символов в строке.
    Требуется из строки допустим "АБС" получить список строк следующего вида:
    АБС
    АСБ
    БАС
    БСА
    САБ
    СБА
    Число строк результата зависит от длины первой строки, т.е. если длина N, то результат из N! строк.
    Набор символов в строке изначально задан и не меняется.

    http://link.ac/37Vl9

  • Cactus

    Анонимный пользователь

    Тебе надо что-то оптимизированное или любой?

    Первое что приходит в голову - рекурсия с двумя массивами: уже составленной строкой и еще не использованными символами.

    Функция перебирает в цикле все оставшиеся символы, на каждой итерации создает копию текущей строки, добавляет к ней i-ый символ из доступных, создает копию доступных символов без i-го. Передает полученные два массива далее по рекурсии. Так пока еще остались неиспользованые символы. Глубина рекурсии = N, количество комбинаций = N!.

    Естественно, если в строке будут повторяющиеся символы, то будут и повторяющиеся комбинации в результирующем наборе.

  • Анонимный пользователь
    программа на C++:

    #include
    #include
    #include

    void main()
    {
    using namespace std;
    string s = "ABC";
    cout

  • Анонимный пользователь
    Как вариант можно было использовать алгоритм Дейкстры для нахождения перестановок...

  • Анонимный пользователь
    случайно наткнулся на этот пост...
    человек просто алгоритм спросил, а результат - лучше сразу бы нафуй послали...
    парами надо менять - сначала 1 и 2, потом 2 и 3, и пока на первой позиции не окажется снова A
    abc (a и b)
    bac (a c)
    bca (снова b и c)
    ...
    пока не acb

  • activist

    Сообщений: 248

    А это и есть мысль, хотя, а если есть повторяющиеся символы?
    Ну в принципе если их нет, то делаем пока не верьнемся к первой позиции, а если есть повторения, то надо наверное делать факториал от длины первоначального массива.

    http://link.ac/37Vl9

  • Анонимный пользователь
    В ответ на: А это и есть мысль, хотя, а если есть повторяющиеся символы?
    Ну в принципе если их нет, то делаем пока не верьнемся к первой позиции, а если есть повторения, то надо наверное делать факториал от длины первоначального массива.
    Ясно-понятно. Вот только при повторяющихся символах нужно будет потом выкинуть будет одинаковые комбинации...

  • Cactus

    Анонимный пользователь

    А не проще сначала убрать повторяющиеся символы?

  • experienced

    Сообщений: 637

    Задача то стоит получить различные перестановки заданной длины 8). Поэтому убрав повторяющиеся символы мы получим перестановки меньшей длины.

    Скромность украшает мужчину. Но настоящий мужчина в украшениях не нуждается.

Записей на странице:

Перейти в форум

Модератор: