8

我正在尝试编写一个函数，该函数将在输入上获取一个数组并返回数组数组，其中包含输入数组的所有可能子集（没有空元素的幂集）。例如对于输入：[1, 2, 3]结果将是[[1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]].

这个函数在 python 中完成了这项工作：

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

但我正在寻找在 Delphi 中实现它。这有可能以这种方式完成还是我应该寻找其他东西？

4

2 回答 2

6 
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;
于 2012-10-22T19:54:33.797 回答
2

我的另一个答案是我不久前在 Delphi 2007 中需要时创建的一段代码。为了使其更通用，您可以使用泛型。现在我以前实际上没有使用过泛型，但它似乎是这样工作的。我必须承认我不得不在这里偷看以检查语法。如果有更简单的方法，我希望其他人可以发布它。

除了输入参数的名称外，代码实际上并没有改变。（是的，泛型！）

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;

并像这样使用：

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]);
于 2012-10-22T20:13:51.260 回答