Kombinatorik - Index von Kombinationen

[Michael II]

Delphi-Quellcode:

var hsum : array[0..64, 0..7] of integer;
// Summen berechnen

procedure berechnesummen;
var n, k : integer;
begin
  for n := 0 to 64 do
    for k := 0 to 7 do
    begin
      if ( k=0 ) or ( k=n ) then hsum[n,k] := 1
      else
      hsum[n,k] := hsum[n-1,k-1] + hsum[n-1,k];
    end;
end;


function indexvon2( n : integer; intar : Tintarray ) : integer;
var i, ind, k : integer;
begin
  ind := 0;
  k := length( intar );
  for i := k-1 downto 1 do intar[i] := intar[i]-intar[i-1]-1;

  for i := 0 to k-1 do
  begin
    inc( ind, hsum[n,k] - hsum[n-intar[i],k] ); // [3]
    dec( k );
    n := n - intar[i] - 1;
  end;

  Result := ind;
end;

Hallo Apro

hier noch eine sehr schnelle Art zur Berechnung (keine Multiplikation, Aufwand nur abhängig von k) der Indices (siehe oben : indexvon2). Viel schneller geht's wohl nicht.

In der vorher geposteten Lösung wurden Summen wie zum Beispiel
[1] tief(n-1,k-1) + tief(n-2,k-1) + ... tief(n-a,k-1) immer wieder neu berechnet. (Die innere Schleife).

In indexvon2 wird jetzt ausgenutzt, dass Summe
[2] tief(n-1,k-1) + .... + tief(k-1,k-1) = tief(n,k).

Du kannst also [1] berechnen, indem du von [2] die Summe tief(n-a-1,k-1)+...+tief(k-1,k-1) abziehst. Im Code oben mit [3] markiert.


Wie erwähnt: Für feste n,k kannst du indexvon2 direkt durch Einsetzen der festen Werte vereinfachen.

Delphi-Quellcode:

procedure TForm126.Button1Click(Sender: TObject);
var ar : TINtArray;
    anzahlelemente,
    test, i : integer;
    n, k : integer;

    hs : TStringList;
    xs : string;
  x: Integer;

begin
  hs := TStringList.Create;

  n := 20;
  k := 5;

  berechnesummen; // Summen werden nur einmal berechnet

  SetLength( ar, k );

  anzahlelemente := tief( n, k );

  for i := 0 to anzahlelemente-1 do
  begin
      ar := get_elem_fromindex( n, k, i );

      xs := '';
      for x := 0 to k-1 do xs := xs + ar[x].ToString + ' ';
      xs := i.ToString + ' ' + xs;
      hs.Add( xs );

      test := indexvon2( n, ar );
      if i <> test then Showmessage( 'fehler' );
  end;

  hs.SaveToFile( 'C:\Users\Michael\Desktop\check.txt' );
  hs.Free;

end;

Viel Spass.

Gruss
M


Ach ja... der umgekehrte Fall Index -> Array Element liesse sich natürlich auch vereinfachen... im oben geposteten Code hatte es noch einen kleinen Bug. Korrekt ist:

Delphi-Quellcode:

function get_elem_fromindex( n, k, index : integer ) : Tintarray;
var lastind, hi, i, ind, firstel : integer;
    intar : TIntArray;
begin
  ind := 0;
  Setlength( intar, k );

  for hi := 0 to k-1 do
  begin
    i := 0;
    repeat
      lastind := ind;
      inc( ind, tief( n-i-1, k-hi-1 ) );
      inc(i);
    until ind >= index;

    if ind > index then
    begin
      firstel := i-1;
      ind := lastind;
    end
    else
    begin
      firstel := i;
    end;

    intar[hi] := firstel;
    if hi > 0 then inc(intar[hi], intar[hi-1]+1 );
    n := n-firstel-1;
  end;

  Result := intar;
end;