4자리 중복피하는 난수구하기

target01의 이미지

제가 자바로 4자리 난수를 구하는데 숫자4자리로 구할수 잇는경우의 수는 0-9999까지 10000가지 입니다.이것을 1:1221 2:3321 3:2231----30:9980 머 이런식으로 하나의 카드(보안카드식)에 30개씩 카드 2만개가 아니라 5만개입니다.
근데 만들 카드의수가 많으니까 중복이 되서..이것을 피해야 하는데..한장의 카드에 같은 난수가 있으면 안되고 서로다른 카드를 비교할때 같은자리의 난수가 2개이상 중복되어도 안됩니다.(예=A 카드의 1번과 B 카드의 1번 숫자동일허용,A카드의 13번과 B카드의13번도 동일하면 2개의 번호가 같은 위치에 같은 난수가 중복되므로 이것은 안됨) 머 이런식으로 해야 하는데 도저히 로직이 안그려지네요..고수님들의 훈수를 기다립니다.제가 한 소스는..
for (int k=1; k <= 100; k++) { //고객카드번호생성
CardNo = k;

// System.out.print(k + "; ");
// int j = 1;
// while(j < 36){
for (int j=1; j < 31; j++ ) { //번호: 1-30번까지 생성문

ar1 = (int)(Math.random() * 10000 );


if ((ar1 == 0000) || (ar1 == 1111) || (ar1 == 2222) || (ar1 == 3333) || (ar1 == 4444)
|| (ar1 == 5555) || (ar1 == 6666) || (ar1 == 7777) || (ar1 == 8888) || (ar1 == 9999)) {

j = j-1;
continue;
}

// if(ar1[j] == ar1[j]) { //같은 레코드 중복데이타 확인
// System.out.println(ar1[j]+"========중복=======" + ar1);
// j = j-1;
// continue;
// }else {
// if(ar1[j] != nextInt(ar1[j])) {


String no = Integer.toString(ar1);

if(no.length() == 1) {
System.out.print("0");
}

String str = Integer.toString(ar1);

if(str.length() == 1) {

System.out.print(j + " : 000" + str + ", " );

} else if (str.length() == 2) {

System.out.print(j + " : 00" + str + ", ");

} else if (str.length() == 3) {

System.out.print(j + " : 0" + str + ", ");

} else {

System.out.print(j + " : " + str + ", ");

}


// }

} //for (j) end
System.out.println("");

} //for (k) end

이럿습니다.

select99의 이미지

배열 10000 개 만들면 되겠네요..

기존 데이터 중복을 피하기위해서 발행한 번호는 기억해야겠죠..

그다음 발번하실때.. 기존데이터들이 중복되지 않게 발번하시면되겠군요..

"중복되지 않게 발번"...의 효율을 높이기위해서..

제생각엔 10000 개의 배열에 발번했으면 1로 셋팅 바번하지 않았으면 0

1~(10000 -현재까지발번 -조건에불일치갯수) 까지 난수발생해서(난수X라하면)

비어있는 X 번째 배열을 조건에 맞으면 1로셋팅 조건에 맞지 않으면 2로셋팅하면서

현재까지발번 + 조건에불일치갯수 = 10000 이될때까지 for 문돌리시면

발번가능한 번호를 빠르게 찾을수있겠군요..

seoleda의 이미지

고스톱을 칠때, 카드패를 어떻게 돌리는지 생각해 보세요.

바닥에 놓고서 대충 섞다가 섞다가, 가장 위에서 부터 하나씩 차례로 나눠 줍니다.

결과적으로, 게임에 참여한 사람들은 중복되지 않는 랜덤한 카드를 받았겠지요.

이러한 생활 속의 지혜를 이용하면,

1) 10000개의 배열을 잡고
2) 차례로 0~9999까지 배열에 넣습니다.
3) 아무 인덱스나 랜덤하게 2개를 뽑아서, 두 곳을 배열의 값을 바꿈니다.
4) 3의 과정을 여러번 반복합니다.
(이 과정에서 고스톱의 통 이라던지 옆사람이 한번 덜어 내는 과정을 추가하시면 더 좋습니다. ^^)
5) 10000개의 배열에는 무작위 순서로 숫자가 배열되어 있으므로, 차례로 하나씩 나누어 줍니다.

p.s. 하나의 숫자가 반드시 중복되어야 하는 경우는 ...
음~ 숙제 입니다. ^^ 조금만 생각하면 간단합니다.

target01의 이미지

초보라서 글로는 잘 이해가 안가는군요..소스로 표현을 좀 해주시면 감솨하겟습니다..

auditory의 이미지


seoleda님의 방법은 일반적인 random permutation 문제이고
원글의 문제는 이것보다 더 복잡한 문제처럼 보이네요.

그냥 랜덤 셔플링을 이만번 반복하는게 제일 간단해보이는데
이렇게만해서는 동일한 2개의 번호가 같은 위치에 발생하는걸 막을 수가 없네요..

3차원 큐브를 채우는것처럼 한번의 랜덤셔플링에서
하나의 카드번호를 다 채우고
동시에 다른 카드(1만장)의 같은 번호를 다채우는 방법인데..
이러면 모든 1개의 번호도 중복되지 안을텐데
그러면 1만장까지밖에 채울수가 없네요..

select99의 이미지

제가 왜 여기다 리플을 붙였는지 모르겠습니다..^^
아이디 s 자만보고 전줄알고..^
---------------------------------------
문제를 처음에 약간 잘못이해했군요..

은행업무하시는모양이지요?^^
좀무식한방법을써야겠군요.. 2차원배열 30 X 5만개 만드시고..

숫자하나 발번할때마다 기존 발번된 데이터들을 체크하시고..발번한 숫자들은 모두 기록하시면되겠네요..

효율성은 고려하지 않았지만.. 50000번째 카드 발번하는경우를 생각해보니..
50000 x 30 x 30 번이상 숫자를 비교해야될수도 있겠군요....
C로 작성되었다면 1~수초내로 나오겠군요..
자바라면... 장담 못하겠군요..

seoleda의 이미지

가만히 생각해 보니 마방진과 비슷하군요.

제 생각에는 1000개의 숫자를 40개씩 250개의 서로 소인 그룹으로 분리하고,

1) 30*200 (50000/250=200) 의 배열을 생성하고,

2) 40개의 숫자를 배열의 행과 열에 중복하지 않도록 배치하면,

하나의 그룹에서 40개의 숫자를 가지고 200개의 카드를 생성할 수 있고,

그러한 그룹에 250개니깐, 50000 (200*250)개의 카드를 생성할 수 있지 않을까요?

30*50000의 마방진보다는 30*200의 마방진이 조금 풀기 수월할 테니까요.

p.s. 그런데 중복을 허용하지 않고 그 정도 크기의 순열을 생성 할 수 있는지는 좀더 생각해 보아야 할 것 같습니다.

auditory의 이미지

이렇게 하면 어떨까요..
1번의 중복은 허용한다고 했으니..최대 2만장까지 만들수 있을것 같습니다..

for i=0:20000
arr[i] = i/2; // arr[i] 는 integer
end

for iteration=0:infinity
r1=random(0,20000);
r2=random(0,20000);
swap(arr[r1],arr[r2])
end

for i=0:20000
card[i].j = arr[i]
end

위의 과정을 j=0:30까지 30번 반복해서 모든카드에 번호를 채웁니다..

여기까지하면 모든 카드의 같은 자리에는 1개씩만 중복이 있습니다.
하지만 한카드에 여러난수가 중복될 수 있습니다.

이제 각 카드를 검사하면서 한 카드에 여러 숫자가 중복되어있으면
그 숫자가 없는 다른 카드에서 같은 위치에 있는 숫자와 swap하게 합니다..

시간적으로 더 효율적인 방법이 있을듯도한데
이렇게해도 주어진 조건은 다 만족시킬 수 있을것 같습니다..

target01의 이미지

음..먼저 0001~ 9999번까지를 배열에 담습니다. 그리고 위 9999개의 배열중에 무작위랜덤으로 30개를 추출하여 하나의 보안카드를 만듭니다.
그리고 다음카드를 만들기 위해 다시 30개의 랜덤배열을 다시 추출하여 카드에 넣을때 기존의 위치에 새로 추출한 난수가 있는지 체크하고 그 번호가 잇으면 다른 위치로 보냅니다.그러니까 하나의 난수가 그 위치에 한번만 오는거죠.
이렇게하면 20만장 이상의 카드를 만들수 있지 않을까요???
계산 : 30개의 자리중 다음에 올수있는경우 29 * 9999 = 280000 ..이 나오네요.
구현하기가 좀 어려운가요??아니면 제 생각이 잘못된건가요??

blueiur의 이미지

저같은 경우 Seed값을 바꾸어 30개를 계속 생성했을때,
20만개 생성 후에 비교하면 20만개 카드가 동일한 자리에 2개가 겹춰지지 않더군요 ..

아래는 C# 코드입니다.

using System;
using System.IO;
 
namespace Randomize
{
	class CCard
	{
		private const int MAX_NUM = 30;
		private int[] numbers = new int[MAX_NUM];
 
		public CCard(int seed)
		{			
			Init(seed);
		}
 
		public void Init(int seed)
		{			
			Random rnd = new Random(seed);
			for(int i=0; i<MAX_NUM; i++)
			{
				numbers[i] = rnd.Next(1000, 10000);
			}			
		}
 
		public bool CompareTo(CCard cd )
		{
			int sameNumCount = 0;
 
			for(int i=0; i<MAX_NUM; i++)
			{
				if(numbers[i] == cd[i])
				{					
					if(++sameNumCount ==2)
						return true;
				}													
			}			
			return false;
		}
 
		public void print()
		{
			for(int i=0; i<MAX_NUM; i++)
			{
				if(i%5 == 0 && i !=0)
					Console.WriteLine();
 
				Console.Write(numbers[i]+ " ");                
			}
            Console.WriteLine();
            Console.WriteLine();                
		}
 
		public int this[int index]
		{
			get
			{
				if(index < MAX_NUM)
					return numbers<ol>
</ol>
;
				else
					throw new ArgumentException();
			}
			set
			{
				if(index < MAX_NUM)
					this.numbers<ol>
</ol>
 = value;
				else
					throw new ArgumentException();				
			}
		}		
	}
 
	class CRandom
	{
		[STAThread]
		static void Main(string[] args)
		{
		    const int MAX_CARD = 20000;
            CCard[] cardList = new CCard[MAX_CARD];
 
            FileStream fs = new FileStream("C:\\test.txt", FileMode.Create);
            StreamWriter sw = new StreamWriter(fs);
 
            for (int i = 0; i < cardList.Length; i++)
            {
                cardList[i] = new CCard(i);
                for (int j = 0; j < 30; j++)
                {
                    if (j % 5 == 0)
                        sw.WriteLine();  
 
                    sw.Write(cardList[i][j] + " ");                    
                }
                sw.WriteLine();
                sw.WriteLine();
            }                   
            fs.Close();
 
            // check for duplicate
            for (int i = 0; i < cardList.Length-1; i++)
            {
                for (int j = i + 1; j < cardList.Length - 1; j++)
                {
                    if (cardList[i].CompareTo(cardList[j]))
                    {
                        Console.WriteLine("Duplicate");
                    }
                }
            }              
		}
	}
}
blueiur의 이미지

test file ..

댓글 첨부 파일: 
첨부파일 크기
Plain text icon test.txt3.17 MB
auditory의 이미지

2만장 초과는 절대 불가능할 것 같은데요..
구현의 문제가 아니라 이론적으로요..

1만개의 숫자를 한번만 중복을 허용한다고 했으니 총 숫자의 가지수는 2만개인데
카드가 2만장 초과면 어떻게하든 적어도 3번이상 같은 숫자가 같은 자리에 나올 수 밖에 없죠..

어렵게 말하면 비둘기집의 원리에 의해서요.. ^^

===

저도 문제를 잘 못 이해한듯..
같은 자리에 3번이상 못나오는게 아니라
같은 pair가 3번이상 못나오는거군요..
그럼 2만장 초과 불가는 헛소리네요..

방법은.. 글쎄요..
그냥 하나씩 차례로 무작위로 만들고
만들때마다 이전에 만든 모든 카드와 비교!
이정도 밖에 안 떠오르네요..

혼란을 드려 죄송~

ironiris의 이미지

0000 0001 0002 0003 ~ 0099
0100 0101 0102 0103 ~ 0199
~~~~
9900 9901 9902 9903 ~ 9999

이 배열을 한번 shuffle 해주시고
30개씩 추려야 하니까 가로 6, 세로 5개씩 추리면 30개가 되니까. 그 직사각형의 틀을 한칸씩 옮기면 될것으로 보입니다.
물론 수십장의 카드를 모으면 예측이 가능하다는 헛점은 있지만 같은 자리에 같은 숫자가 들어올 일은 없습니다.

auditory의 이미지

직사각형 틀을 옮기는 것을 circular shift하는 경우
100x100 = 일만장의 카드만 만들어지네요..
숫자를 두번씩 반복해서 쓰면 이만장의 카드가 만들어지겠지요..

두 고객의 카드가 숫자들이 그냥 1x1 shift 라는 단점은
random이라는 의미하고는 많이 달라서
실전에 쓰기에는 좀 어려울것 같습니다..

jiee의 이미지

카드 한 장에 30개의 숫자가 들어가므로, 각 자리에 ID를 부여함.

ex) {ID:1, ID:2, ,,, ID:30}

1. 이 30개 ID집합의 순열을 구합니다. (만들 카드가 5만장이면 5만개까지만..)
- 이 과정은 같은 위치에 같은 난수가 들어가는 것을 막기위함입니다.
ex)
{1, 2, 3, 4, ,,, 30}
{2, 3, 4, 5, ,,30, 1}
...
{24, 28, 1, 4, ,,,}
순열의 총 개수가 30!이므로 5만개는 충분히 커버합니다.

2. 이제 0~9999의 수를 shuffle합니다.
ex) orgin set{0, 1, 2, ,,, 9999} -(shuffle)-> {2845, 2938, 694, 87, ,,, 3956} shuffled set

3. shuffled set을 30개의 ID에 분배되도록 자릅니다. (30x333 ~= 10000이므로 한 ID당 333개의 수를 할당합니다.

4. 이제 각 ID(1~30)를 shuffle된 집합의 원소와 매칭시킵니다.
ex) ID:1 = {9, 4514, 567, ,,, 44}(총 333개)
ID:2 = {567, 8251, 457, ,,, 9814}
...
ID:30 = {6978, 514, 5789, ,,, 91}
!매칭시에도 1~333개의 순열을 구해서 중복된 위치의 원소가 ID에 매칭되지 않도록 합니다.

이렇게 하면,
위 조건을 모두 충족시키리라 생각됩니다.

ps. 틀린 점 있으면, 알려주세요..-_-a 점심먹은 뒤라 정신이 몽롱..

토나오게...

auditory의 이미지


댓글 달기

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