Leistungsset eines Arrays in Delphi

Question

Ich versuche, eine Funktion zu schreiben, die ein Array am Eingang nimmt und Matrix von Arrays zurückgibt, die alle möglichen Untergruppen von Eingangsarray enthält (Leistungsset ohne leeres Element). Zum Beispiel für die Eingabe: [1, 2, 3] wäre das Ergebnis [[1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]].

Diese Funktion macht die Arbeit in Python:

def list_powerset(lst): 
    result = [[]] 
    for x in lst: 
     result += [subset + [x] for subset in result] 
    result.pop(0) 
    return result 

Aber ich bin für die Umsetzung der in Delphi suchen. Ist dies möglich, oder sollte ich nach etwas anderem suchen?

Answer 1

type 
    TIdArray = array of Integer; 
    TPowerSet = array of TIdArray; 

function PowerSet(Ids: TIdArray): TPowerSet; 
// Implementation loosely based on the explanation on 
// http://www.mathsisfun.com/sets/power-set.html 
var 
    TotalCombinations: Integer; 
    TotalItems: Integer; 
    Combination: Integer; 
    SourceItem: Integer; 
    ResultItem: Integer; 
    Bit, Bits: Integer; 
begin 
    TotalItems := Length(Ids); 

    // Total number of combination for array of n items = 2^n. 
    TotalCombinations := 1 shl TotalItems; 

    SetLength(Result, TotalCombinations); 

    for Combination := 0 to TotalCombinations - 1 do 
    begin 
    // The Combination variable contains a bitmask that tells us which items 
    // to take from the array to construct the current combination. 
    // Disadvantage is that because of this method, the input array may contain 
    // at most 32 items. 

    // Count the number of bits set in Combination. This is the number of items 
    // we need to allocate for this combination. 
    Bits := 0; 
    for Bit := 0 to TotalItems - 1 do 
     if Combination and (1 shl Bit) <> 0 then 
     Inc(Bits); 

    // Allocate the items. 
    SetLength(Result[Combination], Bits); 

    // Copy the right items to the current result item. 
    ResultItem := 0; 

    for SourceItem := 0 to TotalItems - 1 do 
     if Combination and (1 shl SourceItem) <> 0 then 
     begin 
     Result[Combination][ResultItem] := Ids[SourceItem]; 
     Inc(ResultItem); 
     end; 
    end; 

end; 

Answer 2

Meine andere Antwort ist ein Stück Code, den ich vor einiger Zeit erstellt, als ich in Delphi 2007 in benötigt, um es genereller zu machen, können Sie Generika verwenden. Jetzt habe ich noch keine Generika benutzt, aber es scheint so zu funktionieren. Ich muss zugeben, ich musste peek here die Syntax überprüfen. Wenn es einen einfacheren Weg gibt, hoffe ich, dass es jemand anders posten kann.

Der Code ist tatsächlich praktisch unverändert, außer dem Namen des Eingabeparameters. (Yay, Generika!)

type 
    TGenericArray<T> = array of T; 
    TGenericPowerSet<T> = array of array of T; 

    TPowerSet<T> = class(TObject) 
    public 
    class function Get(a: TGenericArray<T>): TGenericPowerSet<T>; 
    end; 

class function TPowerSet<T>.Get(a: TGenericArray<T>): TGenericPowerSet<T>; 
var 
    TotalCombinations: Integer; 
    TotalItems: Integer; 
    Combination: Integer; 
    SourceItem: Integer; 
    ResultItemIncluded: Integer; 
    Bit, Bits: Integer; 
begin 
    TotalItems := Length(a); 

    // Total number of combination for array of n items = 2^n. 
    TotalCombinations := 1 shl TotalItems; 

    SetLength(Result, TotalCombinations); 

    for Combination := 0 to TotalCombinations - 1 do 
    begin 
    // The Combination variable contains a bitmask that tells us which items 
    // to take from the array to construct the current combination. 
    // Disadvantage is that because of this method, the input array may contain 
    // at most 32 items. 

    // Count the number of bits set in Combination. This is the number of items 
    // we need to allocate for this combination. 
    Bits := 0; 
    for Bit := 0 to TotalItems - 1 do 
     if Combination and (1 shl Bit) <> 0 then 
     Inc(Bits); 

    // Allocate the items. 
    SetLength(Result[Combination], Bits); 

    // Copy the right items to the current result item. 
    ResultItemIncluded := 0; 

    for SourceItem := 0 to TotalItems - 1 do 
     if Combination and (1 shl SourceItem) <> 0 then 
     begin 
     Result[Combination][ResultItemIncluded] := a[SourceItem]; 
     Inc(ResultItemIncluded); 
     end; 
    end; 

end; 

Und verwenden Sie wie folgt aus:

var 
    p: TPowerSet<String>; 
    a: TGenericArray<String>; 
    r: TGenericPowerSet<String>; 
begin 
    SetLength(a, 2); 
    a[0] := 'aaa'; 
    a[1] := 'bbb'; 
    r := p.Get(a); 

    ShowMessage(IntToStr(Length(r))); 
    ShowMessage(r[1][0]);