Si vous avez seulement besoin de générer combinaisons - où l'ordre des éléments n'a pas d'importance - vous pouvez utiliser combinadics comme ils le sont mis en œuvre, par exemple, ici par James McCaffrey .
Comparez cela avec k-permutations où l'ordre des éléments est important.
Dans le premier cas (1,2,3) , (1,3,2) , (2,1,3) , (2,3,1) , (3,1,2) , (3,2,1) sont considérés comme identiques - dans ce dernier cas, ils sont considérés comme distincts, bien qu'ils contiennent les mêmes éléments.
Si vous avez besoin de combinaisons, il se peut que vous n'ayez besoin de générer qu'un seul nombre aléatoire (bien qu'il puisse être un peu grand) - qui peut être utilisé directement pour trouver le m e combinaison. Puisque ce nombre aléatoire représente l'indice d'une combinaison particulière, il s'ensuit que votre nombre aléatoire doit être compris entre 0 et C(n,k) . Le calcul de la combinadique peut également prendre un certain temps.
Ça ne vaut peut-être pas la peine - d'ailleurs Réponse de Jerry et Federico est certainement plus simple que l'implémentation de la combinadique. Cependant, si vous n'avez vraiment besoin que d'une combinaison et que vous avez le souci de générer le nombre exact de bits aléatoires nécessaires et rien de plus... ;-)
Bien qu'il ne soit pas clair si vous voulez des combinaisons ou des k-permutations, voici un code C# pour ces dernières (oui, nous pourrions générer uniquement un complément si x > y/2, mais nous nous serions alors retrouvés avec une combinaison qui doit être mélangée pour obtenir une véritable k-permutation) :
static class TakeHelper
{
public static IEnumerable<T> TakeRandom<T>(
this IEnumerable<T> source, Random rng, int count)
{
T[] items = source.ToArray();
count = count < items.Length ? count : items.Length;
for (int i = items.Length - 1 ; count-- > 0; i--)
{
int p = rng.Next(i + 1);
yield return items[p];
items[p] = items[i];
}
}
}
class Program
{
static void Main(string[] args)
{
Random rnd = new Random(Environment.TickCount);
int[] numbers = new int[] { 1, 2, 3, 4, 5, 6, 7 };
foreach (int number in numbers.TakeRandom(rnd, 3))
{
Console.WriteLine(number);
}
}
}
Une autre mise en œuvre, plus élaborée, qui génère k-permutations Je pense qu'il s'agit d'une amélioration par rapport aux algorithmes existants si vous n'avez besoin que d'itérer sur les résultats. Bien qu'il doive aussi générer x des nombres aléatoires, il utilise uniquement O(min(y/2, x)) la mémoire dans le processus :
/// <summary>
/// Generates unique random numbers
/// <remarks>
/// Worst case memory usage is O(min((emax-imin)/2, num))
/// </remarks>
/// </summary>
/// <param name="random">Random source</param>
/// <param name="imin">Inclusive lower bound</param>
/// <param name="emax">Exclusive upper bound</param>
/// <param name="num">Number of integers to generate</param>
/// <returns>Sequence of unique random numbers</returns>
public static IEnumerable<int> UniqueRandoms(
Random random, int imin, int emax, int num)
{
int dictsize = num;
long half = (emax - (long)imin + 1) / 2;
if (half < dictsize)
dictsize = (int)half;
Dictionary<int, int> trans = new Dictionary<int, int>(dictsize);
for (int i = 0; i < num; i++)
{
int current = imin + i;
int r = random.Next(current, emax);
int right;
if (!trans.TryGetValue(r, out right))
{
right = r;
}
int left;
if (trans.TryGetValue(current, out left))
{
trans.Remove(current);
}
else
{
left = current;
}
if (r > current)
{
trans[r] = left;
}
yield return right;
}
}
L'idée générale est de faire un Le remaniement Fisher-Yates y mémoriser les transpositions dans la permutation . Il n'a été publié nulle part et n'a fait l'objet d'aucun examen par les pairs. Je pense qu'il s'agit d'une curiosité plutôt que d'une valeur pratique. Néanmoins, je suis très ouvert à la critique et j'aimerais savoir si vous trouvez quelque chose à redire à cet article - merci de le prendre en considération (et d'ajouter un commentaire avant de rétrograder).
