配列をムダなく並び替える

ここでは配列をムダなく並び替える方法を提案します。

提案というより、いつもの「ループをまわして違う値が出るまで繰り返す」という方法をやめようという提案です。

何度もまわしていれば終わる作業ではあるはずですが、当然のごとくこのアルゴリズムだと終わるという確証がありません。

カウンタなどつけていれば無限ループという最悪の事態は防げるわけですが、ここでは「乱数は配列の大きさだけ計算すればいいはず」というアルゴリズムの提案です。

大げさなことはないわけなのですが、計算しなければならない乱数ってのは「まだ選択されていない数からのみ」なわけなので、その方法を示します。

まずはコード permute() をご覧ください。

…　というわけです。選択されていない中から選ぶので乱数の計算が配列の大きさで済むというわけです。

どうでしょうか。

permute() の応用で、重複しない要素を選択する関数 withoutDuplicate(int n, int max) というのも作れます。

selectWithout(int n, int max, int excluded) は選択すべき要素から一定要素を除いた重複しない要素を選択する関数です。

よく使うアルゴリズムだと思います。