Nサイズのサンプルセットから異なるK個のサンプルをランダムに採取する
このような問題は,K個1~Nの間の異なる整数をランダムに生成することとして抽象化できる.
解決方法:
a、1番目の要素を選択し、n番目の要素のいずれかと交換します(1番目の要素自体を含む).このとき、ソート後の1番目の要素が決定されます.
b,2番目の要素を選択し,n−1番目の要素と任意の交換(2番目の要素自体を含む)を行う.
c,上記手順K回繰り返し
実装コード:
これはFisher-Yates shuffleの詳細です.参考にしてください.https://en.wikipedia.org/wiki/Fisher–Yates_shuffle
解決方法:
a、1番目の要素を選択し、n番目の要素のいずれかと交換します(1番目の要素自体を含む).このとき、ソート後の1番目の要素が決定されます.
b,2番目の要素を選択し,n−1番目の要素と任意の交換(2番目の要素自体を含む)を行う.
c,上記手順K回繰り返し
実装コード:
#include
#include
#include
#include
using namespace std;
int main(){
int n,k;
cin>>n>>k;
if(n>k){
int *nums = new int[n];
for(int i =0;i これはFisher-Yates shuffleの詳細です.参考にしてください.https://en.wikipedia.org/wiki/Fisher–Yates_shuffle