Algorytm wyboru pojedynczej, losowej kombinacji wartości?

Zakładając, że chcesz, aby kolejność była również losowa (lub nie masz nic przeciwko temu, aby była losowa), użyłbym po prostu obciętej shuffle Fisher-Yates. Uruchom algorytm shuffle, ale zatrzymaj się po wybraniu pierwszych wartości x, zamiast "losowo wybrać" wszystkie y z nich.

Fisher-Yates działa w następujący sposób:

• wybierz element losowo i zamień go z elementem na końcu tablicy.
• Rekurencja (lub bardziej prawdopodobne iteracja) na pozostałej części tablicy, wyłączając ostatni element.

Kroki po pierwszym nie modyfikują ostatniego elementu tablicy. Kroki po dwóch pierwszych nie wpływają na dwa ostatnie elementy. Kroki po pierwszym x nie wpływają na ostatnie elementy x. Więc w tym momencie można zatrzymać - górna część tablicy zawiera jednolicie losowo wybrane dane. Dolna część tablicy zawiera nieco randomizowane elementy, ale otrzymana z nich permutacja nie jest równomiernie rozłożona.

Oczywiście oznacza to, że masz skasowanie tablicy wejściowej-jeśli oznacza to, że przed uruchomieniem trzeba zrobić jej kopię, A x jest małe w porównaniu z y, to kopiowanie całej tablicy nie jest zbyt efektywne. Pamiętaj jednak, że jeśli w przyszłości będziesz go używać tylko do dalszych Selekcji, to fakt, że jest w nieco losowej kolejności, nie ma znaczenia, możesz go po prostu użyć ponownie. Jeśli dokonujesz wyboru wiele razy, możesz być w stanie wykonać tylko jedną kopię na początku i zamortyzować koszt.

Jeśli naprawdę potrzebujesz tylko wygenerować kombinacje - gdzie kolejność elementów nie ma znaczenia - możesz użyć combinadics tak, jak są zaimplementowane np. tutaj przez Jamesa Mccaffreya .

Kontrast z k-permutacje , gdzie kolejność elementów ma znaczenie.

W pierwszym przypadku (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1) są uważane za takie same - w te ostatnie są uważane za odrębne, choć zawierają te same elementy.

W przypadku, gdy potrzebujesz kombinacji, naprawdę może być tylko trzeba wygenerować jedną liczbę losową (choć może być nieco duża) - które mogą być użyte bezpośrednio do znalezienia M th kombinacji. Ponieważ ta liczba losowa reprezentuje indeks określonej kombinacji, wynika z tego, że liczba losowa powinna wynosić od 0 do C (n, k). Obliczanie combinadics może zająć trochę czasu, ponieważ cóż.

Chociaż nie jest jasne, czy chcesz kombinacje lub K-permutacje, tutaj jest kod C# dla tych ostatnich (tak, moglibyśmy wygenerować tylko dopełniacz, jeśli x > y/2, ale wtedy mielibyśmy pozostawiono kombinację, która musi zostać przetasowana, aby uzyskać rzeczywistą permutację 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);
        }
    }
}

Kolejna, bardziej rozbudowana implementacja, która generuje K-permutacje , którą miałem i wierzę, że jest w pewnym sensie ulepszeniem w stosunku do istniejących algorytmów, jeśli tylko trzeba iterację nad wynikami. Podczas gdy musi również generować x liczby losowe, używa tylko O (min (y / 2, x)) pamięci w procesie:

    /// <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;
        }
    }

Ogólna idea polega na tym, aby Fisher-Yates shuffle i zapamiętuje transpozycje w permutacji . Nie został nigdzie opublikowany ani nie otrzymał żadnej wzajemnej recenzji. Uważam, że jest to raczej ciekawostka niż praktyczna wartość. Niemniej jednak jestem bardzo otwarty na krytykę i ogólnie chciałbym wiedzieć, czy znajdziesz w niej coś złego - proszę o rozważenie tego (i dodanie komentarza przed odrzuceniem).

Mała sugestia: jeśli x > > y / 2, prawdopodobnie lepiej wybrać losowo elementy y-x, a następnie wybrać Zestaw uzupełniający.

Jeśli na przykład masz 2^64 różne wartości, możesz użyć algorytmu klucza symetrycznego (z 64-bitowym blokiem), aby szybko przetasować wszystkie kombinacje. (na przykład Blowfish).

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

To nie jest przypadkowe w czystym sensie, ale może być przydatne dla Twojego celu. Jeśli chcesz pracować z dowolnymi # o różnych wartościach zgodnie z technikami kryptograficznymi, możesz, ale jest to bardziej złożone.

Sztuczka polega na użyciu odmiany shuffle lub innymi słowy częściowego 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;
}

Uwaga algorytm jest ściśle O(n) w zarówno w czasie, jak i przestrzeni, wytwarza bezstronne selekcje (jest to częściowe bezstronne tasowanie ) i nieniszczące na tablicy wejściowej (jak częściowe tasowanie), ale jest to opcjonalne

Zaadaptowane z tutaj

Update

Inne podejście wykorzystanie tylko jednego wywołania PRNG (generator liczb pseudolosowych) W [0,1] przez Ivana STOJMENOVICIA, "na losowym i adaptacyjnym równoległym generowaniu obiektów kombinatorycznych" (sekcja 3), z O(N) (najgorszy przypadek) złożoności

Oto prosty sposób, aby to zrobić, który jest nieefektywny tylko wtedy, gdy Y jest znacznie większa niż 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];
    }
}

Zasadniczo skopiuj pierwszą X z Twoich odrębnych wartości do tablicy wyjściowej, a następnie dla każdej pozostałej wartości losowo zdecyduj, czy dodać tę wartość.

Liczba losowa jest dalej używana do wybrania elementu naszej (zmiennej) tablicy wyjściowej do zastąpienia.