2

次のような階層構造があります。

- 1 ( identifier = 100 )
  - 1 (101)
  - 2 (102)
  - 3 (103)
    - 1 (1031)
    - 2 (1032)
    - 3 (1033)
  - 4 (104)
    - 1 (1041)
    - 2 (1042)
    - 3 (1043)
  -901 (1001)
- 2 (200)
  - 1 (201)
  - 2 (202)
- 10 (1000)
  - 1 (1001)

必要な特性 :

  • 各ノードの識別子は一意である必要があります。
  • 識別子は、要素のレベルに応じて増加する必要があります
  • 識別子は整数型である必要があります。
  • 各要素のカウンターは、新しいレベル/親要素ごとにリセットされます

要素 1.901 と 10.1 の例でわかるように、現在の実装は機能しません。次の解決策を試しました：

  • 各レベルに数値を掛けます。
  • 最初のレベルのみに数値を掛けて、各子を追加します

識別子が文字列の場合ははるかに簡単になります。この場合、次の方法を使用できます: "level1.level2.level3..."、したがって 1 -> 1 の場合は "1.1" などになります。しかし、これは最も望ましくないステップです。

では、ここで必要な識別子を生成するために使用できるアルゴリズムを提案していただけますか?

更新例を修正しました。PS私はそれが間違っていることを知っていました。

4

3 に答える 3

3

あなたは 10 進数にこだわりすぎています。

  1. Xノード内の子ノードの最大数を表す値、または作業に便利な数よりも大きい値を選択します。
  2. 10 進数への固執をやめ、すべての識別子を base で表される整数として表しますX。
  3. X最初の桁がノード ツリーの最上位レベルを表し、2 番目の桁が 2 番目のレベルを表すというように、識別子を base の整数としてエンコードします。

したがって、運が良く、妥当な値Xが 16 であることが判明した場合は、整数の 16 進数表現を使用できます。36 が適切な値である場合は、任意の英数字を数字として使用してください。

編集

Rafael が指摘したように、ノードが持つことができる子の数の上限を定義できない場合、このアプローチは機能しません。私の経験では、これが実際に深刻な問題になることはまずありません。

の値Xが大きい場合は、base の各桁を表すために 3 桁の 10 進数のグループ863を設定して使用することを明らかに実装することをお勧めします。このようにして、識別子は として表されます。X = 1000100012.245.112245001

そして今、私たちはアレスタニスの答えですでにカバーされている領域に入りました

于 2012-10-30T14:12:15.130 に答える
1

この問題には、単純ですがメモリに関してコストのかかる解決策があります。

各ノード位置は、整数i（1）、i（2）、...、i（n）の一意の有限シーケンスとして簡単に表すことができます。

  • ノード1=[1]
  • ノード1.1=[1、1]
  • ノード7.2.42=[7、2、42]

したがって、質問は、整数の各有限シーケンスを一意の整数にマップする方法として表すことができます。それは素数を使って行うことができます

  • p（1）= 2
  • p（2）= 3
  • p（3）= 5
  • ..。

素数p（n）のi（n）：乗を掛けるだけです。結果の整数の一意性は、素数分解の一意性によって保証されます。ウィキペディアを参照してください：http： //en.wikipedia.org/wiki/Integer_factorization

例：

  • ノード1：2 ^ 1 = 2
  • ノード1.1：2 ^ 1 * 3 ^ 1 = 6
  • ノード7.2.42：2 ^ 7 * 3 ^ 2 * 5 ^ 42 =（膨大な数！）

別の可能な解決策

ノードの文字列表現から始めます（例：「7.2.42」）。ノードの番号付けには8進数を使用します。「。」の代わりに「8」（8進数の最初の未使用の数字）を使用してレベルを区切ります。結果の文字列を10進整数として使用します。

例：

  • ノード1：1
  • ノード1.1：181
  • ノード1.2：182
  • ノード1.3：183
  • ノード7.7.7：78787
  • ノード8:10
  • ノード8.1：1081
  • ノード8.2：1082
  • ノード8.9：10811
  • ノード8.9.1：1081181
  • ノード8.9.2：1081182
于 2012-10-30T15:08:59.640 に答える
1

まず第一に、あなたの例は間違っています (100 は識別子 10000 にマップされます) が、これはそれが機能するという意味ではありません。理由は次のとおりです。

- 1 (100)
  -1 (101)
  ...
  -100 (200)
- 2 (200)

実用的な例が必要なのは、実際に各レベルに数値 N を掛けるか、同じように、各レベルに X 桁を予約することです。あなたの場合、 を選択N = 100したので、例を機能させるために必要な追加の制約は、各レベルがchildrenを超えることはできないということN-1です。

この制約を適用すると、要素 1.100 が無効になり、重複する識別子が排除されます。

N = 100(または)を使用すると、次のX = 2結果が得られます。

- 1 (01)
  - 1 (0101)
    - 1 (010101)
    ...
    - 3 (010103)
  ...
  - 99 (0199)
  - 100 is ILLEGAL
- 2 (02)
- 42 (42)
  - 42 (4242)

その場合の「問題」は、ユーザーを制約することなく必要な桁数を最小限に抑えるように賢明に選択することです。Xたとえば、450 を超える子を追加しないことがわかっている場合は、 を選択しますX=3。

于 2012-10-30T13:44:25.367 に答える