Случайно выбрать подмножество всех возможных комбинаций в Matlab? - PullRequest
Новая
       26

Случайно выбрать подмножество всех возможных комбинаций в Matlab?

2 голосов
/ 16 ноября 2011

Мне нужно выбрать случайные комбинации из k элементов из набора из n элементов, где n может быть довольно большим. Учитывая размер набора, невозможно просто использовать combnk или nchoosek для генерации всех возможных комбинаций и случайного выбора из них.

Есть ли простой способ генерировать уникальное случайное подмножество M из этих комбинаций?

Когда n мало, работает следующее: 

M = 20; %want to pick M random combinations
n = 10; %number of elements 
k = 5;  %number of elements in each combination
allCombos = nchoosek([1:n], k);  %for large n this is not feasible
numCombos = nchoosek(n,k);
permutationsToUse = randperm(numCombos, M);
randomCombos = allCombos(permutationsToUse, :);

Когда n большое, это уже невозможно.

Похожие сообщения

Извлечение определенной перестановки без сохранения всех возможных перестановок в Matlab

Как эффективно выбрать случайное количество комбинаций из всех комбинаций?

Выберите подмножество комбинаций

1 Ответ

2 голосов
/ 16 ноября 2011

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

Nelements=100;
M=10;
combsubset=randi(Nelements,[M 7]);
combsubset=unique(combsubset,'rows');

Если вы хотите получить точно M комбинаций, вы можетеиспользуйте цикл: 

Nelements=100;
M=10;
combsubset=[];
while(size(combsubset,1)<M)
    combsubset=[combsubset;randi(Nelements,[M 7])];
    combsubset=unique(combsubset,'rows');
end
combsusbet=combsubset(1:M,:);

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

Nelements=100;
Mtotal=20
M=10;
while(size(combsubset,1)<Mtotal)
    combsubset=[combsubset;randi(Nelements,[M 7])];
    combsubset=unique(combsubset,'rows');
end
combsusbet=combsubset(1:Mtotal,:);

РЕДАКТИРОВАТЬ : ДругойМетод для ваших нужд будет в том, чтобы упорядочить комбинации, чтобы иметь возможность получить только заданное подмножество.Один из способов их упорядочения можно объяснить на следующем примере: если у вас есть три индекса i, j, k в диапазоне от 0 до N-1, вы можете использовать уникальный индекс n=i*N*N+j*N+k, чтобы просмотреть все возможности.Тогда, если вы хотите получить n-й вектор: 

k=mod(n,N);
j=mod((n-k)/N,N);
i=mod((((n-k)/N)-j)/N,N);

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

...