Perlでツリー構造を生成

質問

質問です。

Perlで以下のような処理をしたい場合どういうコードを書けばよいでしょうか
処理の内容を簡単に説明しますと、
店舗情報を格納しているDBがあるとします。
DBから取得した、X件の情報を、子がN店ずつのツリー構造にした上で、DBの取得してきたレコードに親の店舗IDなりを更新するスクリプトです。
親が1店舗からはじまり、子がN店の構成です、子はその下に孫としてまたN店もちます。

分かりづらいですね・・・もう少し細かく説明します。

1.DBから店舗情報を取得してくる
2.10件の店舗があったとする、IDがshop1,shop2,shop3...shop10と続く
3.その中からランダムで一件決める。今回はshop3とする
4.ランダムでshop3の子をN件決める。今回はshop3の子をshop1とshop2とする(N = 2とする)
6.今度はshop1とshop2の子を決める(残りのshop4～10より決める)
7.4の処理に戻り、孫世代、ひ孫世代を決定する
8.端数は一人っ子ができても問題なし、子なしに落ち着くまで繰り返す
9.すべての店をチェックして親をレコードに更新する。

といったような流れの処理になります。
処理の流れは浮かんでいるのですが、Perlでどう書けばいいのか四苦八苦しています。
(自分のIDと親のIDを結びつけつつ保持し続けておくのがとくにわかりません・・・)

以上になりますがよろしくおねがいします

回答No.3

Tacosan

もちろん店舗ID から直接「その親店舗」を見付けることはできません. が, どんな方法を使っても結局のところ「なんらかの補助的な情報」は必要です.
とはいえ, その「補助的な情報」そのものを店舗ID から調べることができればいいわけで, 端的には
map { $index{$ID[$_]} = $_; } @ID;
としてしまえば「店舗ID」と「配列 @ID に対する添字」を相互変換することができます.
つまり, 店舗ID が $ID であるような店舗の親店舗は $ID[int(($index{$ID}-1)/N)]
で得られます... 多分.

回答No.2

Tacosan

最後の「端数」をどう処理するかによりますが, ヒープに類似の方法が使えるかもしれません.
つまり, 配列 @ID に店舗ID があるとして $ID[0] を最上位の店舗とします. あとは
・店舗$ID[i] の子店舗は $ID[i*N+1]～$ID[i*N+N]
という形で親子関係を割り当てていきます. 逆にいうと
・店舗$ID[i] の親店舗は $ID[(i-1)/N]
です.
最初に書いたように「端数」の処理が分からないのですが, これでいいなら「配列をランダムな順番にシャッフルするだけ」で処理が終わります.

お礼

ありがとうございます！
うまくやればシンプルにまとめられそうですね
この路線でも考えてみたいと思います

端数については左詰め？というか、店舗がすべて家族関係に含まれた時点で終了という感じで考えています

補足

すみません、補足です
ちなみにこの方法だと世代数がわからないと
結局どの一つ一つのIDに対して親を指定できないような気もするのですが、正しいでしょうか？

回答No.1

z_liang_00

突貫で作ったのであちこち格好悪いのですが、
とりあえずそれっぽく出ています。
最後の$treeに入っている情報をＤＢに格納してください。

再帰にしたら一方の枝ばかり深くなってしまったので、
階層という考え方にしてみました。
コメントはたくさん入れたつもりですが、
質問などありましたら、補足をつけてください。

#-------------------------------------------------
# お店の名前リスト（これはＤＢの情報からなんとか作ってください）
my @shops = ('shop0', 'shop1', 'shop2', 'shop3', 'shop4',
　　　　　　 'shop5', 'shop6', 'shop7', 'shop8', 'shop9');

my $N = 2;　　　　　　　　　　　# 探したい子どもの数

# お店の名前をハッシュリストにする
my %sp;
map { $sp{$_} = 1; } @shops;

my %layer = ();　　　　　　　　 # お店の階層を入れるリスト
my $level = 0;　　　　　　　　　# 階層番号

my $top = &choiceShop(\%sp);　　# ランダムに１件
$sp{$top} = 0;　　　　　　　　　# もう選択済みだよのしるし
$layer{$top} = $level;

# 全部のお店に階層番号を付ける
for($level++ ; ; $level++) {
　my @sel;
　# $Nの階層乗の数の枝が必要
　#　 例) $N=2 なら 2階層目なら4件, 3階層目なら8件
　map { my $s = &choiceShop(\%sp);
　　　　if($s){　　　　　　　　　　 # 見つかったら
　　　　　　push(@sel, $s);　　　　 # 枝リストに保存
　　　　　　$layer{$s} = $level;　　# 見つけられた階層番号を入れる
　　　　　　$sp{$s} = 0;　　　　　　# 選択済みだよのしるし
　　　　}
　} (1..$N**$level);
　last if(scalar(@sel) == 0);　 # 未選択のショップがないなら終了
}

# 親子関係を入れるリスト
# $tree{子どものショップ} = 親のショップ
my %tree = ();

# 階層番号が上のものと下のものをマッチングさせて親子関係ぽくしていく
for($level=0 ; ; $level++) {
　my @parent = grep {$layer{$_} == $level} keys %layer;
　my @children = grep {$layer{$_} == ($level+1)} keys %layer;
　last if(scalar(@children)==0); # マッチングすべき枝がないなら終了

　for(my $i=0 ; $i<scalar(@parent) ; $i++) {
　　for(my $j=0 ; $j<$N ; $j++) {
　　　my $c = shift(@children);
　　　$tree{$c} = $parent[$i] if $c;
　　}
　}
}

# 結果：親子関係を表示してみましょう
print map { $_.' の親は '.$tree{$_}." です。\n" } keys %tree;

# ランダムに未選択のショップを選択
sub choiceShop(\%) {
　my $shoplist = shift;
　# 未選択のショップ
　my @shops = grep { $shoplist->{$_}==1 } keys %$shoplist;
　# その中からランダムに１件
　return $shops[int(rand(scalar(@shops)))];
}

お礼

ありがとうございます！
そしてお返事遅くなってすみません
何度も読み直しているのですがまだ完全には理解できていません・・・

とりあえずテストしつつものにしたいと思います

ちなみに恰好悪いというのはどのあたりのことなのでしょうか