[C언어] 겹치지 않는 난수 생성....

한세희의 이미지

어떻게 해야 할까요.....

도무지 감이 오지 않네요...

난수 발생전에 비교를 할수도 없고...

만약에 n개의 랜덤갯수를 발생시키면...

어떤식으로 중복되지 않는 난수를 발생시켜야 하나요?

Scarecrow의 이미지

우선 발생시킨후 중복인지 확인해 보고 중복이면 또 발생.

한세희의 이미지

n개라..만약에 100만개를 난수 발생 시킬경우 않겹칠 확률은 거의 제로이지 않나요;

cppig1995의 이미지

대부분의 환경에서, RAND_MAX는 32767입니다.
따라서 32768개 이상의 난수를 발생시킬 경우 비둘기집원리에 의해 중복되지 않을 확률은 없으며, 단지 수 개를 발생시키더라도 중복이 있을 확률이 높습니다.
그리고, 솔직히 중복체크는... 상당히 많은 시간을 낭비하지 않을까요?

Real programmers /* don't */ comment their code.
If it was hard to write, it should be /* hard to */ read.

한세희의 이미지

일단 32767의 배열을 선언한후

랜덤값을 저장후에

퀵정렬후에 앞뒤로 비교해서 같은게 있다면

난수를 다시 발생하려고 했는데 이역시 확률은 같겠네요..

뭐 방법 없나요?;

아예 난수를 하나 발생할때 배열에 저장되어있는 숫자와 비교하면서 난수를 발생 시키는게

좋겠죠?

only2sea의 이미지

만약에 그런 식으로 32767짜리 배열을 선언하시려면 정렬할 필요 없이 한번 나왔던 숫자를 첨자로 하는 곳에 한번 나왔다는 것을 기록하기만 하는 것이 훨씬 낫지요. True or False 값을 갖는 배열이겠지요.

이제는 서명에 무엇을 써야하는지 생각해보자.

danby04의 이미지

별로 예쁜 방법은 아닌것 같지만은요--;

그냥 배열의 안에다 각각 다른 값을 루프를 쓰던지 해서 그냥 입력하세요
(간단한 예로 0부터 차례대로 넣는다던가)

그럼 중복되지 않은 수들로 채워져있는 배열이 만들어 졌지요
그 다음에 배열의 각 요소들을 섞어주세요;;

그 다음에 필요한 만큼 만개면 만개, 백개면 백개, 앞에서 부터 뽑아서 쓰시면 될듯해요
그럼 적어도 중복되지 않는 다는건 보장되겠죠;;

배열 총 크기보다 뽑는 갯수가 적을 수록 더 자연스럽게 보이겠지요

배열안의 각 요소들을 섞어 버리는 shuffle함수는 간단하게 구현하실수 있을거에요

그럼 안녕히
(근데 써놓구 보니 별루 도움이 안되는거 같애서 댓글을 지우려구 하는데 댓글 지우는 기능이 안 보이구 편집만 보이네요 이거 어떻게 지우죠?--;;)

only2sea의 이미지

처음 난수 발생시에 시간이 걸리겠지만... 그 다음부터는 바로바로 튀어 나오겠네요. 음악 재생 프로그램의 playlist shuffler로 쓰기에는 아주 좋은 방법 같은데요.

ps. playlist shuffle 방식은 shuffle 할 필요없이 하나씩 아무거나 가져오면 될테니... 이 방법을 쓸 필요는 없어지는군요. 실제로 섞는 것 같은 것을 시뮬레이션 하는 방법이네요.

이제는 서명에 무엇을 써야하는지 생각해보자.

dcmru의 이미지

일단 하드웨어 적인 장치가 있으면 좋겠지만 이것이 안될 때는 big number 쓰는 구조를 쓰셔야합니다.

time 값과 big number로 시드값을 구한 후 이 값을 다시 해쉬알고리즘으로 해쉬를 하여 초기화 한 후 랜덤값을 산 출하는 듯했습니다.

저도 정립이 잘 안되어서 자세하게는 설명을 못하겠습니다.

하드웨어적인 방법이 가장 좋을 듯하지만 그건 가격이 비싼 듯하기 때문에, 방사능 무슨 장치였던 것 같습니다. ^^;

의사난수발생기로 한 번 찾아보시기 바랍니다.

노력만이 살길이다.

노력만이 살길이다.

pynoos의 이미지

난수란 다음 수를 예상할 수 없어야합니다만...

n 개의 랜덤 수를 구한다고 하면, n-1 번째에는 그 다음 값을 바로 예측할 수 있습니다. 여지껏 안나온 수니까요.. 이것이 과연 난수인가요?

좀더 일반화 시키면,
n - 2 번째에는 그 다음 나올 수의 확률은 50%입니다.
n - 3 번째에는 그 다음 나올 수의 확률은 33%입니다.

엄밀히 난수를 의미한다면, 모든 수에 대해서 확률이 1/n 이어야하는데, 원하시는 것은 두번째 수부터 그렇지 않게 되는 군요.

lacovnk의 이미지

음.. 그렇긴 하군요 :)

그런데, 앞에 뭐가 나왔는지 기억하지 못한다면 동일하게 1/n이 되는 셈이겠지요? ㅎ

하얀_고양이의 이미지

분명 다음 값을 예측 할 수 없다는 전제를 먼저 하신것 같은데 맞는지요?
맞는다면 끝의 "난수가 나올 확률"에 관한 언급이 앞의 전제에 대한 모순이 됩니다.
제가 잘못 이해하고 있다면 지적 부탁 드리겠습니다.

그리고 이 주제는 겹치치 않는 임의의 수를 구하는게 목적임을 상기 시킵니다.
난수라는 용어가 사람을 좀 곤란하게 만드는 군요 :D
------------------------------------------------
따뜻한 홍차의 여유 냐옹티~

따뜻한 홍차의 여유 냐옹티~

pynoos의 이미지

오랜만에 답글을 달게 되는 군요.
질문을 하셨으니, 제 의견을 드리자면.
제가 전제한 것이 아니라, 처음 질문하신 분의 문제제기가 잘못되었다는 것을 말씀드리려했던 것입니다.
난수발생기로서는 100번을 구해서 100개 다른 수가 나오게 하는 것은 불가능하다는 것이죠.

ironiris의 이미지

음악재생기의 셔플기능을 구현하려고 하시는 것 같은데...
보통 이럴땐 플레이할 목록이 배열로 되어있을텐데
목록갯수를 기준으로 난수발생한후 그것을 기초로 플레이목록이 들어있는 배열에서 하나 팝업시키고(참조하고 배열에서 제거)
줄어든 목록갯수를 기준으로 또 난수발생후 목록에서 팝업시키고...
이렇게 구현하면 될것 같은데요...

익명사용자의 이미지

cnt = MAX;
for (i = 0; i < MAX; i++) n[i] = i;
for (j = 0; j < loop_cnt; j++) {
swap(n[rand() % cnt], n[--cnt]);
printf("%d", n[cnt]);
}

익명사용자의 이미지

cnt = MAX;
for (i = 0; i < MAX; i++) n[i] = i;
for (j = 0; j < loop_cnt; j++) {
swap(n[rand() % cnt], n[--cnt]);
printf("%d", n[cnt]);
}
leonid의 이미지

배열을 섞는다든지 하는 게 아니라

단지 100만개의 난수를 발생시키는 거라면

그냥

long n = 0;
long randNumbers[1000000];
 
for(int i=0; i<1000000; i++)
{
   n += rand();
   randNumbers[i] = n;
}

이렇게 해버리면

절대로 겹칠일 없겠죠 --;

rand() 함수가 자연수만 리턴한다는 조건 하에...

long의 범위값을 넘는 것이 우려되기도 하는데

그건 그냥 저걸 살짝 수정해주면 ^^;

saxboy의 이미지

global로 이렇게 큰 배열을 만들어도 괜찮으려나요. :-)

atdda의 이미지

난수를 32bit로 지정하시고.
난수부 (앞 16bit) + 생성 시리얼 (뒷 16bit)
둘로 나눠서 하시죠.

겹치지 않을텐데요.

16bit로 만족할만한 개수가 아니면, 뒤의 생성 시리얼 부를 확장하면 되지 않을까 싶습니다.

May The Force Be With You.

May The Force Be With You.

사랑천사의 이미지

기본적으로... 왠만큼 안 겹치게 만들기 위해서...
Random Seed를.. Timestamp로 지정 하지 않나요.

#include <stdio.h>
#include <stdlib.h>
 
int main (void)
{
  unsigned long int x[1000000];
  unsigned long int c = 0;
  unsigned long int c2;
  int sign;
 
  while (c < 1000000) {
    srand (time ());
    x[geshifilter-c] = rand ();&#10;    for (c2 = 0; c2 &lt; c; c2++) {&#10;      if (x[c2] == x[c]) {&#10;        sign = 1;&#10;        break;&#10;      }&#10;    }&#10;    if (sign == 1) {&#10;      sign = 0;&#10;      continue;&#10;    }&#10;    c++;&#10;  }&#10;  for (c = 0; c &lt; 1000000; c++) {&#10;    print (&quot;X[%ld] = %ld\n&quot;, c + 1, x[c]);&#10;  }&#10;}&#10;
추가:time.h도 필요할 겁니다 아마... while에는 L을 붙여 줘야 겠죠. 이게 얼마나 실용적일 수 있는진 모르겠습니다. 근대... nano초 단위로 현제 시간을 얻어 네는 함수가 있었는데.. 그걸 쓰면 분명 좀 더 실용성이 있을 거 같은데 말이죠. time는 1초가 지나 가야만 Random Seed가 달라 지니 문제군요. 어떤 분이 난수를 발생 시키는 도스용 프로그램을...(아주 간단하게.) 만들어 내라고 하셔서 저런 식으로 작성을 했었습니다. 아주 같지는 않았죠. 실행 시간은 6에서 10초 정도면 끝났습니다. 최소 실행 시간이 6초였죠.(왜냐면 6개의 난수를 발생 시키면 되었으니까요.) 결론적으로 저 코드를 그데로 적용 시키면 엄청난 시간이 걸릴 겁니다. ---- 일어나라! 싸워라! 그리고 이겨라! 다만!!! 의미 있는 것에 그 힘을!!! 그 능력과 노력을!!![/geshifilter-c]

사람천사

cppig1995의 이미지

프로세서가 시작한 때부터 지금까지의 틱이 지난 횟수를 clock_t단위로 리턴해주는 clock함수가 time.h에 있습니다.;;;
또한, 프로그램 안에서 srand를 여러 번 호출하는 것은 의미가 없습니다.
srand를 while밖으로 끄집어내셔야 할 듯.

Real programmers /* don't */ comment their code.
If it was hard to write, it should be /* hard to */ read.

powerson의 이미지

돼지군 wrote:

대부분의 환경에서, RAND_MAX는 32767입니다.

대부분의 환경이라고 하셨지만, 리눅스에서는 다른 값이 나오더군요.
리눅으선 [2147483647] 값이 나오더군요.. 뭐 저도 심심해서 해본겁니다. ㅎㅎ

아직은 젊다. 모든 것을 할 수 있는 나이란 말이지.

------------------------------------------------------
아직은 젊다. 모든 것을 할 수 있는 나이란 말이지.

cppig1995의 이미지

앗 글쿤요. 하지만 표준 C에는 RAND_MAX의 값에 대한 정확한 정의가 없습니다.(아시다시피)
그리고 rand는 int를 리턴하고 int는 최소 16비트입니다.
그렇다면 한 RAND_MAX가 32767일 것이라는 예상을 할 수 있습니다.
그러나, 이럴 가능성은 없겠지만 이럴 수도 있기 때문에...

#define RAND_MAX 0
#define srand(n)
int rand()
{
 return 0;
}

또 RAND_MAX가 최소 몇이라고 단정지을수도 없지요.
어쨌든 성급하게 32767이라고 말해버린것 죄송합니다.

Real programmers /* don't */ comment their code.
If it was hard to write, it should be /* hard to */ read.

익명사용자의 이미지

current = -1;
cnt = max_cnt;
for (i = 0; i < max_cnt; i++) n[i] = current += get(current, max_cnt - i);
for (j = 0; j < loop_cnt; j++) {
swap(n[rand() % cnt], n[--cnt]);
printf("%d\n", n[cnt]);
}
 
int get(int current, int remain_cnt)
{
return (rand() % ((MAX_NUM - current) / remain_cnt)) + 1;
}

쓰고 보니 코드가 난잡해졌군요.. 낮은 숫자로 몰리는 경향도 있고...

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.