Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

Получение перестановок строки

261
09 октября 2007 года
ahilles
1.5K / / 03.11.2005
Допустим есть строка. Посоветуйте пожалуйста как реализовать алгоритм получения всех её перестановок (время выполнения не важно!). или может есть готовая реализация на каком-нибудь языке (по барабану на каком).
489
09 октября 2007 года
NeO_u
277 / / 11.10.2006
Если мне не изменяеть память, то это факториал кол-ва слов. например:
у нас имеется строка: word1 word2 word3, у нас имеется 3 слова, берем факториал 3, получаем 6. У нас имеется всего 6 вариантов перестановки (с учетом исходного варианта)
320
09 октября 2007 года
m_Valery
1.0K / / 08.01.2007
Цитата: ahilles
Допустим есть строка. Посоветуйте пожалуйста как реализовать алгоритм получения всех её перестановок (время выполнения не важно!). или может есть готовая реализация на каком-нибудь языке (по барабану на каком).


На С++ легко сделать.При помощи обобщенного алгоритма - next_permutation.Вот пример,всех перестановок строки.

Код:
#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;
}
1.6K
09 октября 2007 года
Vov4ick
476 / / 01.02.2007
Я одно время делал так: Пусть в строке N разных символов. Представляем её как число в системе счисления с основанием N. Берём некоторое начальное число (проще всего ноль) с разрядностью, равной длине строки, и прибавляем к нему единицу. После этого проверяем, соответствует ли полученная строчка по числу разных символов начальной строке. Если нет, прибавляем единицу ещё раз. Если да, то одна из перестановок получена. Далее в цикле до последнего возможно числа нашей системы счисления.
Метод очень простой, но и очень тормозной. Был высосан из пальца по дороге в институт пару лет назад ;-)
;----------
Пока писал уже ответили. Оставлю просто так, просьба сильно не пинать.
1.6K
10 октября 2007 года
Shtirlitz
145 / / 31.07.2006
Я в консоли Delphi это реализовывал следующим образом:
Код:
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.


В Delphi7 все работает-проверял.
261
02 ноября 2007 года
ahilles
1.5K / / 03.11.2005
наконец-то нашёл свободное время и реализовал алгоритм получения перстановок БЕЗ рекурсий, по схеме которую описал Vov4ick (или что-то наподобие)
выкладываю, может быть кому-нибудь пригодится (сомневаюсь что в нём вообще кто-нибудь разберётся, кто разберётся тот герой :) )
Код:
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.

но у него есть ДВА минуса:
1. максимальная длина строки 256 символов
2. При больших размерах строк алгоритм работает ОЧЕНЬ медленно.
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог