| Новости | Поиск | FAQ | Статьи | Книги | Новости VCL | | Форумы ЧАТ | Орешник | KOL и MCK |
Форумы -» Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

	« предыдущая ветвь | форум | следующая ветвь »

Алгоритм перебора всех комбинаций

RealGanj ©   (2007-01-13 17:59:00) 

Есть строка символов произвольной длины. (Н-р, "abc"). Нужно получить ве возможные перестановки (bca,acb,...)
Подскажите или алгоритм, или готовый код. (Жедательно алгоритм)

---

школьник :-)   (2007-01-15 17:48:00) [1]

> Алгоритм перебора всех комбинаций


к сожалению перестановки != комбинации (имхо), поэтому я кинул свой примерчик, с перестановками согласен.

---

ors_archangel   (2007-01-15 14:06:00) [2]

> 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 13:26:00) [3]

> - странно, получается, что за внутренний цикл должен быть
> выведен один вариант перестановки, но не каждый символ может
> быть выведен в результате этого кода, т.к. условие i & c
> не всегда будет выполнятся, получается выборка какая-то
> или я совсем Си не знаю!??


думаю на пасе будет тоже самое, по крайней мере должно быть.
попробуй разложить все :-)
пиши на бумаге
ABCD
0000
0001
0011
......

короче биты отчечают, за то, что выводить - в общих чертах :-)

---

школьник :-)   (2007-01-15 13:23:00) [4]

> int pr = 1 и
> int a = i & c;

смотрел в дебагере какие значения получаются :-)

---

ors_archangel   (2007-01-14 23:55:00) [5]

Не понял юмора! :)))

---

ors_archangel   (2007-01-14 23:53:00) [6]

int pr = 1

---

школьник :-)   (2007-01-14 22:21:00) [7]

К сожалению нет под рукой дельфи, так што на сях :-)

//---------------------------------------------------------------------------

#include
#include
#include
#pragma hdrstop

//---------------------------------------------------------------------------

#pragma argsused

using std::string;
using std::cout;
using std::cin;
using std::endl;

int main()
{
 string s = "ABCDEFGH";
 int pr = 1

---

Sha   (2007-01-14 00:54:00) [8]

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;


И че я добрый такой?

---

antonn   (2007-01-13 22:53:00) [9]

> Так задача же получить перестановки

хм, действительно:)

---

ors_archangel   (2007-01-13 22:01:00) [10]

>  Вроде так:)

Так задача же получитьперестановки, а не подсчитать их количество. Подсчитать количество перестановок без повторений, действительно, очень просто:

 Pn = n!

С повторениями:

 Pn = n! / (П ki!)

- если есть k = Σki, где ki - число элементов i-го класса.

---

antonn   (2007-01-13 21:50:00) [11]

не надо переставлять и сравнивать строки, этоже математика (из раздела перестановки). нужно знать кол-во повторяющихся значений и общее кол-во, а затем рубить их факториалами. Вроде так:)

---

ors_archangel   (2007-01-13 18:06:00) [12]

Может быть даже работает:
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

---

Джо   (2007-01-13 18:01:00) [13]

algolist.manual.ru

---

Наверх