1

私はPythonでこの問題を解決したいのですが、私はこの問題のためにDelphiで立ち往生しています。ネストされたリスト（実際にはネストされたリストをプロパティとして持つオブジェクトですが、気にしないでください）があり、ジェネレーター方式でそれらを反復処理したいと思います。つまり、ネストされたリストによって記述されたツリーの葉から次のアイテムを取得するNext関数を作成します。

たとえば、私が持っているとしましょう

 [[1,2,3],[4,5],[],[6],[7,8]]

Next（）を8回連続して呼び出して、1..8を返すようにします。

イールドとジェネレーターのない言語でこれを行うにはどうすればよいですか？

ネストの深さは固定されていますが（この例では2、実際には4）、深さが可変であるより一般的なケースを解決する答えは歓迎されます。

編集：申し訳ありませんが、これはDelphi2007です。

4

3 に答える 3

2

ビルトインの列挙子を持つ Delphi リストを使用している場合は、少し再帰するだけで簡単に実行できます。ベースリストは、 のような数字のリストですTList<integer>。次に、として実装されたネストされたリストがありますTList<TList<integer>>。(Delphi 2009 または 2010 を使用していると仮定しています。そうでない場合は、少しトリッキーになります。)

必要なのは、独自の特殊なリスト クラスを作成し、そこTList<T>に仮想の Next() 関数を追加し、リストの列挙子のフィールドを追加することです。for..in ループを設定すると、コンパイラは内部的に列挙子を使用しますが、手動で実行することもできます。Next() 関数は、まだ割り当てられていない場合は列挙子を作成し、それをフィールドに配置してから、MoveNext() を呼び出します。これが成功したら、GetCurrent を呼び出して番号を取得します。それ以外の場合は、完了です。列挙子を FreeAndNil にして、呼び出し元の関数に返すものが何もないことを知らせます。おそらくこれを行う最も簡単な方法は、MoveNext への呼び出しの結果を返すvar boolean パラメーターを Next() に配置し、呼び出し元の関数にその値をチェックさせることです。

上位のリストの場合は、もう少し複雑になりますが、大したことではありません。設定したジェネリック クラスから派生し、Next() をオーバーライドします。これは、保持しているリストを列挙する列挙子を取得し、FEnumerator.GetCurrent.Next()そのサブリストがなくなるまで値を返し、その列挙子で MoveNext を呼び出します。

これは、ネストされたリストの任意の深さで機能するはずです。数字とリストの両方を含むリストを作成しようとしないでください。

于 2009-10-08T15:09:05.580 に答える
0

方法1：「階層化リスト」はツリーであり、ツリー/ツリーノードクラスを使用（または書き込み）し、その値の単純な深さ優先探索を実行します。

方法2：階層化リストタイプの深さ優先探索を明示的に記述します：

TEnumerator = RECORD
  private
    FStack : Stack of TNestedList;  //a stack, holding which level of the tree you are exploring
    FIndexStack : Stack of Integer; //a twin stack, holding the index of the child you are exploring at each layer

  public
    Init( AList : TNestedList );
    Next( var AVal : Integer ) : boolean;
end;


procedure TEnumerator.Init( AList );
begin
  SetLength(FStack, 1);
  FStack[0] := AList;
  SetLength( FIndexStack, 1 );
  FIndexStack[0] := 0;

  _GoToNextValue();
end;

procedure TEnumerator._GoToNextValue();
begin
  while FStack.notEmpty()
    and FIndexStack.last > FStack.last.length do
     begin
     //we have finished exploring FStack.last, we need to explore its next sibling :
     //pop FStack.last :
       FIndexStack.pop;
       FStack.pop;
     //go to next sibling :
       FIndexStack.last := FIndexStack.last + 1;
     end;

  //nothing left to explore :
  if FStack.empty then Exit;

  //else :
  //  dig through the layers of list until you reach a value
  while FStack.last.isAList() do
  begin
    FStack.push( FStack.last[ FIndexStack.last ] );
    FIndexStack.push( 0 );    
  end;
end;

function Next( var AVal : Integer ) : boolean;
begin
  _GoToNextValue();

  Result := FStack.notEmpty();

  if Result then
  begin
    AVal := FStack.last[ FIndexStack.last ];
    FIndexSatck.last := FIndexSatck.last + 1;
  end;
end;

基本的に、「yield」が行うことを明示的に行います（つまり、呼び出しスタックの「フリーズコピー」を保存し、現在の値を返します）

使用法 ：

LEnum : TEnumerator;

LEnum.Init( myList );
while LEnum.Next( LVal ) do
begin
  <do something>
end;
于 2009-10-09T14:11:06.150 に答える
0

この問題を解決するために、私はインデックスのフラットリストを作成し、その中の自分の位置を覚えていました: (pythonesque では、短いため)

class Nested:
    nestedList = [[1,2,3],[4,5],[],[6],[7,8]]
    positions = []
    curr = 0

    def Setup:
        for a in nestedList:
            for b in a:
               positions.add((a,b))

    def Next:
        p = positions[curr]
        curr += 1
        return nestedList[p[0]][p[1]]

明らかに、反復中に私のリストが変更されないか、これはおそらく機能しません...

于 2009-10-23T11:39:07.717 に答える