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

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

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

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

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

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

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

	using System;
	using System.Collections.Generic;
	using System.Linq;
	using System.Text;
	using System.Threading.Tasks;
	namespace Permute
	{
	class Program
	{
	// Permute 0 .. n
	static int[] permute(int n)
	{
	Random random = new Random();
	int[] index = new int[n];
	int[] x = new int[n];
	for (int i = 0; i < n; i++)
	{
	int r = random.Next(n-i)+1;
	int count = 0;
	int j = 0;
	for (; j < n;j++)
	{
	if (index[j] == 0)
	count++;
	if (r <= count)
	break;
	}
	if(j<n)
	{
	x[i] = j;
	index[j] = 1;
	}
	}
	return x;
	}
	// Select max elements from 0 .. n
	static int[] withoutDuplicate(int n, int max)
	{
	Random random = new Random();
	int[] index = new int[n];
	int[] x = new int[max];
	for (int i = 0; i < max; i++)
	{
	int r = random.Next(n - i) + 1;
	int count = 0;
	int j = 0;
	for (; j < n; j++)
	{
	if (index[j] == 0)
	count++;
	if (r <= count)
	break;
	}
	if (j < n)
	{
	x[i] = j;
	index[j] = 1;
	}
	}
	return x;
	}
	// Select [max] elements from 0 .. n excluding [excluded]
	static int[] selectWithout(int n, int max, int excluded)
	{
	Random random = new Random();
	int[] index = new int[n];
	int[] x = new int[max];
	for (int i = 0; i < max; i++)
	{
	int r = random.Next(n - i) + 1;
	int count = 0;
	int j = 0;
	for (; j < n; j++)
	{
	if (index[j] == 0 && j != excluded)
	count++;
	if (r <= count)
	break;
	}
	if (j < n)
	{
	x[i] = j;
	index[j] = 1;
	}
	}
	return x;
	}
	static void Main(string[] args)
	{
	int[] x=Program.permute(10);
	foreach(int i in x)
	{
	Console.Write(i+" ");
	}
	Console.ReadLine();
	int[] y = Program.withoutDuplicate(10, 3);
	foreach(int i in y)
	{
	Console.Write(i + " ");
	}
	Console.ReadLine();
	int[] y = Program.selectWithout(10, 3, 6);
	foreach (int i in y)
	{
	Console.Write(i + " ");
	}
	Console.ReadLine();
	}
	}
	}

view raw Permute.cs hosted with ❤ by GitHub

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

どうでしょうか。

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

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

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