Алгоритм для выбора единственной, случайной комбинации значений?

Предполагая, что вы также хотите, чтобы порядок был случайным ( или не возражайте против того, чтобы это было случайным образом), я бы просто использовал усеченный тасование Фишера-Йейтса. Запустите алгоритм перемешивания, но остановитесь, как только вы выбрали первые x значения, вместо «случайного выбора» всех y из них.

Фишер-Йейтс работает следующим образом:

• выбирает элемент случайным образом и меняет его местами на элемент в конце массива.
• Повторять (или, что более вероятно, повторять) остаток массива, исключая последний элемент.

Шаги после первого не изменяют последний элемент массива. Шаги после первых двух не влияют на последние два элемента. Шаги после первого x не влияют на последние x элементов. Итак, на этом этапе вы можете остановиться - верхняя часть массива содержит равномерно выбранные случайным образом данные. Нижняя часть массива содержит несколько рандомизированные элементы, но получаемая вами перестановка распределяется неравномерно.

Конечно, это означает, что вы уничтожили входной массив - если это означает, что вам нужно сделать его копию перед запуском, а x мало по сравнению с y, то копирование всего массива не очень эффективно. Однако обратите внимание, что если все, что вы собираетесь использовать в будущем, - это дальнейший выбор, то тот факт, что он находится в несколько случайном порядке, не имеет значения, вы можете просто использовать его снова.Следовательно, если вы делаете выбор несколько раз, вы можете сделать только одну копию в начале и амортизировать стоимость.

Небольшое предложение: если x >> y / 2, вероятно, лучше выбрать случайным образом y - x элементов, а затем выбрать дополнительный набор.

Если вам действительно нужно только генерировать комбинации - где порядок элементов не имеет значения - вы можете использовать комбинаторику, как она реализована, например, здесь Джеймсом МакКэффри.

В отличие от k-пермутаций, где порядок элементов имеет значение.

В первом случае (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1, 2), (3,2,1) считаются одинаковыми - в последнем случае они считаются разными, хотя содержат одинаковые элементы.

В случае, если вам нужны комбинации, вам может потребоваться только одно случайное число (хотя оно может быть немного большим), которое можно использовать непосредственно для нахождения m-й комбинации. Поскольку это случайное число представляет собой индекс конкретной комбинации, следует, что ваше случайное число должно находиться в диапазоне от 0 до C(n,k). Вычисление комбинаторики также может занять некоторое время.

Возможно, это просто не стоит того - кроме того, ответ Джерри и Федерико, безусловно, проще, чем реализация комбинаторики. Однако если вам действительно нужна только комбинация, и вы озабочены генерацией именно того количества случайных битов, которое необходимо, и не более... ;-)

Хотя неясно, нужны ли вам комбинации или k-пермутации, вот код на C# для последнего (да, мы могли бы генерировать только дополнение, если x > y/2, но тогда у нас осталась бы комбинация, которую нужно перетасовать, чтобы получить настоящую 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);
        }
    }
}

Другая, более сложная реализация, которая генерирует k-пермутации, которая лежала у меня без дела, и я считаю, что она в некотором смысле является улучшением существующих алгоритмов, если вам нужно только итерировать результаты. Хотя ему также необходимо генерировать x случайных чисел, он использует O(min(y/2, x)) памяти в процессе:

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

Общая идея состоит в том, чтобы сделать перестановку Фишера-Ятса и запомнить транспозиции в перестановке. Эта работа нигде не была опубликована и не получила никакой экспертной оценки. Я считаю, что это скорее любопытство, чем практическая ценность. Тем не менее, я очень открыт для критики и хотел бы знать, если вы найдете в ней что-то неправильное - пожалуйста, рассмотрите это (и добавьте комментарий перед тем, как поставить минус).

Если, например, у вас есть 2^64 различных значений, вы можете использовать алгоритм симметричного ключа (с блоком в 64 бита) для быстрой перестановки всех комбинаций. (например, Blowfish).

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

Это не является случайностью в чистом смысле, но может быть полезно для вашей цели. Если вы хотите работать с произвольным количеством различных значений, используя криптографические методы, вы можете это сделать, но это сложнее.