【C++】隣同士で同じにならない配列の並べ替え

質問

以下に説明する配列を、以下のような条件で並び替えるC++のプログラムを考えています。

------------------------------------------------------------------------------
●並び替えたい配列
・要素数は72
・配列の中身は0~71のいずれかの整数（同じ数は入らない）

●並び替える条件
・「中身を6で割った商」が配列の隣同士で同じにならないこと。
・「中身を24で割った商」が配列の隣同士で同じにならないこと。
・「中身を6で割った余り」が配列の隣同士で同じにならないこと。
・0~5、6~11、12~17、…という6刻みの配列の範囲内においては、6で割った余りの数が範囲内の中身の数同士で被らないようにする。
・条件を守る範囲内で、無作為な並び替えとなるようにすること
------------------------------------------------------------------------------

具体的に何故このプログラムが必要なのかというと、
・3つの条件（条件1:6種類、条件2:4種類、条件3:3種類）を同時に表示するにあたり、
・条件1をランダムに並び替えたもの（ただし前回の条件1と被らない中身で）を繰り返し表示する中で、
・条件3の種類を前回の条件3と異なるものを表示させ、
・条件2を加えた条件1~3の組み合わせ全72種類を条件内でランダムに表示させようと考え、上記の方法を思いつきました。

皆様のお知恵をお借りできればと思います。よろしくお願いいたします。

回答No.3

Ogre7077

再帰の探索アルゴリズムで重要なのは、しっかりとした「枝切り」です。
それさえ出来ていれば、この条件とデータ量ならあっという間でしょう。

差し支えない範囲でプログラム内容を補足投稿いただければ、
なにかしら助言出来ると思います。

回答No.2

Tacosan

プログラムができてるわけじゃないけどちょっと指摘だけ.

条件として 5つ (「ランダム」を除けば 4つ) あるけど, 実は 1つ目の条件は 2つ目に完全に含まれてるから無視してもいい. あと, 3つ目と 4つ目も条件としてはそれほど差がないのでまとめて考えた方がいいような気がする.

で, この手の「ある条件を満たしつつランダムに選ぶ」ということだと
1. ランダムに作る
2. 条件を満たしていれば OK, 満たさなければやり直し
というのが多いような気がするんだが, 今回の場合は 2つ目の条件がきっついのでこの筋はとれない.

実のところ条件を満たす並べ方がどのくらいあるのか知らんのだが, 「2つ目の条件がきつい」ことを念頭に置くと
1. 「中身を24で割った商」を条件を満たすように並べる (したがって 0, 1, 2 が 24個ずつ入る)
2. 「中身を24で割った商」が同じ値の奴ら同士で, 「中身」の値をランダムシャッフル
3. 必要な条件をすべて満たしていれば OK, ダメなら 2 に戻る
くらいでなんとかならないかなぁ. 等確率になる保証がないんだけど....

お礼

ご回答ありがとうございます！
確かに1つ目の条件は2つ目の条件に含められますね。気づきませんでした…！

回答者さんの言う通り、やはり２つ目の条件がキツすぎるようです。
等確率の条件を緩める方向で検討しようと思います。

回答No.1

Ogre7077

この手は再帰を使った探索が定石でしょう

ぱぱっと書いた未検証コードなので、
バグとか性能劣化要因とかが混入していたらスミマセン

int 配列[72];

bool 配列が条件を満たす(数) {
_ int i;
_ for(i=0; i<数; i++) { if(...) return false; }
_ return true;
}

bool 探索(int 位置) {
_ if (! 配列が条件を満たす(位置)) return false;
_ if (位置 == 72) return true; // 条件を満たす72個の配列が探索できた!
_ int i, delta = 整数の乱数0から71();
_ for(i=0; i<72; i++){
_ _ 配列[位置] = (i + delta) % 72;
_ _ if(探索(位置+1)) return true;
_ }
_ return false;
}

/** 条件を満たす配列をランダムに一つ作成できたら true を返す. */
bool 探索開始() {
_ return 探索(0);
}

お礼

ご回答ありがとうございます！
こちらを参考にして作成してみました…がやはり条件が厳しいためにループが続いてしまい、プログラムが止まってしまいました。
条件を緩める方向でもう少し考えてみることにします。