アルゴリズム基本編 1 - ランダムな整数列の生成

ランダムで要素の重複があってもよい整数列

ランダムな整数列をつくりなさい，要素の重複はあってもいいですよ，といわれた場合，あなたはどうするか．
当然ながら最も簡単な答えは整数列に疑似乱数を生成して割り当てればよい．

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

#define INTARRAY_MAX 10

int* gen_rand_intarray(int* arr, int size) {
 
 for(int i = 0;i < size;i++){
  *arr = rand() % size;
  printf("%d\n",*arr);
  arr++;
 }
 return arr;

}

int main() {

 srand(time(NULL));
 int* arr = (int*)malloc(INTARRAY_MAX*sizeof(int));
 gen_rand_intarray(arr,INTARRAY_MAX);
 for( int i = 0;i < INTARRAY_MAX;i++ ) {
  printf("%i - %d[@%d]\n",i,*arr,arr);
  arr++;
 }
 return EXIT_SUCCESS;

}

では要素の重複はゆるさないよ，となったら？リストからセットにデータを移し替えればおのずと重複要素は消えるが，整数列長は縮む可能性があるので解として不適な可能性がある．
やはりここは定石の配列のインデックスを乱数生成しシャッフル，だろう．乱数値の生成とシャッフル合わせてO(2N)．もっと効率的な方法はありそうだが．．

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

#define INTARRAY_MAX 10

int main() {

 srand(time(NULL));
 int r,t;

 int arr2[INTARRAY_MAX];
 for(int i = 0;i < sizeof(arr2)/sizeof(int);i++)
  arr2[i] = i;

 for(int i = 0;i < INTARRAY_MAX;i++) {
  r = rand() % INTARRAY_MAX;
  t = arr2[r];
  arr2[r] = arr2[i];
  arr2[i] = t;
 }

 for(int i = 0;i < INTARRAY_MAX;i++)
  printf("%d ", arr2[i]);

 char ch;
 scanf(&ch);
 return EXIT_SUCCESS;

}

---

ちなみにSTLのrandom_shuffleを使った場合の解は以下の通り．

#include <iostream>
#include <vector>
#include <algorithm>

#define INTARRAY_MAX 10

int main() {
 std::vector<int> v;
 for( int i = 0;i < INTARRAY_MAX;i++ )
  v.push_back(i);
 std::random_shuffle(v.begin(),v.end());
 for(std::vector<int>::iterator it = v.begin();it != v.end();++it)
  std::cout << *it << ' ';
 std::cout << std::endl;
 return EXIT_SUCCESS;
}