Комбинаторика - нахождение всех возможных комбинаций

[chandrasecar]

Есть 4 числа: 1, 2, 3, 4. Нужно узнать все возможные комбинации из этих 4-х чисел в числе, состоящем из N знаков.

Например если число пятизначное, то чтобы узнать все комбинации, нужно сделать пять вложенных циклов от 1 до 4. А если число знаков в числе неизвестно заранее и оно может изменяться от 1 и до бесконечности (грубо говоря). Как в таком случае вычислить все комбинации?

В результате получается 4 в степени N возможных вариантов, где N - число знаков в числе.

[Сtrl]

Поиск - великая вещь...

procedure generate(l, r: Integer; var k: longint);
var
  i, v: Integer;
begin
  if (l = r) then
  begin
    for i := 1 to n do
      write(a[i], ' ');
    writeln;
    k := k + 1;
  end
  else
  begin
    generate(l + 1, r, k); { вызов новой генерации }
    for i := l + 1 to r do
    begin
      v := a[l];
      a[l] := a[i];
      a[i] := v; { обмен a[i],a[l] }
      generate(l + 1, r, k); { вызов новой генерации }
    end;
    v := a[l];
    for i := l to r - 1 do
      a[i] := a[i + 1];
    a[r] := v;
  end;
end;

[phomm]

я делал так http://programmersforum.ru/showthread.php?t=138096

[chandrasecar]

Поиск - великая вещь...

http://www.cyberforum.ru/pascal/thread188474.html

{генерация перестановок }
uses crt;
const n = 4; { количество элементов в перестановке}
var a:array[1..n] of integer;
    j:integer;{счетчик}
    kol : longint;{количество перестановок}
procedure generate (l,r:integer;var k:longint);
var i,v:integer;
begin
if (l=r) then
  begin
    for i:=1 to n do write(a[i],' ');
    writeln;
    k:=k+1;
  end
else
  begin
    for i := l to r do
      begin
        v:=a[l]; a[l]:=a[i]; a[i]:=v; {обмен a[i],a[l]}
        generate(l+1,r,k); {вызов новой генерации}
        v:=a[l]; a[l]:=a[i]; a[i]:=v; {обмен a[i],a[l]}
      end;
  end;
end;
begin
clrscr;
for j := 1 to N do
a[j]:=j;
generate( 1,n,kol);
writeln('kol=',kol);
readln
end.

И как это сделать в Дельфи? Например с ЛистБоксом и выводом всех вариантов решения?

[Serge_Bliznykov]

И как это сделать в Дельфи? Например, с ЛистБоксом и выводом всех вариантов решения?

дык достаточно заменить вывод в процедуре generate:

procedure generate (l,r:integer;var k:longint);
var i,v:integer;
     s : string;
begin
if (l=r) then
  begin
    s := '';
    for i:=1 to n do s := s + IntToStr(a[i])+' ';
    ListBox1.Items.Append(s); 
    k:=k+1;
  end

[chandrasecar]

Спасибо. Я свой алгоритм написал, все устраивает.

[Sibedir]

Уважаемый chandrasecar, ну покажите уж, что сделали. У нас так заведено. Решил задачу - покажи как.
Тем более

Я свой алгоритм написал

так еще интересней

[chandrasecar]

Уважаемый chandrasecar, ну покажите уж, что сделали. У нас так заведено. Решил задачу - покажи как.

Само собой. Наверняка можно и лучше сделать. Но тоже рабочий вариант. Если заранее неизвестно сколько цифр в наборе и каков их состав:

  
  combi:='';
  MainForm.ListBox1.Clear;
  for i:=1 to n do  //n-максимальная длина, тип Integer
    combi:=combi+s; //s-максимальное число тип Char. переменная combi строкового типа. например если нужно узнать сколько комбинаций в пятизначном числе (переменная n=5) состоящей из чисел от 0 до 3, то s='3';
  for i:=0 to StrToInt(combi) do begin
    a:=0;
    for j:=1 to Length(IntToStr(i)) do begin
      if (StrToInt(IntToStr(i)[j]) in [0..StrToInt(s)]) then a:=a+1;
    end;
    if a=Length(IntToStr(i)) then MainForm.ListBox1.AddItem(IntToStr(i),nil); // в ListBox1 записываем результат
  end;

Минус в том, что чем длиннее комбинация тем дольше считает. Например на пятизначную комбинацию состоящей из чисел от 0 до 3 тратиться время в несколько секунд. Этот код максимально подходит под мои личные задачи.

[Sibedir]

Например на пятизначную комбинацию состоящей из чисел от 0 до 3 тратиться время в несколько секунд

Не мудренно

if (StrToInt(IntToStr(i)[j]) in [0..StrToInt(s)]) then a:=a+1;

Наверняка можно и лучше сделать

Особо не вникал, но сразу навскидку могу посоветовать потратить пару лишних байт на локальные переменные. Скорость возрастет значительно.

  s1 := IntToStr(i);
  i1 := StrToInt(s);
  for j:=1 to Length(IntToStr(i)) do begin
    if (ord(s1[j]) in [0..i1]) then a:=a+1;
  end;

[Helen236]

uses crt;
const n = 4; { количество элементов в перестановке}
var a:array[1..n] of integer;
    j:integer;{счетчик}
    kol : longint;{количество перестановок}
procedure generate (l,r:integer;var k:longint);
var i,v:integer;
begin
if (l=r) then
  begin
    for i:=1 to n do write(a[i],' ');
    writeln;
    k:=k+1;
  end
else
  begin
    for i := l to r do
      begin
        v:=a[l]; a[l]:=a[i]; a[i]:=v; {обмен a[i],a[l]}
        generate(l+1,r,k); {вызов новой генерации}
        v:=a[l]; a[l]:=a[i]; a[i]:=v; {обмен a[i],a[l]}
      end;
  end;
end;
begin
clrscr;
for j := 1 to N do
a[j]:=j;
generate( 1,n,kol);
writeln('kol=',kol);
readln
end.

Что нужно изменить если дана строка символов (и числа и цифры)????