Kombinatorik - Index von Kombinationen

[Michael II]

Hallo APro,

wenn du für ein gegebenes n und ein Element intar:array of integer den Index ermitteln willst, dann könntest du es so tun:

Delphi-Quellcode:

type Tintarray = array of integer;


function indexvon( n : integer; intar : Tintarray ) : integer;
var hi, i, j, ind, k, firstel : integer;
begin
  ind := 0;
  k := length( intar );

  for hi := 0 to k-1 do
  begin
    firstel := intar[hi];
    for i := 0 to firstel-1 do inc( ind, tief( n-i-1, k-hi-1 ) );
    for j := hi+1 to k-1 do intar[j] := intar[j]-firstel-1;
    n := n-firstel-1;
  end;

  Result := ind;
end;

Wenn du umgekehrt für gegebene n, k und einen Index das Element ermitteln möchtest, dann kannst du es so tun:

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;
    firstel := i-1;
    ind := lastind;
    intar[hi] := firstel;
    if hi > 0 then inc(intar[hi], intar[hi-1]+1 );
    n := n-firstel-1;
  end;

  Result := intar;
end;

Testen kannst du die ganze Sache so:

Delphi-Quellcode:

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

begin
   // zum Beispiel für deinen Fall n=5, k=3:
  n := 5;
  k := 3;

  SetLength( ar, k );

  anzahlelemente := 0;
  for i := 0 to n-k do inc( anzahlelemente, tief( n-i-1, k-1 ) ); // so viele Elemente enthält deine "k aus n Liste"

  // wir testen alle Fälle durch:
  for i := 0 to anzahlelemente-1 do
  begin
      ar := get_elem_fromindex( n, k, i ); // wir ermitteln aus dem Index das Listenelement
      test := indexvon( n, ar ); // für gegebenes n und Element ar wird der Listenindex berechnet
      if i <> test then Showmessage( 'fehler' );
  end;
end;

Im Code oben gilt:
tief(n,k) = n!/k!/(n-k)!

Der Code lässt sich sicher schöner schreiben - ich hatte es etwas eilig .