//---------------------------------------------------------------------------
AnsiString SetWord(AnsiString str,int i,int j)
{
AnsiString res = str;
char tmp = res[j];
res[j] = res;
res = tmp;
return res;
}
AnsiString NewWord(AnsiString str,int i)
{
AnsiString res = str;
char tmp = res;
res = res[1];
res[1] = tmp;
return res;
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{
AnsiString begStr = Edit1->Text;
AnsiString resStr;
for(int i=0;i<begStr.Length();i++)
{
for(int j=0;j<begStr.Length();j++)
{
resStr = SetWord(begStr,i+1,j+1);
Memo1->Lines->Add(resStr);
}
begStr = NewWord(begStr,i+1);
}
}
//---------------------------------------------------------------------------
Алгоритм.Строка.
Блин немогу составить алгоритм. Готовый код ненадо.
Задание:
Для заданного с клавиатуры слова построить все его анаграммы, т.е. слова (возможно бессмысленные), состоящие из всех букв исходного слова, но расположенных в произвольном порядке.
Докатился блин. :( :( :(
Задание:
Для заданного с клавиатуры слова построить все его анаграммы, т.е. слова (возможно бессмысленные), состоящие из всех букв исходного слова, но расположенных в произвольном порядке.
Докатился блин. :( :( :(
Цитата:
Originally posted by Тимофей
Блин немогу составить алгоритм. Готовый код ненадо.
Задание:
Для заданного с клавиатуры слова построить все его анаграммы, т.е. слова (возможно бессмысленные), состоящие из всех букв исходного слова, но расположенных в произвольном порядке.
Докатился блин. :( :( :(
Блин немогу составить алгоритм. Готовый код ненадо.
Задание:
Для заданного с клавиатуры слова построить все его анаграммы, т.е. слова (возможно бессмысленные), состоящие из всех букв исходного слова, но расположенных в произвольном порядке.
Докатился блин. :( :( :(
Алгоритм типа пузырька:
Первый символ двигаешь по строке (на 2 место, 3 и т.д.)
Берешь исходную строку и второй двигаешь.
Потом третий и т.д.
Исключай только повторения.
Цитата:
Originally posted by AlexandrVSmirno
Алгоритм типа пузырька:
Первый символ двигаешь по строке (на 2 место, 3 и т.д.)
Берешь исходную строку и второй двигаешь.
Потом третий и т.д.
Исключай только повторения.
Алгоритм типа пузырька:
Первый символ двигаешь по строке (на 2 место, 3 и т.д.)
Берешь исходную строку и второй двигаешь.
Потом третий и т.д.
Исключай только повторения.
Ёпрст. Точно. Мучо грасьяс. Блин бывает же, упрешся рогом, когда все просто. Ещё раз грасьяс.
Поторопился немного. Такой подход охватывает не всё множество значений. Т.е.
У нас получится, если строка ABCD:
ABCD-BACD-BCAD-BCDA
....
DABC-ADBC...
А как быть с DBCA,BADC...? Т.е. пузырек двигается по слову а другие символы место не меняют
У нас получится, если строка ABCD:
ABCD-BACD-BCAD-BCDA
....
DABC-ADBC...
А как быть с DBCA,BADC...? Т.е. пузырек двигается по слову а другие символы место не меняют
Нужно определить массив напр.
int ndx[4] = {0,1,2,3};
Сгенерировать все перестановки
На каждом шаге, построить слово, согласно массиву.
Напр. введено ABCD
ndx, на каком-то шаге = {3,0,2,1}, получаем DACB
int ndx[4] = {0,1,2,3};
Сгенерировать все перестановки
На каждом шаге, построить слово, согласно массиву.
Напр. введено ABCD
ndx, на каком-то шаге = {3,0,2,1}, получаем DACB
Цитата:
Originally posted by rostyslav
Нужно определить массив напр.
int ndx[4] = {0,1,2,3};
Сгенерировать все перестановки
Нужно определить массив напр.
int ndx[4] = {0,1,2,3};
Сгенерировать все перестановки
Но мы же опять пришли к началу. Как реализовать генератор перестановки?
Цитата:
Originally posted by Тимофей
Но мы же опять пришли к началу. Как реализовать генератор перестановки?
Но мы же опять пришли к началу. Как реализовать генератор перестановки?
Ты же писал, что тебе код не нужен...
Цитата:
Originally posted by rostyslav
Ты же писал, что тебе код не нужен...
Ты же писал, что тебе код не нужен...
Нет ненужен. Я немогу сообразить как сгенерировать массив уникальных значений, неважно int или char. Ты ведь просто предложил не строку генерировать а int массив, вобщем то это одно и тоже, разве не так? Помню в институте раньше море таких прог переписал, давно это было....
Цитата:
Originally posted by rostyslav
Предполагается, что на форме есть компонент TMemo, по имени Memo1.
Предполагается, что на форме есть компонент TMemo, по имени Memo1.
Я похоже плохо изложил. Вот мой вариант
Код:
ЗЫ: Только на совпадающие строки забыл проверить
Цитата:
Originally posted by AlexandrVSmirno
Я похоже плохо изложил. Вот мой вариант
ЗЫ: Только на совпадающие строки забыл проверить
Я похоже плохо изложил. Вот мой вариант
Код:
//---------------------------------------------------------------------------
AnsiString SetWord(AnsiString str,int i,int j)
...
-----------------------------------------------------------------
AnsiString SetWord(AnsiString str,int i,int j)
...
-----------------------------------------------------------------
ЗЫ: Только на совпадающие строки забыл проверить
Можно поменять TMemo на TListbox c Sorted = true, и добавлять слово командой
if(Listbox1->Items->IndexOf(resStr)<0)Listbox1->Items->Add(resStr);
Но если begStr первоначально равно "ABCD", тогда напр. "ABDC" не генерируется.
Цитата:
Originally posted by rostyslav
Можно поменять TMemo на TListbox c Sorted = true, и добавлять слово командой
if(Listbox1->Items->IndexOf(resStr)<0)Listbox1->Items->Add(resStr);
Но если begStr первоначально равно "ABCD", тогда напр. "ABDC" не генерируется.
Можно поменять TMemo на TListbox c Sorted = true, и добавлять слово командой
if(Listbox1->Items->IndexOf(resStr)<0)Listbox1->Items->Add(resStr);
Но если begStr первоначально равно "ABCD", тогда напр. "ABDC" не генерируется.
Понял. Доработал.
Код:
void __fastcall TForm1::Button1Click(TObject *Sender)
{
AnsiString begStr = Edit1->Text;
AnsiString resStr;
for(int l = 0;l<begStr.Length();l++)
{
for(int i=0;i<begStr.Length();i++)
{
for(int j=0;j<begStr.Length();j++)
{
resStr = SetWord(begStr,i+1,j+1);
if(Memo1->Lines->Text.Pos(resStr) == 0)
Memo1->Lines->Add(resStr);
}
begStr = SetWord(begStr,i+1,l+1);
}
begStr = NewWord(begStr,l+1);
}
}
{
AnsiString begStr = Edit1->Text;
AnsiString resStr;
for(int l = 0;l<begStr.Length();l++)
{
for(int i=0;i<begStr.Length();i++)
{
for(int j=0;j<begStr.Length();j++)
{
resStr = SetWord(begStr,i+1,j+1);
if(Memo1->Lines->Text.Pos(resStr) == 0)
Memo1->Lines->Add(resStr);
}
begStr = SetWord(begStr,i+1,l+1);
}
begStr = NewWord(begStr,l+1);
}
}
Цитата:
Originally posted by AlexandrVSmirno
Понял. Доработал.
Понял. Доработал.
Код:
...
Не генерируется при "ABCD" слово BDCA и CDAB. Число всевозможных перестановок из n чисел равно n!(n-факториал).
Могу ошибиться, (как на параллельной ветке :)) но не верится, что с таким способом можно сгенерировать все перестановки.
Цитата:
Originally posted by rostyslav
Не генерируется при "ABCD" слово BDCA и CDAB. Число всевозможных перестановок из n чисел равно n!(n-факториал).
Могу ошибиться, (как на параллельной ветке :)) но не верится, что с таким способом можно сгенерировать все перестановки.
Не генерируется при "ABCD" слово BDCA и CDAB. Число всевозможных перестановок из n чисел равно n!(n-факториал).
Могу ошибиться, (как на параллельной ветке :)) но не верится, что с таким способом можно сгенерировать все перестановки.
Здесь перестановки с повторениями. И нужна рекурсия. Так для слов из четырех букв достаточно четырех циклов. Для слов из пяти необходимо пять и т.д.
Цитата:
Originally posted by AlexandrVSmirno
Здесь перестановки с повторениями. И нужна рекурсия. Так для слов из четырех букв достаточно четырех циклов. Для слов из пяти необходимо пять и т.д.
Здесь перестановки с повторениями. И нужна рекурсия. Так для слов из четырех букв достаточно четырех циклов. Для слов из пяти необходимо пять и т.д.
Можно и без рекурсии. Я (наверно) мог бы построить перестановки в последовательности
1234
2134
1324
3124
1324
3124
1243
...
Но алгоритм был бы, почти такой неэффективный, как ваш. Вместо этого алгоритм Джонса-Троттера (в моей реализации :))
Код:
#include <algorithm>
#define N 4
String wrd = "ABCD";
void __fastcall TForm1::Button6Click(TObject *Sender)
{
Memo1->Clear();
String res;
bool flag[N+1];
int ndx[N+1], pos[N+1];
int i, j, step;
for(i=1;i<=N;i++)
{
ndx = i;
flag = true;
pos = 1;
}
res = "";
for(j=1;j<=N;j++)res= res + wrd[ndx[j]];
Memo1->Lines->Add(res);
pos[N] = 0;
i = 1;
while(i<N)
{
i = 1;
step = 0;
while(pos==N-i+1)
{
flag=!flag;
pos=1;
if(flag)step++;
i++;
}
if(i<N)
{
if(flag)
j = pos+step;
else
j = N-i+1-pos+step;
std::swap(ndx[j],ndx[j+1]);
res = "";
for(j=1;j<=N;j++)res=res+wrd[ndx[j]];
Memo1->Lines->Add(res);
pos++;
}
}
}
#define N 4
String wrd = "ABCD";
void __fastcall TForm1::Button6Click(TObject *Sender)
{
Memo1->Clear();
String res;
bool flag[N+1];
int ndx[N+1], pos[N+1];
int i, j, step;
for(i=1;i<=N;i++)
{
ndx = i;
flag = true;
pos = 1;
}
res = "";
for(j=1;j<=N;j++)res= res + wrd[ndx[j]];
Memo1->Lines->Add(res);
pos[N] = 0;
i = 1;
while(i<N)
{
i = 1;
step = 0;
while(pos==N-i+1)
{
flag=!flag;
pos=1;
if(flag)step++;
i++;
}
if(i<N)
{
if(flag)
j = pos+step;
else
j = N-i+1-pos+step;
std::swap(ndx[j],ndx[j+1]);
res = "";
for(j=1;j<=N;j++)res=res+wrd[ndx[j]];
Memo1->Lines->Add(res);
pos++;
}
}
}
Цитата:
Originally posted by rostyslav
Можно и без рекурсии. Я (наверно) мог бы построить перестановки в последовательности
1234
2134
1324
3124
1324
3124
1243
...
Но алгоритм был бы, почти такой неэффективный, как ваш. Вместо этого алгоритм Джонса-Троттера (в моей реализации :))
Можно и без рекурсии. Я (наверно) мог бы построить перестановки в последовательности
1234
2134
1324
3124
1324
3124
1243
...
Но алгоритм был бы, почти такой неэффективный, как ваш. Вместо этого алгоритм Джонса-Троттера (в моей реализации :))
Код:
#include <algorithm>
#define N 4
String wrd = "ABCD";
void __fastcall TForm1::Button6Click(TObject *Sender)
{
Memo1->Clear();
String res;
bool flag[N+1];
int ndx[N+1], pos[N+1];
int i, j, step;
for(i=1;i<=N;i++)
{
ndx = i;
flag = true;
pos = 1;
}
res = "";
for(j=1;j<=N;j++)res= res + wrd[ndx[j]];
Memo1->Lines->Add(res);
pos[N] = 0;
i = 1;
while(i<N)
{
i = 1;
step = 0;
while(pos==N-i+1)
{
flag=!flag;
pos=1;
if(flag)step++;
i++;
}
if(i<N)
{
if(flag)
j = pos+step;
else
j = N-i+1-pos+step;
std::swap(ndx[j],ndx[j+1]);
res = "";
for(j=1;j<=N;j++)res=res+wrd[ndx[j]];
Memo1->Lines->Add(res);
pos++;
}
}
}
#define N 4
String wrd = "ABCD";
void __fastcall TForm1::Button6Click(TObject *Sender)
{
Memo1->Clear();
String res;
bool flag[N+1];
int ndx[N+1], pos[N+1];
int i, j, step;
for(i=1;i<=N;i++)
{
ndx = i;
flag = true;
pos = 1;
}
res = "";
for(j=1;j<=N;j++)res= res + wrd[ndx[j]];
Memo1->Lines->Add(res);
pos[N] = 0;
i = 1;
while(i<N)
{
i = 1;
step = 0;
while(pos==N-i+1)
{
flag=!flag;
pos=1;
if(flag)step++;
i++;
}
if(i<N)
{
if(flag)
j = pos+step;
else
j = N-i+1-pos+step;
std::swap(ndx[j],ndx[j+1]);
res = "";
for(j=1;j<=N;j++)res=res+wrd[ndx[j]];
Memo1->Lines->Add(res);
pos++;
}
}
}
А повторения?
Цитата:
Originally posted by AlexandrVSmirno
А повторения?
А повторения?
Алгоритм повторения не генерирует.
Цитата:
Originally posted by rostyslav
Алгоритм повторения не генерирует.
Алгоритм повторения не генерирует.
Попробуйте слово "аааа". Сколько у Вас слов получиться по алгоритму?
Цитата:
Originally posted by AlexandrVSmirno
Попробуйте слово "аааа". Сколько у Вас слов получиться по алгоритму?
Попробуйте слово "аааа". Сколько у Вас слов получиться по алгоритму?
24. Но это уже философский вопрос. Исходное слово [color=red]a[/color][color=blue]a[/color][color=orange]a[/color][color=indigo]a[/color]
Все перестановки:
[color=red]a[/color][color=blue]a[/color][color=orange]a[/color][color=indigo]a[/color]
[color=blue]a[/color][color=red]a[/color][color=orange]a[/color][color=indigo]a[/color]
[color=blue]a[/color][color=orange]a[/color][color=red]a[/color][color=indigo]a[/color]
[color=blue]a[/color][color=orange]a[/color][color=indigo]a[/color][color=red]a[/color]
[color=orange]a[/color][color=blue]a[/color][color=indigo]a[/color][color=red]a[/color]
[color=orange]a[/color][color=blue]a[/color][color=red]a[/color][color=indigo]a[/color]
[color=orange]a[/color][color=red]a[/color][color=blue]a[/color][color=indigo]a[/color]
[color=red]a[/color][color=orange]a[/color][color=blue]a[/color][color=indigo]a[/color]
[color=red]a[/color][color=orange]a[/color][color=indigo]a[/color][color=blue]a[/color]
[color=orange]a[/color][color=red]a[/color][color=indigo]a[/color][color=blue]a[/color]
[color=orange]a[/color][color=indigo]a[/color][color=red]a[/color][color=blue]a[/color]
[color=orange]a[/color][color=indigo]a[/color][color=blue]a[/color][color=red]a[/color]
[color=indigo]a[/color][color=orange]a[/color][color=blue]a[/color][color=red]a[/color]
[color=indigo]a[/color][color=orange]a[/color][color=red]a[/color][color=blue]a[/color]
[color=indigo]a[/color][color=red]a[/color][color=orange]a[/color][color=blue]a[/color]
[color=red]a[/color][color=indigo]a[/color][color=orange]a[/color][color=blue]a[/color]
[color=red]a[/color][color=indigo]a[/color][color=blue]a[/color][color=orange]a[/color]
[color=indigo]a[/color][color=red]a[/color][color=blue]a[/color][color=orange]a[/color]
[color=indigo]a[/color][color=blue]a[/color][color=red]a[/color][color=orange]a[/color]
[color=indigo]a[/color][color=blue]a[/color][color=orange]a[/color][color=red]a[/color]
[color=blue]a[/color][color=indigo]a[/color][color=orange]a[/color][color=red]a[/color]
[color=blue]a[/color][color=indigo]a[/color][color=red]a[/color][color=orange]a[/color]
[color=blue]a[/color][color=red]a[/color][color=indigo]a[/color][color=orange]a[/color]
[color=red]a[/color][color=blue]a[/color][color=indigo]a[/color][color=orange]a[/color]
Вы видите, хоть один дубль?
Алгоритм Джонса-Троттера для n чисел генерирует ровно n! разных перестановок. Если среди чисел есть дубли, конечно будут повторения.
Когда Вы спросили на счет дублей, я думал Вы имеете в виду, что генерируются ли алгоритмом одинаковые перестановки, как напр. для n=4, генерируется Вашим алгоритмом 64 перестановок, хоть разных есть 24. Или для n=6, генерируется 216 перестановок, хоть разных есть 720. итд.
Огромное спасибо. Разобрался.
Цитата:
Originally posted by rostyslav
24. Но это уже философский вопрос. Исходное слово [color=red]a[/color][color=blue]a[/color][color=orange]a[/color][color=indigo]a[/color]
Все перестановки:
[color=red]a[/color][color=blue]a[/color][color=orange]a[/color][color=indigo]a[/color]
[color=blue]a[/color][color=red]a[/color][color=orange]a[/color][color=indigo]a[/color]
[color=blue]a[/color][color=orange]a[/color][color=red]a[/color][color=indigo]a[/color]
[color=blue]a[/color][color=orange]a[/color][color=indigo]a[/color][color=red]a[/color]
[color=orange]a[/color][color=blue]a[/color][color=indigo]a[/color][color=red]a[/color]
[color=orange]a[/color][color=blue]a[/color][color=red]a[/color][color=indigo]a[/color]
[color=orange]a[/color][color=red]a[/color][color=blue]a[/color][color=indigo]a[/color]
[color=red]a[/color][color=orange]a[/color][color=blue]a[/color][color=indigo]a[/color]
[color=red]a[/color][color=orange]a[/color][color=indigo]a[/color][color=blue]a[/color]
[color=orange]a[/color][color=red]a[/color][color=indigo]a[/color][color=blue]a[/color]
[color=orange]a[/color][color=indigo]a[/color][color=red]a[/color][color=blue]a[/color]
[color=orange]a[/color][color=indigo]a[/color][color=blue]a[/color][color=red]a[/color]
[color=indigo]a[/color][color=orange]a[/color][color=blue]a[/color][color=red]a[/color]
[color=indigo]a[/color][color=orange]a[/color][color=red]a[/color][color=blue]a[/color]
[color=indigo]a[/color][color=red]a[/color][color=orange]a[/color][color=blue]a[/color]
[color=red]a[/color][color=indigo]a[/color][color=orange]a[/color][color=blue]a[/color]
[color=red]a[/color][color=indigo]a[/color][color=blue]a[/color][color=orange]a[/color]
[color=indigo]a[/color][color=red]a[/color][color=blue]a[/color][color=orange]a[/color]
[color=indigo]a[/color][color=blue]a[/color][color=red]a[/color][color=orange]a[/color]
[color=indigo]a[/color][color=blue]a[/color][color=orange]a[/color][color=red]a[/color]
[color=blue]a[/color][color=indigo]a[/color][color=orange]a[/color][color=red]a[/color]
[color=blue]a[/color][color=indigo]a[/color][color=red]a[/color][color=orange]a[/color]
[color=blue]a[/color][color=red]a[/color][color=indigo]a[/color][color=orange]a[/color]
[color=red]a[/color][color=blue]a[/color][color=indigo]a[/color][color=orange]a[/color]
Вы видите, хоть один дубль?
Алгоритм Джонса-Троттера для n чисел генерирует ровно n! разных перестановок. Если среди чисел есть дубли, конечно будут повторения.
Когда Вы спросили на счет дублей, я думал Вы имеете в виду, что генерируются ли алгоритмом одинаковые перестановки, как напр. для n=4, генерируется Вашим алгоритмом 64 перестановок, хоть разных есть 24. Или для n=6, генерируется 216 перестановок, хоть разных есть 720. итд.
24. Но это уже философский вопрос. Исходное слово [color=red]a[/color][color=blue]a[/color][color=orange]a[/color][color=indigo]a[/color]
Все перестановки:
[color=red]a[/color][color=blue]a[/color][color=orange]a[/color][color=indigo]a[/color]
[color=blue]a[/color][color=red]a[/color][color=orange]a[/color][color=indigo]a[/color]
[color=blue]a[/color][color=orange]a[/color][color=red]a[/color][color=indigo]a[/color]
[color=blue]a[/color][color=orange]a[/color][color=indigo]a[/color][color=red]a[/color]
[color=orange]a[/color][color=blue]a[/color][color=indigo]a[/color][color=red]a[/color]
[color=orange]a[/color][color=blue]a[/color][color=red]a[/color][color=indigo]a[/color]
[color=orange]a[/color][color=red]a[/color][color=blue]a[/color][color=indigo]a[/color]
[color=red]a[/color][color=orange]a[/color][color=blue]a[/color][color=indigo]a[/color]
[color=red]a[/color][color=orange]a[/color][color=indigo]a[/color][color=blue]a[/color]
[color=orange]a[/color][color=red]a[/color][color=indigo]a[/color][color=blue]a[/color]
[color=orange]a[/color][color=indigo]a[/color][color=red]a[/color][color=blue]a[/color]
[color=orange]a[/color][color=indigo]a[/color][color=blue]a[/color][color=red]a[/color]
[color=indigo]a[/color][color=orange]a[/color][color=blue]a[/color][color=red]a[/color]
[color=indigo]a[/color][color=orange]a[/color][color=red]a[/color][color=blue]a[/color]
[color=indigo]a[/color][color=red]a[/color][color=orange]a[/color][color=blue]a[/color]
[color=red]a[/color][color=indigo]a[/color][color=orange]a[/color][color=blue]a[/color]
[color=red]a[/color][color=indigo]a[/color][color=blue]a[/color][color=orange]a[/color]
[color=indigo]a[/color][color=red]a[/color][color=blue]a[/color][color=orange]a[/color]
[color=indigo]a[/color][color=blue]a[/color][color=red]a[/color][color=orange]a[/color]
[color=indigo]a[/color][color=blue]a[/color][color=orange]a[/color][color=red]a[/color]
[color=blue]a[/color][color=indigo]a[/color][color=orange]a[/color][color=red]a[/color]
[color=blue]a[/color][color=indigo]a[/color][color=red]a[/color][color=orange]a[/color]
[color=blue]a[/color][color=red]a[/color][color=indigo]a[/color][color=orange]a[/color]
[color=red]a[/color][color=blue]a[/color][color=indigo]a[/color][color=orange]a[/color]
Вы видите, хоть один дубль?
Алгоритм Джонса-Троттера для n чисел генерирует ровно n! разных перестановок. Если среди чисел есть дубли, конечно будут повторения.
Когда Вы спросили на счет дублей, я думал Вы имеете в виду, что генерируются ли алгоритмом одинаковые перестановки, как напр. для n=4, генерируется Вашим алгоритмом 64 перестановок, хоть разных есть 24. Или для n=6, генерируется 216 перестановок, хоть разных есть 720. итд.
Да. Это все строка аааа. И цвет здесь не причем. Вы никак не хотите понять, что здесь перестановки с повторениями и этто далеко не n!. Проблема в том, что Ваш алгоритм работает с индексами, а не со значениями. Мой же алгоритм работает со значениями. Да он генерит больше вариантов чем нужно, но не нужное тут же отметает. А если вы добавите в свой проверку на дубли? Где-же будет Ваша хваленая эффективность. Я думаю там-же где и моя. Если не дальше, поскольку вам предется все равно просматривать весь массив полученных значений на дубли.
Цитата:
Originally posted by AlexandrVSmirno
Да. Это все строка аааа. И цвет здесь не причем. Вы никак не хотите понять, что здесь перестановки с повторениями и этто далеко не n!.
Да. Это все строка аааа. И цвет здесь не причем. Вы никак не хотите понять, что здесь перестановки с повторениями и этто далеко не n!.
Давайте тогда так: максимальное количество различных перестановок для n символов равна n!. И чтоб перекрыть все возможные случаи, нужно исходить из этого.
Цитата:
Проблема в том, что Ваш алгоритм работает с индексами, а не со значениями.
Это не проблема. Ниже алгоритм без индексов.
Код:
void __fastcall TForm1::Button6Click(TObject *Sender)
{
Memo1->Clear();
AnsiString begStr = Trim(Edit1->Text);
int n = begStr.Length();
if(n<2)
{
ShowMessage("Для генерирования перестановок, слово должно содержать хотя бы 2 символа!");
return;
}
bool *flag = new bool[n+1];
int *pos = new int[n+1];
int i, j, step;
for(i=1;i<=n;i++)
{
flag = true;
pos = 1;
}
Memo1->Lines->Add(begStr);
pos[n] = 0;
i = 1;
try
{
while(i<n)
{
i = 1;
step = 0;
while(pos==n-i+1)
{
flag=!flag;
pos=1;
if(flag)step++;
i++;
}
if(i<n)
{
if(flag)
j = pos+step;
else
j = n-i+1-pos+step;
char c = begStr[j];
begStr[j] = begStr[j+1];
begStr[j+1] = c;
if(Memo1->Lines->Text.Pos(begStr)==0)
Memo1->Lines->Add(begStr);
pos++;
}
}
}
__finally
{
delete flag;
delete pos;
}
ShowMessage("Число перестановок слова '"+Trim(Edit1->Text)+"' равна " + IntToStr(Memo1->Lines->Count));
}
{
Memo1->Clear();
AnsiString begStr = Trim(Edit1->Text);
int n = begStr.Length();
if(n<2)
{
ShowMessage("Для генерирования перестановок, слово должно содержать хотя бы 2 символа!");
return;
}
bool *flag = new bool[n+1];
int *pos = new int[n+1];
int i, j, step;
for(i=1;i<=n;i++)
{
flag = true;
pos = 1;
}
Memo1->Lines->Add(begStr);
pos[n] = 0;
i = 1;
try
{
while(i<n)
{
i = 1;
step = 0;
while(pos==n-i+1)
{
flag=!flag;
pos=1;
if(flag)step++;
i++;
}
if(i<n)
{
if(flag)
j = pos+step;
else
j = n-i+1-pos+step;
char c = begStr[j];
begStr[j] = begStr[j+1];
begStr[j+1] = c;
if(Memo1->Lines->Text.Pos(begStr)==0)
Memo1->Lines->Add(begStr);
pos++;
}
}
}
__finally
{
delete flag;
delete pos;
}
ShowMessage("Число перестановок слова '"+Trim(Edit1->Text)+"' равна " + IntToStr(Memo1->Lines->Count));
}
Цитата:
Мой же алгоритм работает со значениями. Да он генерит больше вариантов чем нужно, но не нужное тут же отметает. А если вы добавите в свой проверку на дубли? Где-же будет Ваша хваленая эффективность. Я думаю там-же где и моя.
Это не моя хваленная эффективность. Алгоритм выдумали 2 математика. Считается лучшим. Работает без рекурсии, и каждая новая перестановка получается с предыдущей одной операцией swap. Конечно есть накладные рассходы для определения того, каие элементы нужно поменять местами, но такие же рассходы есть и в других алгоритмах
Цитата:
Если не дальше, поскольку вам предется все равно просматривать весь массив полученных значений на дубли.
Для n=4 алг.Д-Т генерирует 24 перестановок и ищет в них дубли. Ваш генерирует 64 (и даже не все возможные) и ищет среди них дубли. И это еще лучший вариант. Число перестановок, которых генерирует Ваш алгоритм равна n в кубе.
для n = 6, напр. для слова ABCDEF существует 720 разных перестановок (прилагаю снимок). Ваш алгоритм генерирует 216 перестановок.
Вы писали, что для 4 символа нужно 4 цикла, для 5 символов 5 итд. Это дает n в степери n. Т.е. для ABCDEF Ваш алгоритм сгенерирует 46656 вместо 720.
Цитата:
Originally posted by rostyslav
Давайте тогда так: максимальное количество различных перестановок для n символов равна n!. И чтоб перекрыть все возможные случаи, нужно исходить из этого.
Это не проблема. Ниже алгоритм без индексов.
Это не моя хваленная эффективность. Алгоритм выдумали 2 математика. Считается лучшим. Работает без рекурсии, и каждая новая перестановка получается с предыдущей одной операцией swap. Конечно есть накладные рассходы для определения того, каие элементы нужно поменять местами, но такие же рассходы есть и в других алгоритмахДля n=4 алг.Д-Т генерирует 24 перестановок и ищет в них дубли. Ваш генерирует 64 (и даже не все возможные) и ищет среди них дубли. И это еще лучший вариант. Число перестановок, которых генерирует Ваш алгоритм равна n в кубе.
для n = 6, напр. для слова ABCDEF существует 720 разных перестановок (прилагаю снимок). Ваш алгоритм генерирует 216 перестановок.
Вы писали, что для 4 символа нужно 4 цикла, для 5 символов 5 итд. Это дает n в степери n. Т.е. для ABCDEF Ваш алгоритм сгенерирует 46656 вместо 720.
Давайте тогда так: максимальное количество различных перестановок для n символов равна n!. И чтоб перекрыть все возможные случаи, нужно исходить из этого.
Это не проблема. Ниже алгоритм без индексов.
Код:
void __fastcall TForm1::Button6Click(TObject *Sender)
{
Memo1->Clear();
AnsiString begStr = Trim(Edit1->Text);
int n = begStr.Length();
if(n<2)
{
ShowMessage("Для генерирования перестановок, слово должно содержать хотя бы 2 символа!");
return;
}
bool *flag = new bool[n+1];
int *pos = new int[n+1];
int i, j, step;
for(i=1;i<=n;i++)
{
flag = true;
pos = 1;
}
Memo1->Lines->Add(begStr);
pos[n] = 0;
i = 1;
try
{
while(i<n)
{
i = 1;
step = 0;
while(pos==n-i+1)
{
flag=!flag;
pos=1;
if(flag)step++;
i++;
}
if(i<n)
{
if(flag)
j = pos+step;
else
j = n-i+1-pos+step;
char c = begStr[j];
begStr[j] = begStr[j+1];
begStr[j+1] = c;
if(Memo1->Lines->Text.Pos(begStr)==0)
Memo1->Lines->Add(begStr);
pos++;
}
}
}
__finally
{
delete flag;
delete pos;
}
ShowMessage("Число перестановок слова '"+Trim(Edit1->Text)+"' равна " + IntToStr(Memo1->Lines->Count));
}
{
Memo1->Clear();
AnsiString begStr = Trim(Edit1->Text);
int n = begStr.Length();
if(n<2)
{
ShowMessage("Для генерирования перестановок, слово должно содержать хотя бы 2 символа!");
return;
}
bool *flag = new bool[n+1];
int *pos = new int[n+1];
int i, j, step;
for(i=1;i<=n;i++)
{
flag = true;
pos = 1;
}
Memo1->Lines->Add(begStr);
pos[n] = 0;
i = 1;
try
{
while(i<n)
{
i = 1;
step = 0;
while(pos==n-i+1)
{
flag=!flag;
pos=1;
if(flag)step++;
i++;
}
if(i<n)
{
if(flag)
j = pos+step;
else
j = n-i+1-pos+step;
char c = begStr[j];
begStr[j] = begStr[j+1];
begStr[j+1] = c;
if(Memo1->Lines->Text.Pos(begStr)==0)
Memo1->Lines->Add(begStr);
pos++;
}
}
}
__finally
{
delete flag;
delete pos;
}
ShowMessage("Число перестановок слова '"+Trim(Edit1->Text)+"' равна " + IntToStr(Memo1->Lines->Count));
}
для n = 6, напр. для слова ABCDEF существует 720 разных перестановок (прилагаю снимок). Ваш алгоритм генерирует 216 перестановок.
Вы писали, что для 4 символа нужно 4 цикла, для 5 символов 5 итд. Это дает n в степери n. Т.е. для ABCDEF Ваш алгоритм сгенерирует 46656 вместо 720.
Тем не менее он работает правильно в отличие от Вашего.
Цитата:
Originally posted by AlexandrVSmirno
Тем не менее он работает правильно в отличие от Вашего.
Тем не менее он работает правильно в отличие от Вашего.
???
Для слова ABCD Ваша программа находит 22 перестановки, пропустив BDCA и CDAB.
Для ABCDEF программа находит 152 из имеющихся 720.
Хм...
Один пример плз, на которой моя прога работает неправильно.