Люди помогите с алгоритмом перебора
2611
8
Люди помогите с алгоритмом перебора символов в строке.
Требуется из строки допустим "АБС" получить список строк следующего вида:
АБС
АСБ
БАС
БСА
САБ
СБА
Число строк результата зависит от длины первой строки, т.е. если длина N, то результат из N! строк.
Набор символов в строке изначально задан и не меняется.
Требуется из строки допустим "АБС" получить список строк следующего вида:
АБС
АСБ
БАС
БСА
САБ
СБА
Число строк результата зависит от длины первой строки, т.е. если длина N, то результат из N! строк.
Набор символов в строке изначально задан и не меняется.
Тебе надо что-то оптимизированное или любой?
Первое что приходит в голову - рекурсия с двумя массивами: уже составленной строкой и еще не использованными символами.
Функция перебирает в цикле все оставшиеся символы, на каждой итерации создает копию текущей строки, добавляет к ней i-ый символ из доступных, создает копию доступных символов без i-го. Передает полученные два массива далее по рекурсии. Так пока еще остались неиспользованые символы. Глубина рекурсии = N, количество комбинаций = N!.
Естественно, если в строке будут повторяющиеся символы, то будут и повторяющиеся комбинации в результирующем наборе.
Первое что приходит в голову - рекурсия с двумя массивами: уже составленной строкой и еще не использованными символами.
Функция перебирает в цикле все оставшиеся символы, на каждой итерации создает копию текущей строки, добавляет к ней i-ый символ из доступных, создает копию доступных символов без i-го. Передает полученные два массива далее по рекурсии. Так пока еще остались неиспользованые символы. Глубина рекурсии = N, количество комбинаций = N!.
Естественно, если в строке будут повторяющиеся символы, то будут и повторяющиеся комбинации в результирующем наборе.
программа на C++:
#include
#include
#include
void main()
{
using namespace std;
string s = "ABC";
cout
#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
человек просто алгоритм спросил, а результат - лучше сразу бы нафуй послали...
парами надо менять - сначала 1 и 2, потом 2 и 3, и пока на первой позиции не окажется снова A
abc (a и b)
bac (a c)
bca (снова b и c)
...
пока не acb
mages
activist
А это и есть мысль, хотя, а если есть повторяющиеся символы?
Ну в принципе если их нет, то делаем пока не верьнемся к первой позиции, а если есть повторения, то надо наверное делать факториал от длины первоначального массива.
Ну в принципе если их нет, то делаем пока не верьнемся к первой позиции, а если есть повторения, то надо наверное делать факториал от длины первоначального массива.
А это и есть мысль, хотя, а если есть повторяющиеся символы?Ясно-понятно. Вот только при повторяющихся символах нужно будет потом выкинуть будет одинаковые комбинации...
Ну в принципе если их нет, то делаем пока не верьнемся к первой позиции, а если есть повторения, то надо наверное делать факториал от длины первоначального массива.
Сейчас читают
Брелок сигнализации работает, но на дисплее ничего нет
38731
28
Обмен/продажа абонементов в спортивные клубы
220660
228
ОКНА: дерево иди пластик????
3257
37
Задача то стоит получить различные перестановки заданной длины 8). Поэтому убрав повторяющиеся символы мы получим перестановки меньшей длины.
ТОП 5
2
4