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

もう1つの答えは、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 に答える