最近、Ruby信者をいろんなスレで見かけるのは、Rubyが下火になっているからか
多言語の機能を取り込むのは良いことだが、機能に拘るのは偏食と変わらないな

文字列が入った配列（例として["aaa","aaa","bbb","bbb","ccc","ccc",…以下1000個ほど続くとする]）があるとして、
この配列を「できるだけ似た文字列が並ばないように」並び替える方法ってどんなものが考えられますか？
つまり["aaa","bbb","ccc","aaa","bbb","ccc",…] となるように並べ替えたいです
言い換えれば「できるだけ似てない文字列が隣合って並ぶように」バラけさせるアルゴリズムです
レーベンシュタイン距離でというのも考えましたが「1つ前の文字列からもっとも遠い文字列を」短絡的に並べていくのでは、上記の例でいうと
["aaa","ccc","aaa","ccc","bbb","bbb",…]
というふうに、もっとも遠い文字列を使い果たした後はむしろ近いものが並んでしまうのではないかと危惧してます

もっと要件詰めなよ。仕事でそんな発注するんじゃないぞ。

ソートして半分に割って一個ずつ取り出し並べていけば良いんじゃね

>>153
「似た文字列」を定義する事から始めては？

「似た文字」は文字の類似度を数値で返す関数がある
という前提でいいだろ

じゃあsortにその関数使ったコンパレータぶっ込んで終わり。
はい次。

>>153
レーベンシュタイン距離でいいんじゃないか？

1. 同一文字をまとめて、ユニークな文字列の値、出現回数をまとめた配列(or Map)を作る
2. 隣接要素のレーベンシュタイン距離がしきい値を越えるように並べ替える
3. 1周する
4. 各要素の出現回数を -1
5. 全要素が出現回数0なら終了。一部に出現回数0があったら、2.へ、それ以外は3.へ

>>153
例えば100通りランダムに並び替える
その中で10個距離が短いのを選んでそれぞれ10通りランダムに少量だけ並び替える
その繰り返しでいい

>>158
素朴な疑問なんだけど、Array#sortって隣接要素の判定条件を指定出来るの？
2つの要素が似た文字列だった場合に引き離す機能がないと実装出来ないと思うんだけど

巡回セールスマン問題か？

例えば範囲が、1～100 なら、

1, 100, 2, 99 みたいに取っていくと、
最後には、50 近辺の数字ばかりが残るから、ダメ！

無数のアルゴリズム・シミュレーションを繰り返して、
合計距離が多くなるように、しないといけない

// 出現回数は考慮しないものとする
// 小文字アルファベット a-z から選ぶものとする
const length = 100
const threshold = 10
let a = []
let place = []
let aryResults = []

for (let i = 0; i < 26; i++) {
let strTmp = String.fromCharCode(0x61 + i)
a.push(strTmp)
place.push(-threshold)
}

for (let i = 0; i < length; i++) {
let t = i - threshold
let setTmp = new Set(a)
for (j = 0; j < 26; j++) {
if (place[j] > t) { setTmp.delete(a[j]) }
}
const arrTmp = [...setTmp]
let x = (Math.random() * arrTmp.length | 0)
place[x] = i
aryResults.push(arrTmp[x])
}
console.log(aryResults)

>>153
うーん
定性的な部分をどうにかしないと書けないな


「似た文字列」
何をもって「似ている」と判断するか基準不明

「できるだけ似た文字列が並ばないように」
→どの範囲で許されるのか

高田馬場1丁目1番地、2番地…
高田馬場2丁目1番地、2番地…
高田馬場3丁目1番地、2番地…
高田馬場4丁目1番地、2番地…
高田馬場5丁目1番地、2番地…

西早稲田1丁目1番地、2番地…
西早稲田2丁目1番地、2番地…
西早稲田3丁目1番地、2番地…
西早稲田4丁目1番地、2番地…
西早稲田5丁目1番地、2番地…

とかなら、まだ分かりやすいだろうけど（高田馬場m丁目と西早稲田n丁目の遠近は度外視として）

>>165
その問題は>>159で解決してるんじゃないか？

厳密には、先頭/末尾の繋ぎが未チェックという問題が残っているが…
2.のソート時に繋ぎを意識したsortにして、5.から2.へ行く前に直前要素と先頭要素を比較する処理を入れてやれば良さそうだ

Set 使えば登場回数ゼロはありえないだろ

>>170
>>153ではaaa,bbb,cccが何度も登場してる
そもそも、重複がなかったら、この質問は成立しないわけで

>>171
それなら >>164 のように完全ランダムにするか、
3つの順列をセットとして 3P3 = 3! = 6通りから、末尾の文字と異なる文字で始まるモノで並べて行くか

完全ランダムだと残り物にバラつきが出すぎる可能性はあるけど


3つの順列で心配なら
a - b - a - c - b - c
a - b - c - a - b - c
a - b - c - b - a - c
a - b - c - b - c - a
（以下省略）
とかいう組み合わせを事前に作っておいて並べて行けば良いんじゃね


バラつき具合の判別方法は知らんけど…

難しく考えすぎ
期待値に達するまで適当に振り分続ければいいだけ
あとはその振り分けアルゴリズムが完全なランダムより賢ければ賢いだけコストが減る
それを十分な状態になるまで追求すればいいだけ

>>173
振り分けアルゴリズムの質問にその回答はなかろうて

「ナップサック問題」でも「全検索」は解の1つ
エレガントではないかも知れないが、不正解という評価は誤り

http://postd.cc/programmer-competency-matrix/

いきなり「レーベンシュタイン距離」と書いたとしても、他の人に理解されるとは限らん…
元質問者の場合はそうではないようだが

こういう時は発送を逆転させる
つまり良い分配アルゴリズムではなく、悪い整頓アルゴリズムを考える
それで思いつくものを現実的な妥協点として良いと思う
そういう意味ではランダムは悪くない

最初ランダムで走査して固まってる部分があったら適当に入れ替えてほぐす
その繰り返しはどうだろうか？

レーメンはじめました

>>171
配列を splice() すれば良かろう
人にケチ付けてる暇があったら改善案出せよ無能

>>175
> 「ナップサック問題」でも「全検索」は解の1つ

「全検索 アルゴリズム」でぐぐっても見つからないが、もしかして「全探索」といいたかったのか？
全探索は「全ての組み合わせを試す」というもので、1000個の要素なら、最大試行回数=1000*999*998*...*3*2*1回となる力業

> エレガントではないかも知れないが、不正解という評価は誤り

>>173は「失敗したらやり直す」なので「全探索」とは違う
「振り分けアルゴリズム」に欠陥があれば、永久に失敗するので無限ループとなるし、アルゴリズムの成功確率が低ければ、試行回数は全探索よりも高くなる可能性が高い
アルゴリズムに欠陥がない場合の最大試行回数は「1～∞回」で運要素の高い方法

>>180
>>170は

> Set 使えば登場回数ゼロはありえないだろ

とケチをつけたが、>>159の回答を咀嚼すれば「登場回数」がそういう意味ではないことが分かるはずなので、それを指摘しただけ

> 人にケチ付けてる暇があったら改善案出せよ無能

これは>>170にいいたい

>>181
>>173は失敗したらやり直すのとは違うでしょ
遺伝的アルゴリズムと言ったら大げさだけど、モンテカルロ法で円周率を求めるのと同じくこの手のアルゴリズムは運任せでも現実的には収束していくんだから
この手のアルゴリズムで不運が重なって想定よりも遥かに時間がかかる事を想定するのは、計算中にマシンが突然クラッシュしたりビットアップセットを起こしたりするのを心配するようなもの
最善でなくても一定の期待値を越えれば良いというときには良いアルゴリズムだよ

>>181
1000は無いだろ

選択肢3つなんだから、たとえば1002個あったと仮定して、
同じ選択肢が決して連続しないのは大前提だろ
「できるだけ似てない文字列が隣合って並ぶように」って言ってんだから

ケチばっか付けた挙句完全に誤ったこと書いてんじゃねえよ無能

なんで選択肢が3つだけだと思ったんだろう…

ランダムに(または、ルールで制限しつつ)シャッフルして、
許容回数実行して、最善のものを選ぶ

最良のアルゴリズムを考えなくて良いから、
これが簡単で現実的で、そこそこ良い結果も得られる

要約すると

「できるだけ似た文字列が並ばないように」並び替えるアルゴリズムは思いつかないので
「ランダムに」並び替えるアルゴリズムでごまかしましょう

>>184
結局、「全検索」のアルゴリズムを説明出来てない
オレオレ用語を使わず、一般的な用語を書け

重複しない整数からなる4個以上の数列がある
例 1,2,3,4

これを並び替えて、隣り合う数の差が2以上である
並びとして次のようなものが考えられる
例 3,1,4,2

この数列が大量（例1 000個）にあるとき
隣り合う数の差が2以上に並び替えるアルゴリズムを考えよ
また、隣り合う数の差の合計が最大になるアルゴリズムを考えよ
アルゴリズムは高速であればあるほどよい

参考 隣り合う数の差の合計
3,1,4,2,5 の場合 2+3+2+3=10
4,2,5,1,3 の場合 2+3+4+2=11

>>187
逆でしょ
何が効果的か根拠も自信もなくて抽象的で実装できるかもわからない理論よりも
ランダム探索でそこそこの結果を得ればいいと割り切る方が誤魔化さずハッキリしてるでしょ

>>190
そこそこ結果でOKなんて誰が言ったんですか？

１文字目で分類して最も多いものから順に均等に振り分ける
その振り分け範囲内で２文字について同じように振り分けなおす
短文字ではこれを繰り返すのが最もコストが少なく並び替えられる

>>189
質問は文字列だぞ？
簡単に数値に置き換えられ無いだろ

>>194
きにすんな、別の問題として考えろ

うわ
マウンターばっかり

屁理屈こねまくって重箱の隅をつつきまくって
1行もコードも何も具体的なモノ書かずに
良く上から目線で書き込めるもんだ

>>153 における
> 文字列が入った配列（例として["aaa","aaa","bbb","bbb","ccc","ccc",…以下1000個ほど続くとする]）

の構成要素が、具体的に ["aaa,""bbb,", "ccc" ...] 以外何があるか回答がない
釣り確定だな

>>198
どんな文字列が入ってきてもって意味だろ
答えられないからって釣り認定するなよ

>>199
板違い

そういうのは計算機科学の研究室でやれば良いし
Web制作との関連性も皆無