besondere Permutation, keine Anagramme!

[senF_77]

Hallo DPler!

Ich sitze hier vor einem großen Problem: Ich habe einen Array of Word und ich möchte testen, ob ich mit der Addition beliebiger Zahlen diese Arrays eine bestimmte Zahl darstellen kann.

Zitat:

zB: Array of Word = (1, 2, 3, 4, 10, 16, 21)
zu findende Zahl: 30 (2 + 3 + 4 + 21)

jetzt habe ich mir überlegt, mit dem Array viele Permutationen zu erzeugen und zu überprüfen ob diese zusammengezählt die gesuchte Zahl ergeben. Das Problem ist, dass alle bisher gefundene Permutationen nur die verschiedenen Kombinationsmöglichkeiten des Arrays zeigen.

Zitat:

zB: Permutation von 1, 2, 3 =
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Das Problem bei dieser Permutation ist aber, dass die Summe stets die Selbe bleibt!
Ich bräuchte aber als Resultat sowas wie

Zitat:

Permutation von 1, 2, 3 =
1 2 3
1 2
1 3
2 3
1
2
3

(Dabei sind hier doppelte bereits eleminiert (2,1) = (1,2) ).

Kann mir jemand vieleicht einen Denkanstoß geben wie ich dieses Problem löse?

[Edit: oooops was vergessen :-D ]

[Dax]

Solange dein Array weniger als 65 Zahlen beinhaltet, kannst du dich eines Tricks bedienen:

Delphi-Quellcode:

type
  TIntArray = array of Integer;

var
  Mask: Int64 = 0;
  Numbers: TIntArray;

function NextPermutation: TIntArray,
var i: Integer;
begin
  SetLength(Result, 0);
  Inc(Mask);
  for i := 0 to High(Numbers) do
    if (Mask shr i) and 1 <> 0 then
    begin
      SetLength(Result, Length(Result)+1);
      Result[High(Result)] := Numbers[i];
    end;
end;

Dabei ist Mask der eigentlich trickreiche Teil, hier wird kodiert, welche Zahlen im Ergebnis enthalten sind. Da Mask nur 64 Bits hat, für jede Zahl in Numbers eins, kann Numbers nur 64 Elemente lang sein. Bei jedem Schritt wird Mask um 1 erhöht und dann die nächste Permutation erzeugt.

Wenn du das mit beliebig großen Arrays machen willst, brauchst du eine Möglichkeit, mit beliebig langen Zahlen zu hantieren. Dabei werden nur zwei Anforderungen gestellt: eine Zahl muss inkrementierbar sein und man muss beliebige Bits der Zahl inspizieren können. Die Implementierung einer solchen Klasse ist eine Übungsaufgabe ;)

[senF_77]

Wow Danke!

Die Funktion ist genial!

Nur noch eine kleine Frage: gibt es eine Möglichkeit herauszufinden, wie oft ich die Funktion aufrufen muss? Mir fliegt irgendwas mit Bernoulli und Fakultät im Kopf herum, aber was es genau ist kann ich nicht sagen :roll:

[EDIT: Ist doch einfach nur die Fakultät der Anzahl der Elemente :-D ]
[EDIT2: Doch nicht :? ]

[Sergej]

Also solch eine Aufgabe löst man im Allgemeinen mittels Backtracking.

[Dax]

Um alle derartig geformenten Permutionen zu bekommen, ist die notwendige Zahl der Aufrufe Length(Numbers) * Length(Numbers). Das ist auch recht einfach ersichtlich, schließlich werden Length(Numbers) Bits in der Maske belegt, die von (alle Bits 0) bis (alle Bits 1) läuft.

Zitat:

Zitat von Sergej

Also solch eine Aufgabe löst man im Allgemeinen mittels Backtracking.

Das geht natürlich auch, aber bei dieser Methode ist es einfacher, zwischendurch abzubrechen, und die Funktionsweise ist (fast) sofort ersichtlich.

[alzaimar]

Eins vorneweg: Wir wollen alle Variationen der Länge 0..N erstellen.

Ob man nun alle Möglichkeiten durchiteriert, oder das Problem rekursiv löst, kommt aufs Gleiche raus. Ich vermute aber, das der iterative Ansatz hier langsamer sein könnte, weil man jedesmal eine mögliche Lösung von Grund auf zusammenbaut. Das Prinzip mit der Bitmaske lässt sich aber so abwandeln, das die Zahlen anhand des Bitmusters summiert werden, und erst im Erfolgsfall die Lösung zusammengebastelt wird. Bei mehr als 64 Zahlen wird die Lösung aber sehr umständlich.

Dax irrt aber bei der Anzahl der Aufrufe, denn wir benötigen nicht N*N, sondern 2^N Aufrufe. (N=3, das sind 3 Bits und somit Zahlen 0..7, also 8 Stückerl)

Ich bevorzuge rekursive Lösungen, alleine deshalb, weil sie i.a. kompakt und eleganter sind (was immer das sein mag). Es ist aber letztendlich Geschmackssache. Auch finde ich sie einleuchtender, da sie den kombinatorischen Lösungsansatz direkt algorithmisch umsetzen.

Der Umweg über die Bitmaske ist wirklich trickreich, aber um die Ecke gedacht. Mit fehlender Eleganz hat das aber nicht zu tun, ganz im Gegenteil. Und wer vermutet schon Bitmasken in Verbindung mit der Erstellung aller Variationen.

Hier mein Senf:

Delphi-Quellcode:

  
Procedure FindeSumme(Const N : Array Of Integer; Const S : String; I0, T, X : Integer);
Var
  I : Integer;

Begin
  If T = X Then
    Form1.Memo.Lines.Add(S) // Lösung gefunden (Ausgabe häßlich, da Komma am Ende der Lösung...)
  Else
    For I := I0 To High(N) Do 
      If T + N[I]  <= GesuchteSumme Then
        FindeSumme(N, S + IntToStr(N[I]) + ', ', I + 1, T + N[I], X)
End;

...
  FindeSumme([1, 2, 3, 4, 10, 16, 21], '', 30);
...