Zestaw mocy tablicy w Delphi

Question

Próbuję napisać funkcję, która zajmie tablicę na tablicę wejściową i zwrotną tablic, zawierającą wszystkie możliwe podzbiory tablicy wejściowej (zestaw mocy bez pustego elementu). Na przykład dla wejścia: [1, 2, 3] wynikiem będzie [[1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]].

Funkcja ta spełnia swoje zadanie w Pythonie:

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

Ale szukam wdrożenia jej w Delphi. Czy jest to możliwe do osiągnięcia w ten sposób, czy powinienem szukać czegoś innego?

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

Moja druga odpowiedź jest kawałek kodu stworzyłem jakiś czas temu, kiedy potrzebne w Delphi 2007. Aby uczynić go bardziej uniwersalne, można użyć rodzajowych. Teraz nie używałem generycznych wcześniej, ale wygląda na to, że działa tak. Muszę przyznać, że musiałem do peek here sprawdzić składnię. Jeśli jest łatwiejszy sposób, mam nadzieję, że ktoś inny może go opublikować.

Kod jest praktycznie niezmieniony, z wyjątkiem nazwy parametru wejściowego. (Yay, rodzajowych!)

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; 

i używać tak:

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]);