1

だから...私は次のものを持っています：

.xml ファイルから取得されるいくつかのプロパティを持つクラス。これらのプロパティは、オブジェクトが条件 (2 つの子を持つ) であるかどうかとその名前です。基本的に、オブジェクトの子プロパティはその子の名前です。

.xml は次のようになります。

<object-2>
     <name>Object - 2</name>
     <yesChild>Object - 3</yesChild>
     <noChild>Object - 4</noChild>
</object-2>

noChild が空の場合、オブジェクトが条件ではないことを意味します。.xml から取得されたすべてのオブジェクトは、配列に格納されます。

私が必要としているのは、どうにかしてそこからツリーを作成し、配列の最後の要素に到達するために取ることができるすべてのパスを特定することです。アルゴリズムはすべてのノードをトラバースする必要はなく、配列の最後の要素に到達するために必要なノードだけをトラバースします。

例：

X1、X2、X3、X4 の 4 つのオブジェクトがあります。ここで、X1 は X2 と X3 を子として持つ条件であり、X1 で始まり X4 で終わる 2 つのパスがあります。パス 1: X1->X2->X4 パス 2: X1->X3->X4

ありがとうございました。

4

1 に答える 1

0

解析後のデータの形式が表示されないので、推測します :) 解析したデータを ruby​​ オブジェクトに格納する方法を次に示します (わかりやすくするために、新しいスタイルのハッシュ キー構文を使用します)。

[ {yes: 2, no: 3},
  {yes: 4},
  {yes: 4},
  {yes: -1} ]

次に、ツリートラバーサルを再帰的に行うことができます。配列の長さが数千要素でない限り、これは問題なく機能します。

def tree(object_number, list)
  if object_number == list.size
    [[object_number]]
  else
    list[object_number-1].values.map { |obj_num|
      tree(obj_num,list)
    }.inject{|a,b| a+b}.map{|l| [object_number] + l}
  end
end

次に、関数を呼び出します。

tree(1,data)
  => [[1, 2, 4], [1, 3, 4]]
data = [ {yes: 2, no: 3}, {yes: 4, no:5}, {yes:5, no:4}, {yes:5}, {yes: -1} ]
tree(1,data)
  => [[1, 2, 4, 5], [1, 2, 5], [1, 3, 5], [1, 3, 4, 5]]

仕組み:このリストを作成する最も簡単な方法は逆順です。すべてのパスの最後にたどり着いて初めてパスの数がわかるためです。したがって、このコードは参照を最後までたどり、最後のオブジェクトに到達すると、それを単一要素の 2 次元配列として返します。

tree(5,list)
  => [[5]]

再帰の各レベルで、再帰呼び出しの結果 (リストのリストとして返される) を取得し、内部リストのそれぞれに独自のオブジェクト番号を付加します。したがって、次のようにツリーをバックアップします。

tree(4,list) # prepends 4 to tree(5)
  => [[4,5]]
tree(3,list) # prepends 3 to tree(4) and tree(5)
  => [[3,4,5],[3,5]]
tree(2,list) # prepends 2 to tree(4) and tree(5)
  => [[2,4,5],[2,5]]
tree(1,list) # prepends 1 to tree(2) and tree(3)
  => [[1, 2, 4, 5], [1, 2, 5], [1, 3, 5], [1, 3, 4, 5]]

リストがスタックをオーバーフローするほど長くなる可能性がある場合は、再帰なしでこれを行うことが常に可能です。再帰は、この特定の問題に対する最も簡単な方法です。

于 2012-12-27T09:23:36.593 に答える