Power set of an array in Delphi

Question

I'm trying to write a function that will take an array on input and return array of arrays, containing all possible subsets of input array (power set without empty element). For example for input: [1, 2, 3] the result would be [[1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]].

This function does the job in python:

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

But I'm looking for implementation of it in Delphi. Is this possible to accomplish this way or should I look for something else?

Answer 1

My other answer is a piece of code I created a while ago when I needed in in Delphi 2007. To make it more generic, you can use generics. Now I haven't actually used generics before, but it seems to work like this. I must admit I had to peek here to check the syntax. If there's an easier way, I hope someone else can post it.

The code is in fact practically unaltered, except the name of the input parameter. (Yay, generics!)

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;

And use like this:

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