C++でn未満の数字をk個選択

n個からk個をランダムに選び出したいことはよくあるので、0~n-1の数字のうちk個をランダムに選ぶもので例えば

のためのプログラム。

#include <set>
#include <cstdlib>
#include <ctime>
#include <iostream>
using namespace	std;
 
set<int> nCk(int n, int k){
  set<int> cmb;
  int j;
  srand(time(NULL));
  for(int i=n-k; i<n; i++){
    j = rand()%i;
    if(cmb.find(j) == cmb.end())
      cmb.insert(j);
    else
      cmb.insert(i);
  }     
  return cmb;
}
 
int main(){
  set<int> r	= nCk(100, 50);
  set<int>::iterator i = r.begin();
  while(i != r.end()){
    cout << *i << endl;
    i++;
  }
}
 

nCkという関数で返り値はsetで返ってくる。
出てきた順番通りに値を出力するものは、

#include <cstdlib>
#include <ctime>
#include <vector>
#include <iostream>
using namespace std;
 
vector<int> nCk(int n, int k){
  vector<int> cmb;
  int j;
  srand(time(NULL));
  for(int i=n-k; i<n; i++){
    j = rand()%i;
    if(find(cmb.begin(), cmb.end(), j) == cmb.end()){
      cmb.push_back(j);
    }else{
      cmb.push_back(i);
    }
  }
  return cmb;
}
 
int main(){
  vector<int> r = nCk(100, 50);
  for (int i=0; i<50; i++)
    cout << r[i] << endl;
}
 

vectorクラスでいちいち出てきた値があるかどうか探すので少し時間がかかるので、setを利用して高速化したものは

#include <set>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <iostream>
using namespace std;
 
vector<int> nCk(int n, int k){
  vector<int> cmb;
  set<int> check;
  int j;
  srand(time(NULL));
  for(int i=n-k; i<n; i++){
    j = rand()%i;
    if(check.find(j) == check.end()){
      check.insert(j);
      cmb.push_back(j);
    }else{
      check.insert(i);
      cmb.push_back(i);
    }
  }
  return cmb;
}
 
int main(){
  vector<int> r = nCk(100, 50);
  for (int i=0; i<50; i++)
    cout << r[i] << endl;
}
 

vectorじゃなくてstackとかでもいい。