PRM.Форум /Компьютеры Интернет Связь / Программирование /

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

Печать RSS Деревом

mages
activist
Сообщений: 248
24.05.03 09:28
Люди помогите с алгоритмом перебора символов в строке.
Требуется из строки допустим "АБС" получить список строк следующего вида:
АБС
АСБ
БАС
БСА
САБ
СБА
Число строк результата зависит от длины первой строки, т.е. если длина N, то результат из N! строк.
Набор символов в строке изначально задан и не меняется.
http://link.ac/37Vl9
КопироватьСсылка
Рассказать друзьям
Cactus
Анонимный пользователь
24.05.03 22:28Ответ на сообщение Люди помогите с алгоритмом перебора пользователя mages
Тебе надо что-то оптимизированное или любой?

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

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

Естественно, если в строке будут повторяющиеся символы, то будут и повторяющиеся комбинации в результирующем наборе.
КопироватьСсылка
Рассказать друзьям
Анонимный пользователь
26.05.03 08:11Ответ на сообщение Люди помогите с алгоритмом перебора пользователя mages
программа на C++:

#include
#include
#include

void main()
{
using namespace std;
string s = "ABC";
cout
КопироватьСсылка
Рассказать друзьям
Анонимный пользователь
27.08.03 09:05Ответ на сообщение Люди помогите с алгоритмом перебора пользователя mages
Как вариант можно было использовать алгоритм Дейкстры для нахождения перестановок...
КопироватьСсылка
Рассказать друзьям
Анонимный пользователь
18.09.03 23:28Ответ на сообщение Люди помогите с алгоритмом перебора пользователя mages
случайно наткнулся на этот пост...
человек просто алгоритм спросил, а результат - лучше сразу бы нафуй послали...
парами надо менять - сначала 1 и 2, потом 2 и 3, и пока на первой позиции не окажется снова A
abc (a и b)
bac (a c)
bca (снова b и c)
...
пока не acb
КопироватьСсылка
Рассказать друзьям
mages
activist
Сообщений: 248
19.09.03 12:38Ответ на сообщение Re: Люди помогите с алгоритмом перебора пользователя Анонимный пользователь
А это и есть мысль, хотя, а если есть повторяющиеся символы?
Ну в принципе если их нет, то делаем пока не верьнемся к первой позиции, а если есть повторения, то надо наверное делать факториал от длины первоначального массива.
http://link.ac/37Vl9
КопироватьСсылка
Рассказать друзьям
Анонимный пользователь
22.09.03 12:36Ответ на сообщение Re: Люди помогите с алгоритмом перебора пользователя mages
В ответ на: А это и есть мысль, хотя, а если есть повторяющиеся символы?
Ну в принципе если их нет, то делаем пока не верьнемся к первой позиции, а если есть повторения, то надо наверное делать факториал от длины первоначального массива.
Ясно-понятно. Вот только при повторяющихся символах нужно будет потом выкинуть будет одинаковые комбинации...
КопироватьСсылка
Рассказать друзьям
Cactus
Анонимный пользователь
23.09.03 00:09Ответ на сообщение Re: Люди помогите с алгоритмом перебора пользователя Анонимный пользователь
А не проще сначала убрать повторяющиеся символы?
КопироватьСсылка
Рассказать друзьям
Неместный
experienced
Сообщений: 637
23.09.03 08:57Ответ на сообщение Re: Люди помогите с алгоритмом перебора пользователя Cactus
Задача то стоит получить различные перестановки заданной длины 8). Поэтому убрав повторяющиеся символы мы получим перестановки меньшей длины.
Скромность украшает мужчину. Но настоящий мужчина в украшениях не нуждается.
КопироватьСсылка
Рассказать друзьям

PRM.Форум /Компьютеры Интернет Связь / Программирование /

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

открыть в новом окне

Модератор:

flopic