21°C
завтра: 24°C
Погода в Перми
21°C
вечером25°C
ночью16°C
завтра24°C
Подробно
 63,13
+0.1514
Курс USD ЦБ РФна 24 июля
63,1290
+0.1514
 70,64
−0.0196
Курс EUR ЦБ РФна 24 июля
70,6350
−0.0196
PRM.Форум /Компьютеры Интернет Связь / Программирование /

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

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

    http://link.ac/37Vl9

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

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

    Функция перебирает в цикле все оставшиеся символы, на каждой итерации создает копию текущей строки, добавляет к ней 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

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

    http://link.ac/37Vl9

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

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

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

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

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

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

Модератор: