トーナメント表を描画するアルゴリズム

参加人数nを与えるとそれに応じたトーナメント表を自動的に描画したいと思っています。
トーナメント表というのは、甲子園とかでよくあるピラミッド状に勝ち上がっていくタイプのやつです。
参加人数がちょうど2の冪乗になるときだけを考えるなら力ずくでできそうなのですが、そうじゃない場合のときのことも考えるとめちゃくちゃ難しくて、調べてもなかなかわかりやすい情報もなく困っております。

とりあえず方針として思ったのが、ルートを決勝戦とする木構造のデータを、参加人数nを与えると返してくれるような関数ができればいいなと思いました。描画をどうするかはそれを元に後から考えればいいかなと。
しかし考えれば考える程行き詰ってしまい訳がわからなくなってきました。
どなたか何卒、できればコードそのまま書いてご教示いただけると大変助かります。
方針自体もこうした方がいいよとかあれば。
よろしくお願い致します。

hoshi-takanori

2020/12/27 04:37 編集

これじゃ丸投げですね。「参加人数がちょうど2の冪乗になるときだけを考えるなら力ずくでできそう」なら、まずそれをやってみて、できたソースを示すのがいいと思います。あと、方針としては、・データ構造を考えて、サンプルデータを作ってみる・そのデータを作るアルゴリズムを実装する・そのデータを描画するに分けて考えてみてはいかがでしょうか。

fana

2020/12/27 04:53

> めちゃくちゃ難しくて何が難しいのかを説明しないと，話が伝わらないのでは．（ルートから半々に分けていく話のどこにどのような難しさがあるのか）

KazukiKudo

2020/12/27 05:38

コメントありがとうございます。説明するのも難しいので諦めます。自分で頑張ります。見ていただきありがとうございました。

miyabi_pudding

2020/12/27 07:22

> できたソースを示すのがいいと思います。質問者さん、言葉で説明が難しければ、まずこれをやりましょう。まずやってみる、を、やらないと、いつまでもできるようにならないのがプログラミングの世界だと思います。

KazukiKudo

2020/12/27 09:01

正直色々書き殴ってわけがわからない状態なのでお見せできる状態でもないと思った次第です。完成したらここに貼ります。

行動規範の内容に同意します

回答1件

ベストアンサー

データ構造は JavaScript でワンライナーでできますね。

JavaScript
1f = (x) => x.length === 2 ? x : f(x.reduce((acc, x, i) => i % 2 === 0 ? [...acc,[x]] : [...acc.slice(0, acc.length - 1), [acc[acc.length - 1][0], x]],[]))

再帰使ってるのですぐスタックオーバーフローになっちゃいますが。

追記

すみません脳死で作ってたのでツリーが偏ります。まじめにやると。

JavaScript
1function build(xs){
2  if(xs === undefined || !Array.isArray(xs) || xs.length === 0){
3    return undefined
4  } else if(xs.length === 1){
5    return xs
6  } else if(xs.length === 2){
7    return xs
8  } else {
9    const i = Math.floor(xs.length / 2)
10    const inits = xs.splice(0, i)
11    const tails = xs.splice(i -i , xs.length)
12    return [build(inits), build(tails)]
13  }
14}
15
16ys = [...Array(10).keys()]
17console.log(build(ys))