#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
void print(char elem) { cout<<elem; }
void (*pp)(char) = print;
int _tmain(int argc, _TCHAR* argv[])
{
string s("23415");
cout<<s<<"\n\n";
sort(s.begin(),s.end());
for_each(s.begin(),s.end(),pp);
cout<<'\t';
int a = 2;
while(next_permutation(s.begin(),s.end()))
{
for_each(s.begin(),s.end(),pp);
cout<<'\t';
if(! (a++ % 8))
{
cout<<'\n';
a = 1;
}
}
cout<<"\n\n";
return 0;
}
Получение перестановок строки
Допустим есть строка. Посоветуйте пожалуйста как реализовать алгоритм получения всех её перестановок (время выполнения не важно!). или может есть готовая реализация на каком-нибудь языке (по барабану на каком).
у нас имеется строка: word1 word2 word3, у нас имеется 3 слова, берем факториал 3, получаем 6. У нас имеется всего 6 вариантов перестановки (с учетом исходного варианта)
Цитата: ahilles
Допустим есть строка. Посоветуйте пожалуйста как реализовать алгоритм получения всех её перестановок (время выполнения не важно!). или может есть готовая реализация на каком-нибудь языке (по барабану на каком).
На С++ легко сделать.При помощи обобщенного алгоритма - next_permutation.Вот пример,всех перестановок строки.
Код:
Метод очень простой, но и очень тормозной. Был высосан из пальца по дороге в институт пару лет назад ;-)
;----------
Пока писал уже ответили. Оставлю просто так, просьба сильно не пинать.
Код:
program permut;
{$APPTYPE CONSOLE}
uses
SysUtils;
const
N=8;
type
mas=array[char] of byte;
stroke=array[1..8] of char;
var
M,MyM: stroke;
used: mas;
step,i,L: byte;
j: string[N];
{-----------------------------------------------------------}
procedure file_read();
begin
assign(input,'permut2.in');
reset(input);
assign(output,'permut2.out');
rewrite(output);
end;
{-----------------------------------------------------------}
procedure perebor(var MyM: stroke; var used: mas; step: byte; const L: byte);
var
i: char;
j: byte;
begin
If step>L then begin
for j:=1 to L-1 do
write(MyM[j]);
writeln(MyM[j]);
end else begin
for i:=chr(1) to chr(255) do
If used>0 then begin
MyM[step]:=i;
dec(used);
perebor(MyM,used,step+1,L);
inc(used);
end;
end;
end;
{-----------------------------------------------------------}
begin
file_read();
read(j);
L:=Length(j);
for i:=1 to L do
M:=j;
for i:=1 to N do
inc(used[M]);
perebor(MyM,used,1,L);
end.
{$APPTYPE CONSOLE}
uses
SysUtils;
const
N=8;
type
mas=array[char] of byte;
stroke=array[1..8] of char;
var
M,MyM: stroke;
used: mas;
step,i,L: byte;
j: string[N];
{-----------------------------------------------------------}
procedure file_read();
begin
assign(input,'permut2.in');
reset(input);
assign(output,'permut2.out');
rewrite(output);
end;
{-----------------------------------------------------------}
procedure perebor(var MyM: stroke; var used: mas; step: byte; const L: byte);
var
i: char;
j: byte;
begin
If step>L then begin
for j:=1 to L-1 do
write(MyM[j]);
writeln(MyM[j]);
end else begin
for i:=chr(1) to chr(255) do
If used>0 then begin
MyM[step]:=i;
dec(used);
perebor(MyM,used,step+1,L);
inc(used);
end;
end;
end;
{-----------------------------------------------------------}
begin
file_read();
read(j);
L:=Length(j);
for i:=1 to L do
M:=j;
for i:=1 to N do
inc(used[M]);
perebor(MyM,used,1,L);
end.
В Delphi7 все работает-проверял.
выкладываю, может быть кому-нибудь пригодится (сомневаюсь что в нём вообще кто-нибудь разберётся, кто разберётся тот герой :) )
Код:
program project2;
{$APPTYPE CONSOLE}
uses windows;
var
mainstr,str1:string;
combmass:pointer;
function GetSrtMod(vstr:string;indx:pointer):string;
var
resstr:string;
i,l:integer;
begin
Result:='';
l:=Length(Pchar(indx));
for i:=1 to l do
Result:=Result+vstr[byte(PChar(indx)[i-1])];
end;
function GetFirstPermutation(str:string;pmassiv:pointer):string;
var
i:integer;
begin
pointer(pmassiv^):=HeapAlloc(GetProcessHeap,8,length(str));
for i:=1 to length(str) do
Byte(PChar(pmassiv^)[i-1]):=i;
Byte(PChar(pmassiv^)[i-1]):=0;
Result:=GetSrtMod(str,pointer(pmassiv^));
end;
function IsPermutArray(massiv:pointer):boolean;
var
i,j,l:integer;
begin
result:=True;
l:=Length(Pchar(massiv));
for i:=1 to l-1 do
for j:=i+1 to l do
if Byte(PChar(massiv)[i-1])=Byte(PChar(massiv)[j-1]) then
begin
Result:=false;
exit;
end;
end;
function GetNextPermutation(str:string;massiv:pointer):string;
var
len,ci:integer;
dorep:boolean;
begin
result:=str;
len:=length(str);
ci:=len-1;
repeat
if ci=-1 then exit;
dorep:=true;
if byte(PChar(massiv)[ci])=len then
begin
byte(PChar(massiv)[ci]):=1;
dec(ci);
continue;
end;
Byte(PChar(massiv)[ci]):=Byte(PChar(massiv)[ci])+1;
if not IsPermutArray(massiv) then
begin
ci:=len-1;
continue;
end;
dorep:= false;
until not dorep;
Result:=GetSrtMod(str,massiv);
end;
begin
write('vvedite stroku: ');
Readln(mainstr);
str1:=GetFirstPermutation(mainstr,@combmass);
repeat
writeln(str1);
str1:=GetNextPermutation(mainstr,combmass);
until str1=mainstr;
Readln;
end.
{$APPTYPE CONSOLE}
uses windows;
var
mainstr,str1:string;
combmass:pointer;
function GetSrtMod(vstr:string;indx:pointer):string;
var
resstr:string;
i,l:integer;
begin
Result:='';
l:=Length(Pchar(indx));
for i:=1 to l do
Result:=Result+vstr[byte(PChar(indx)[i-1])];
end;
function GetFirstPermutation(str:string;pmassiv:pointer):string;
var
i:integer;
begin
pointer(pmassiv^):=HeapAlloc(GetProcessHeap,8,length(str));
for i:=1 to length(str) do
Byte(PChar(pmassiv^)[i-1]):=i;
Byte(PChar(pmassiv^)[i-1]):=0;
Result:=GetSrtMod(str,pointer(pmassiv^));
end;
function IsPermutArray(massiv:pointer):boolean;
var
i,j,l:integer;
begin
result:=True;
l:=Length(Pchar(massiv));
for i:=1 to l-1 do
for j:=i+1 to l do
if Byte(PChar(massiv)[i-1])=Byte(PChar(massiv)[j-1]) then
begin
Result:=false;
exit;
end;
end;
function GetNextPermutation(str:string;massiv:pointer):string;
var
len,ci:integer;
dorep:boolean;
begin
result:=str;
len:=length(str);
ci:=len-1;
repeat
if ci=-1 then exit;
dorep:=true;
if byte(PChar(massiv)[ci])=len then
begin
byte(PChar(massiv)[ci]):=1;
dec(ci);
continue;
end;
Byte(PChar(massiv)[ci]):=Byte(PChar(massiv)[ci])+1;
if not IsPermutArray(massiv) then
begin
ci:=len-1;
continue;
end;
dorep:= false;
until not dorep;
Result:=GetSrtMod(str,massiv);
end;
begin
write('vvedite stroku: ');
Readln(mainstr);
str1:=GetFirstPermutation(mainstr,@combmass);
repeat
writeln(str1);
str1:=GetNextPermutation(mainstr,combmass);
until str1=mainstr;
Readln;
end.
но у него есть ДВА минуса:
1. максимальная длина строки 256 символов
2. При больших размерах строк алгоритм работает ОЧЕНЬ медленно.