Программирование на С: Генерировать случайные n-комбинации из заданного набора?

Question

Скажем, у меня есть предварительно заданный набор S из m элементов. Я хотел бы создать случайную комбинацию n (уникальных) элементов, взятых из S.

Есть ли простой способ реализовать это в C? Я посмотрел на Ранд(), но, похоже, он не делал то, что я хочу.

(EDIT, чтобы добавить больше деталей)

Специфической проблемой является случайным образом выбирать п различных элементов из массива размером м. Мой первый инстинкт должен сделать это:

idx_array = []

INT IDX = рандов()% м

[если IDX не в idx_array, добавить к idx_array. В противном случае повторите выше строки. Повторяйте до тех пор, пока idx_array не будет иметь размер n]

Но это не похоже, что этот процесс действительно случайный. Я все еще новичок в C и на самом деле просто хочу знать, есть ли встроенная функция для этой цели.

Любая помощь приветствуется.

Answer 1

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

Answer 2

Вместо того чтобы генерировать число от 1 до n с возможностью дубликата, перетасуйте массив, а затем выбрать из первых n элементов:

#include <stdio.h> 
#include <stdlib.h> 

// Randomly shuffle a array 
void shuffle (int * array, int n) { 
    int i, j, tmp; 

    for (i = n - 1; i > 0; i--) { 
    j = arc4random_uniform(i + 1); 
    tmp = array[j]; 
    array[j] = array[i]; 
    array[i] = tmp; 
    } 
} 


int main (int argc, char const *argv[]) 
{ 
    const int m = 5; 
    const int n = 3; 

    int s[m] = {10, 20, 30, 40, 50}; 

    // Make a copy of s before shuffling it 
    int t[m]; 
    for(size_t i = 0; i < m; i++) 
    { 
     t[i] = s[i]; 
    } 
    shuffle(t, m); 

    // Now, the first n elements of t is what you want 
    for(size_t i = 0; i < n; i++) 
    { 
     printf("%d ", t[i]); 
    } 

    return 0; 
} 

Кредит Roland Illig для функции перетасовки Fisher-Yate.