2017年5月8日月曜日

優先順位付きの組み合わせ

 与えられた配列からn個の要素を取り出して組み合わせを作る際、添字が若いほうが優先度が高い、という条件をつけて生成する。
 今回はnが固定なので、forべた書き。可変長の場合は再帰とか使えばできるんだろうけど、今回は必要ないので考えてない。


 単純forネスト(上)は早いうちに4が出てきているが、優先度付き(下)はそうならないようになっている。

 あれとそれとこれの組み合わせが相手にも存在するか、みたいな総当りで、相手にも存在する確率が高い順にソートしてからこの添字で調べていけば、早期にマッチする確率が高い。もっとも、「相手にも存在する組み合わせが何個有るか」みたいな判定の場合は効果がないのだけど。

 左側がぽんぽん動いてるのが気に食わねぇ、って場合は添字に使う順番を変えればいい。ただしその場合は左側>右側になるので、どっちが好きかという話。


 前回のジグザグスキャンのコードとかも、いちいち自分で考えないで、探してきたほうが早かったりするんだろうなぁ。
 四角い車輪の再発明でも、地面のデコボコに一致すれば完璧に走るんです!とか、四角い車輪でも回転数上げれば安定するんです!みたいな言い訳。ま、回転数上げると車軸折れるんだけどな。。。




int[] arr = Enumerable.Range(0, 5).ToArray();

for (int i = 0; i < arr.Length - 2; i++)
{
    for (int j = i + 1; j < arr.Length - 1; j++)
    {
        for (int k = j + 1; k < arr.Length; k++)
        {
            Console.WriteLine(arr[i] + "," + arr[j] + "," + arr[k]);
        }
    }
}

Console.WriteLine();

for (int k = 2; k < arr.Length; k++)
{
    for (int j = 1; j < k; j++)
    {
        for (int i = 0; i < j; i++)
        {
            Console.WriteLine(arr[i] + "," + arr[j] + "," + arr[k]);
        }
    }
}

0 件のコメント:

コメントを投稿