Текущий архив: 2007.02.04;
Скачать: CL | DM;
Вниз
Алгоритм перебора всех комбинаций Найти похожие ветки
← →
RealGanj (2007-01-13 17:59) [0]Есть строка символов произвольной длины. (Н-р, "abc"). Нужно получить ве возможные перестановки (bca,acb,...)
Подскажите или алгоритм, или готовый код. (Жедательно алгоритм)
← →
Джо © (2007-01-13 18:01) [1]algolist.manual.ru
← →
ors_archangel © (2007-01-13 18:06) [2]Может быть даже работает:
var
s: string;
idx: array of integer;
done: boolean;
procedure Transposition(from: integer = 0);
var
i,over: integer;
begin
if from = length(s) then begin
done := true;
exit;
end;
i := from;
over := from;
if idx[i]=over then begin
swap(s[1+i],s[1+i-idx[i]]);
idx[i] := 0;
Transposition(from+1);
end else begin
swap(s[1+i],s[1+i-idx[i]]);
inc(idx[i]);
swap(s[1+i],s[1+i-idx[i]])
end
end;
begin
done := false;
repet
Transposition;
Writeln(s);
until done;
end
← →
antonn © (2007-01-13 21:50) [3]не надо переставлять и сравнивать строки, этоже математика (из раздела перестановки). нужно знать кол-во повторяющихся значений и общее кол-во, а затем рубить их факториалами. Вроде так:)
← →
ors_archangel © (2007-01-13 22:01) [4]
> Вроде так:)
Так задача же получить перестановки, а не подсчитать их количество. Подсчитать количество перестановок без повторений, действительно, очень просто:
Pn = n!
С повторениями:
Pn = n! / (П ki!)
- если есть k = Σki, где ki - число элементов i-го класса.
← →
antonn © (2007-01-13 22:53) [5]
> Так задача же получить перестановки
хм, действительно:)
← →
Sha © (2007-01-14 00:54) [6]
procedure TForm1.Button4Click(Sender: TObject);
var
n: integer;
s: string;
//(p<>nil) and (len>=1)
procedure GenerateSubs(p: pchar; len: integer);
var
i: integer;
ch: char;
begin;
if len<=2 then begin;
if len>0 then begin;
n:=n+1; Memo1.Lines.Add(Format("%2d %s",[n,s]));
end;
if len=2 then begin;
ch:=p[0]; p[0]:=p[1]; p[1]:=ch;
n:=n+1; Memo1.Lines.Add(Format("%2d %s",[n,s]));
ch:=p[0]; p[0]:=p[1]; p[1]:=ch;
end;
end
else begin;
GenerateSubs(p+1,len-1);
for i:=1 to len-1 do begin;
ch:=p[0]; p[0]:=p[i]; p[i]:=ch;
GenerateSubs(p+1,len-1);
end;
ch:=p[0];
for i:=1 to len-1 do p[i-1]:=p[i];
p[len-1]:=ch;
end;
end;
var
len: integer;
p: pchar;
begin
Memo1.Lines.Clear;
len:=StrToIntDef(Edit1.Text,0);
if len>0 then begin;
SetLength(s,len);
p:=pointer(s);
for n:=0 to len-1 do p[n]:=chr(n+ord("a"));
n:=0;
GenerateSubs(p,len);
end;
end;
И че я добрый такой?
← →
школьник :-) (2007-01-14 22:21) [7]К сожалению нет под рукой дельфи, так што на сях :-)
//---------------------------------------------------------------------------
#include <vcl.h>
#include <iostream.h>
#include <string.h>
#pragma hdrstop
//---------------------------------------------------------------------------
#pragma argsused
using std::string;
using std::cout;
using std::cin;
using std::endl;
int main()
{
string s = "ABCDEFGH";
int pr = 1 << s.size();
for (int i = 0; i < (1 << s.size()); i++)
{
for (int c = 1, j = 0; j < s.size(); j++, c = c << 1)
{
int a = i & c;
if (i & c)
{
cout << s[j];
}
}
cout << endl;
}
return 0;
}
//---------------------------------------------------------------------------
← →
ors_archangel © (2007-01-14 23:53) [8]
int pr = 1 << s.size();
иint a = i & c;
- зачем?
for (int c = 1, j = 0; j < s.size(); j++, c = c << 1)
{
int a = i & c;
if (i & c)
{
cout << s[j];
}
}
- странно, получается, что за внутренний цикл должен быть выведен один вариант перестановки, но не каждый символ может быть выведен в результате этого кода, т.к. условие i & c не всегда будет выполнятся, получается выборка какая-то или я совсем Си не знаю!??
← →
ors_archangel © (2007-01-14 23:55) [9]Не понял юмора! :)))
← →
школьник :-) (2007-01-15 13:23) [10]
> int pr = 1 << s.size();
> и
> int a = i & c;
смотрел в дебагере какие значения получаются :-)
← →
школьник :-) (2007-01-15 13:26) [11]
> - странно, получается, что за внутренний цикл должен быть
> выведен один вариант перестановки, но не каждый символ может
> быть выведен в результате этого кода, т.к. условие i & c
> не всегда будет выполнятся, получается выборка какая-то
> или я совсем Си не знаю!??
думаю на пасе будет тоже самое, по крайней мере должно быть.
попробуй разложить все :-)
пиши на бумаге
ABCD
0000
0001
0011
......
короче биты отчечают, за то, что выводить - в общих чертах :-)
← →
ors_archangel © (2007-01-15 14:06) [12]
> 0000 0001 0011
Всё-таки:
for j := 1 to s.size do
if condition then
write(s[j])
За цикл должна быть выведена вся перестановка, так?
Получаем, т.к. сторка индексируется по j, следовательно вывод будет всегда строго последовательный, например, если condition тождественно true, то получим
ABCD
если condition то true, то false:
AC
т.е. B и D - пропущены; если condition всегда false - ничего не получим.
Определение: Перестановка упорядоченного множества - есть новое упорядоченное множество, отличающееся от данного порядком следования элементов. - Не количеством, а порядком, т.е., например
01. ABCD
02. ABDC
03. ACBD
04. ACDB
05. ADBC
06. ADCB
07. BACD
08. BADC
09. BCAD
10. BCDA
11. BDAC
12. BDCA
13. CABD
14. CADB
15. CBAD
16. CBDA
... ...
Короче, вот такие у меня мысли :)
p.s. 24. DCBA
← →
школьник :-) (2007-01-15 17:48) [13]
> Алгоритм перебора всех комбинаций
к сожалению перестановки != комбинации (имхо), поэтому я кинул свой примерчик, с перестановками согласен.
Страницы: 1 вся ветка
Текущий архив: 2007.02.04;
Скачать: CL | DM;
Память: 0.5 MB
Время: 0.029 c
