こんにちはゲストさん。会員登録(無料)して質問・回答してみよう!

回答受付中の質問

文字列を複数の段落に分割して出力

次のようなことを実現したいのですが、どのようなアルゴリズムになりますか?

------
文字列が複数ある。各文字列は改行コード(\n)で区切られた複数行の文字列からなる。
string[STR_NUM];// STR_NUM: 文字列数


これらの文字列をN段落に分けて出力したい。
ただし文字列の途中行で段落を変えない。
各段落の行数は最適値を求める。つまり、各段落に最も均等になるように振り分ける。

N=2でSTR_NUM=4の場合は次のような感じで出力する。

文字列1文字列1      文字列3文字列3文字列3
文字列1文字列1文字列1  文字列3文字列3
文字列1文字列1      文字列3文字列3文字列3
文字列1          文字列3
文字列2          文字列3文字列3文字列3
文字列2文字列2文字列2  文字列4文字列4
              文字列4文字列4
              文字列4文字列4文字列4
              文字列4

全体で15行あるので、均等に割ると1段落は8行となり、詰めて出力すると文字列3の2行目で改段落されることになります。そうならないように文字列3は2段落目の頭から出力します。

求めたいのは、Nとstring[0]~string[MAX_STR-1]が与えられたときの「1段落あたりの最大行数」と「各段落に出力する文字列」です。
各段落に出力する文字列は結合した状態で、かつ最大行数に合わせるように末尾に改行コードを必要数追加するものとします。
1段落あたりの行数の制限はありません。与えられた文字列によって最適な行数を求めます。

投稿日時 - 2017-10-13 23:18:55

QNo.9385560

困ってます

このQ&Aは役に立ちましたか?

0人が「このQ&Aが役に立った」と投票しています

回答(5)

ANo.5

> ちょっとよく意味が分からないのですが。この場合は7,7,7,27,1,1,1しか解はないように思えますが。先頭の行数を減らすとは?21,27,3,0,0,0,0も考えられますが、「均等に割り振る」という条件を付け加えると前者しか解がないと思います。

先頭3段の7行というのが、1段落で7行とは限りませんから、3 4 2 5 7 21 3なんて割り振りもあり得るということです。

投稿日時 - 2017-10-21 20:45:28

ANo.4

> 極端な例だと、文字列1が27行で残りが全て1行の場合、1段の行数は27行でなければなりません。つまり27,1,1,1と配分する必要があります。そのようなケースも含めた汎用的なアルゴリズムは書けるでしょうか。

端的に言うと書けません。
なぜなら、仕様がすべて出揃っていないからです。
あなたが出した例で、27行の段落の後が3行の段落1つだけだった場合はどうするのですか?
7段の場合に、先頭3段が7行、4段目が27行、5段目以降が1行になった場合は、そのままでいいのですか? それとも先頭の行数を減らしてバランスをとるのですか?
例外的な場合の対処方法が複数考えられるような処理に、汎用的なアリゴリズムは存在しません。

私がこのような処理をするとして、最初の方法がうまくいかないとわかったなら、次にスコアを付ける方法を試します。
考えられる分割方法全てに対して、分割された状態にスコアを付けます。好ましくない状態の度合いに応じてマイナスポイントを付与して、最もスコアが良い分割方法を採用します。
例えば、隣の段落との行数の差に応じてマイナスポイントを付与、0行の段は出来ればないほうがいいので-10000などの大きなマイナスポイントを付与、といったようにします。
テストを行って、好ましくない分割方法が採用される場合があれば、そのような状況の場合にマイナスポイントを付与する処理を追加していけば、採用される分割方法が改善されるでしょう。

投稿日時 - 2017-10-20 10:03:58

お礼

>あなたが出した例で、27行の段落の後が3行の段落1つだけだった場合はどうするのですか?

この場合は27,3,0,0とします。基本的に前詰めです。途中に空行の段があるのはバランス上良くないので、それ以外の選択肢はないでしょう。存在しないものは出力できないので、この場合は残りの2段が0行となるのは仕方ありません。

>7段の場合に、先頭3段が7行、4段目が27行、5段目以降が1行になった場合は、そのままでいいのですか? それとも先頭の行数を減らしてバランスをとるのですか?

ちょっとよく意味が分からないのですが。この場合は7,7,7,27,1,1,1しか解はないように思えますが。先頭の行数を減らすとは?21,27,3,0,0,0,0も考えられますが、「均等に割り振る」という条件を付け加えると前者しか解がないと思います。

>私がこのような処理をするとして、最初の方法がうまくいかないとわかったなら、次にスコアを付ける方法を試します

なかなか興味深い方法ですね。ただスコアの付け方に合理的な解はあるでしょうか?感覚的な数値ではなく、論理的に求めるのがアルゴリズムだと思うのですが。最大行数の段との差の合計値が最小になるのがベストですかね。

投稿日時 - 2017-10-20 12:32:55

ANo.3

N段の場合、各段に何行あるのが理想的かを先に決めて、理想的な行数と実際の行数の差が小さくなるように分割位置を決めていく方法がいいんじゃないでしょうか。
ただし、理想的な配置をきめる時に注意点があります。
まず、全行数が段数で割り切れない場合、単純に平均行数を四捨五入したりすると、最後の段にしわ寄せがいってしまいます。
例えば、全行数が30行で4段の場合、平均は7.5行ですが四捨五入で8行とすると、最後の段が6行になります。逆に切捨てだと他の段が7行なのに対して最後の段だけ9行になります。
30÷4=7余り2 と考えて、8行の段が2段、残りの段は7行と考えるといいと思います。
そして、そのような場合の段の配置方法が複数あります。
例の場合では、8 8 7 7や8 7 8 7、7 7 8 8、7 8 7 8など多くの組み合わせが考えられます。

投稿日時 - 2017-10-18 15:22:03

お礼

その8行と7行の組み合わせで常に可能とは限りませんよね。極端な例だと、文字列1が27行で残りが全て1行の場合、1段の行数は27行でなければなりません。つまり27,1,1,1と配分する必要があります。そのようなケースも含めた汎用的なアルゴリズムは書けるでしょうか。

投稿日時 - 2017-10-19 19:05:42

ANo.2

まずは各文字列が何行なのかを調べ、さらに全行数を調べる。
左の列にn行あるとすると、右の列は(全行数-n)行になる。
この差の絶対値が最小になる場合が求める場合となる。
順に、
(1) 左の列に「文字列1」だけがある場合の差の絶対値
(2) 左の列に「文字列1」と「文字列2」がある場合の差の設定値
 ・
 ・
 ・
を計算していって、どの場合に最小か調べる、というのが解法じゃないでしょうか。

例の場合、文字列の行数は4,2,5,4だから、
(1) |15-4*2|=7
(2) |15-(4+2)*2|=3
(3) |15-(4+2+5)*2|=7
なので、(2)、つまり左の列に文字列1と文字列2がある場合が最小(行の差が3)になります。

投稿日時 - 2017-10-16 17:47:02

お礼

ご回答ありがとうございます。
提示頂いたのは段数2の場合でしょうか?
一般にN段であった場合はどうなりますか?

投稿日時 - 2017-10-16 19:11:04

ANo.1

全体的に仕様があいまいな気がするのですが、そもそも「N段落」というけど段組のこと言ってますか?それとも本当に段落分けの話?

投稿日時 - 2017-10-14 00:06:42

補足

言葉が適切でなかったですかね。例を見て頂ければ分かるとおり、段組の話です。マルチカラムのことです。

投稿日時 - 2017-10-14 00:28:33