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

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

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

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

#include
#include
#include

void main()
{
using namespace std;
string s = "ABC";
cout
mages
Как вариант можно было использовать алгоритм Дейкстры для нахождения перестановок...
mages
случайно наткнулся на этот пост...
человек просто алгоритм спросил, а результат - лучше сразу бы нафуй послали...
парами надо менять - сначала 1 и 2, потом 2 и 3, и пока на первой позиции не окажется снова A
abc (a и b)
bac (a c)
bca (снова b и c)
...
пока не acb
А это и есть мысль, хотя, а если есть повторяющиеся символы?
Ну в принципе если их нет, то делаем пока не верьнемся к первой позиции, а если есть повторения, то надо наверное делать факториал от длины первоначального массива.
mages
А это и есть мысль, хотя, а если есть повторяющиеся символы?
Ну в принципе если их нет, то делаем пока не верьнемся к первой позиции, а если есть повторения, то надо наверное делать факториал от длины первоначального массива.
Ясно-понятно. Вот только при повторяющихся символах нужно будет потом выкинуть будет одинаковые комбинации...
А не проще сначала убрать повторяющиеся символы?
Cactus
Задача то стоит получить различные перестановки заданной длины 8). Поэтому убрав повторяющиеся символы мы получим перестановки меньшей длины.