[완료] 빠른 shuffle 알고리즘이 어떤게 있을까요?

lee3390의 이미지

0~29999까지의 수, 30000개의 수를 shuffle을 해야하는데

어떤 방법이 가장 빠를련지 질문 드립니다.

30000개의 배열 만들어서 중복검사해서 할라하니 29999개를 뽑아내고 마지막 하나 남았을 때

잘못하면 무한루프가 돌 것 같고..

그래서 고민하다보니 차라리 30000개짜리의 linked list를 만들어서

처음에 30000개의 수에서 난수 생성해서 linked list에서 하나 뽑고 그다음은 29999개의 수에서 난수 생성해서 또 뽑아내고 하는게 가장 괜찮을 것 같은데..

이 방법 말고 쉽고 간단한 방법이 있을까요?

cppig1995의 이미지

저는... 난수 뽑아서 난수만큼 next_permutation 돌립니다.
C++ 만세! STL 만세!

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

익명사용자의 이미지

0~29999 까지 그냥 순서대로 배열 만들고,
루프돌면서 random 하게 swap 시키면 어떨까요?

익명사용자의 이미지

과제물 제출용이 될지도 모르지만... 일단 코드 첨부합니다.

#include <stdio.h>
 
#define MAX_ARRAY     10
 
void generate_random(int *random_array, int size)
{
    int i, random_number, temp_value;
 
    for( i = 0; i < size; i++ )
        random_array[i] = i;
 
    for( i = size - 1; i > 0; i-- )
    {
        random_number = (rand() + rand()) % i;
 
        // swap
        temp_value = random_array[i];
        random_array[i] = random_array[random_number];
        random_array[random_number] = temp_value;
    }
}
 
int main(void)
{
    int i, random_value[MAX_ARRAY];
 
    generate_random(&random_value[0], MAX_ARRAY);
 
    for( i = 0; i < MAX_ARRAY; i++ )
        printf("%d\n", random_value[i]);
 
    return 0;
}

helloneo의 이미지

그냥 이렇게하면 되지않을까요..?

for (i = 29999; i; i--) {
j = rand() % i;
swap(num[j], num[i]);
}

WHAT'S UP

lee3390의 이미지

과제가 아니고요 제가 만드는게 있는데

만든 플그램을 시뮬레이팅 하기위해선 저 알고리즘이 필요해서요..

여기저기 뒤져보니까 stl 에 random_shuffle이란것이 있네요

여러 답변 감사합니다 ^_^

댓글 달기

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
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.