Algorithme pour sélectionner une seule combinaison aléatoire de valeurs?

en supposant que vous voulez que l'ordre soit aléatoire aussi (ou ne faites pas attention à ce qu'il soit aléatoire), je voudrais juste utiliser un Fisher-Yates tronqué shuffle. Démarrez l'algorithme de mélange, mais arrêtez une fois que vous avez sélectionné les premières valeurs x , au lieu de "sélectionner au hasard" toutes les valeurs y d'entre elles.

de Fisher-Yates fonctionne comme suit:

• sélectionner un élément au hasard, et il échange avec l'élément à la fin du tableau.
• Récurse (ou plus probablement itérate) sur le reste du tableau, à l'exclusion du dernier élément.

pas après le premier ne modifiez pas le dernier élément du tableau. Étapes après les deux premières n'affectent pas les deux derniers éléments. Les étapes après le premier x n'affectent pas les derniers éléments de X. Donc, à ce stade, vous pouvez arrêter le haut du tableau contient uniformément au hasard de données sélectionnée. Le bas du tableau contient des éléments quelque peu aléatoires, mais le la permutation que vous obtenez d'eux n'est pas uniformément répartie.

bien sûr, cela signifie que vous avez détruit le tableau d'entrées - si cela signifie que vous devez en prendre une copie avant de commencer, et que x est petit par rapport à y, alors copier l'ensemble du tableau n'est pas très efficace. Notez bien que si vous allez l'utiliser à l'avenir à d'autres sélections, puis le fait que c'est un peu aléatoire de l'ordre n'a pas d'importance, vous pouvez simplement l'utiliser à nouveau. Si vous êtes en train de faire la sélection plusieurs fois, donc, vous pouvez être en mesure de faire une seule copie au début, et amortir le coût.

si vous avez vraiment besoin de générer combinaisons - où l'ordre des éléments n'a pas d'importance - vous pouvez utiliser combinatoires comme ils sont mis en œuvre par exemple ici par James McCaffrey .

contraste avec K-permutations , où l'ordre des éléments importe.

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 de la même manière dans le dernier, ils sont considérés comme distincts, bien qu'ils contiennent les mêmes éléments.

dans le cas où vous avez besoin de combinaisons, vous pouvez vraiment seulement besoin de générer un nombre aléatoire ( bien qu'il puisse être un peu grand) - qui peut être utilisé directement pour trouver le m th combinaison. Puisque ce nombre aléatoire représente l'indice d'une combinaison particulière, il s'ensuit que votre nombre aléatoire devrait être entre 0 et C(n,k) . Le calcul de la combinaison peut aussi prendre du temps.

il pourrait tout simplement pas la peine de la peine - en outre la réponse de Jerry et Federico est certainement plus simple que la mise en œuvre combinatoire. Toutefois, si vous avez vraiment besoin d'une combinaison et vous sont sur écoute pour générer le nombre exact de bits aléatoires qui sont nécessaires et aucun plus... ;- )

bien qu'il ne soit pas clair si vous voulez des combinaisons ou des permutations k, voici un code C# pour ces dernières (Oui, nous pourrions générer seulement un complément si x > y / 2, mais alors nous aurions été laissés avec une combinaison qui doit être mélangée pour obtenir une vraie permutation k):

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 , que j'avais couché autour et je crois est en quelque sorte une amélioration par rapport aux algorithmes existants si vous avez seulement besoin d'itérer sur les résultats. Alors qu'il doit également générer x nombres aléatoires, il utilise seulement O (min (y/2, x)) 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 Fisher-Yates shuffle et mémoriser les transpositions dans le permutation . Il n'a pas été publié et n'a reçu aucun examen par les pairs que ce soit. Je crois que c'est une curiosité plutôt que d'avoir une valeur pratique. Néanmoins, je suis très ouvert à la critique et je voudrais généralement savoir si vous trouvez quelque chose de mal à ce sujet - s'il vous plaît considérer cela (et Ajouter un commentaire avant la rétrogradation).

une petite suggestion: si x >> y/2, Il est probablement préférable de sélectionner au hasard des éléments y - x, puis de choisir l'ensemble complémentaire.

si, par exemple, vous avez 2^64 valeurs distinctes, vous pouvez utiliser un algorithme de clé symétrique (avec un bloc de 64 bits) pour mélanger rapidement toutes les combinaisons. (par exemple Blowfish).

for(i=0; i<x; i++)
   e[i] = encrypt(key, i)

ce n'est pas un hasard dans le sens pur mais peut être utile pour votre but. Si vous voulez travailler avec le nombre arbitraire de valeurs distinctes suivant des techniques cryptographiques, vous pouvez mais c'est plus complexe.

L'astuce est d'utiliser une variante de shuffle ou en d'autres termes partielle shuffle.

function random_pick( a, n ) 
{
  N = len(a);
  n = min(n, N);
  picked = array_fill(0, n, 0); backup = array_fill(0, n, 0);
  // partially shuffle the array, and generate unbiased selection simultaneously
  // this is a variation on fisher-yates-knuth shuffle
  for (i=0; i<n; i++) // O(n) times
  { 
    selected = rand( 0, --N ); // unbiased sampling N * N-1 * N-2 * .. * N-n+1
    value = a[ selected ];
    a[ selected ] = a[ N ];
    a[ N ] = value;
    backup[ i ] = selected;
    picked[ i ] = value;
  }
  // restore partially shuffled input array from backup
  // optional step, if needed it can be ignored
  for (i=n-1; i>=0; i--) // O(n) times
  { 
    selected = backup[ i ];
    value = a[ N ];
    a[ N ] = a[ selected ];
    a[ selected ] = value;
    N++;
  }
  return picked;
}

NOTE l'algorithme est strictement O(n) dans à la fois temps et espace , produit sélections non biaisées (il s'agit d'un shuffling partiel non biaisé ) et non destructif sur le tableau d'entrées (en tant qu'un shuffle) mais c'est facultatif

adapté de ici

mise à jour

another approach using only a single call to PRNG (pseudo-random number generator) in [0,1] by IVAN STOJMENOVIC, "ON RANDOM AND ADAPTIVE PARALLEL GENERATION OF COMBINATORIAL OBJECTS" (section 3 ), of O(N) (dans le pire des cas), de la complexité

voici un moyen simple de le faire qui n'est inefficace que si Y est beaucoup plus grand que X .

void randomly_select_subset(
    int X, int Y,
    const int * inputs, int X, int * outputs
) {
    int i, r;
    for( i = 0; i < X; ++i ) outputs[i] = inputs[i];
    for( i = X; i < Y; ++i ) {
        r = rand_inclusive( 0, i+1 );
        if( r < i ) outputs[r] = inputs[i];
    }
}

essentiellement, Copiez le premier X de vos valeurs distinctes dans votre tableau de sortie, et ensuite pour chaque valeur restante, décidez au hasard si oui ou non inclure cette valeur.

le nombre aléatoire est ensuite utilisé pour choisir un élément de notre tableau de sortie (mutable) à remplacer.