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?
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]);
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With