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?

It is certainly possible to do this (but the code will probably not be that brief in Delphi). — Andreas Rejbrand, Oct 22 '12 at 19:52
My answer here should help: http://stackoverflow.com/questions/8316479/combination-without-repetition-of-n-elements-without-use-for-to-do — David Heffernan, Oct 22 '12 at 19:53

GolezTrol · Accepted Answer · 2012-10-23T13:51:32.173

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;

I gave this method a shot and after some adaptation it just worked! Thanks, you are the best. — maciejjo, Oct 22 '12 at 22:19
TotalCombinations := 2 shl (TotalItems - 1); should be TotalCombinations := 1 shl TotalItems; — David Heffernan, Oct 22 '12 at 22:55
@DavidHeffernan Same result, but a little more logical. Changed it. — GolezTrol, Oct 23 '12 at 13:51

GolezTrol · Answer 2 · 2012-10-23T13:52:23.747

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

Power set of an array in Delphi

2 Answers2