중복 없는 랜덤 뽑기
중복 없는 랜덤 뽑기를 위해 몇가지 방법을 찾아왔다
현재 목록중 3개를 뽑는걸 목표로 하기에 1번째걸 뽑은후 2번째 ,3번째가 앞선것에 중복되지 않는걸 뽑는걸 목표로 하고 잇따
중복이면 한번더 해서 다시뽑기
using System;
using System.Linq; // 배열 초기화 - Enumerable 사용
static void Main(string[] args)
{
Random random = new Random();
int N = Convert.ToInt32(Console.ReadLine());
bool[] selected = Enumerable.Repeat<bool>(false, N).ToArray<bool>();
int selectedCnt = 0;
while(selectedCnt < N)
{
int a = random.Next(0, N); // 1에서 N-1까지
if(selected[a] == true)
{
continue;
}
Console.Write($"{a} ");
selected[a] = true;
selectedCnt++;
}
}이 방법은 최소 N의 시간이 걸리지만 최대 무한대의 시간이 걸릴 수도 있는 방법
심플하게 생각했을때 이방법이였는데 찾아보니 운이 나쁘다면 계속 뽑을걸 뽑아 이론상 무한한 시간이 걸릴수가 있다
표본이 적을수록 더 더욱 위험
연속으로 뽑기
제목 그대로, 이미 뽑은 것을 뽑았다면 그 다음 것을, 그것도 이미 뽑았다면 또 그 다음 것을 뽑는 방식입니다.
using System;
using System.Linq; // 배열 초기화 - Enumerable 사용
static void Main(string[] args)
{
Random random = new Random();
int N = Convert.ToInt32(Console.ReadLine());
bool[] selected = Enumerable.Repeat<bool>(false, N).ToArray<bool>();
int selectedCnt = 0;
while(selectedCnt < N)
{
int a = random.Next(0, N); // 1에서 N-1까지
while(selected[a] == true)
{
a = (a+1) % N;
}
Console.Write($"{a} ");
selected[a] = true;
selectedCnt++;
}
}서론에서 언급한 코드에서 if문 내부만 바꿔주어 간단하게 구현할 수 있으며 O(N²)의 시간복잡도로 예측가능한 실행시간을 가졌으나, 이 방법으로 얻는 랜덤값은 확률적으로 오류가 있습니다.
간단하게 1에서 3까지의 숫자를 뽑는 중에 이미 1을 뽑은 상태라고 해봅시다. 오류가 없다면, 이 때 2를 뽑을 확률과 3을 뽑을 확률은 같아야 하겠죠. 하지만 위 알고리즘의 경우 1을 뽑으면 그 다음 원소인 2를 뽑아야 하기 때문에 (2를 뽑을 확률 = 1을 뽑을 확률 + 2를 뽑을 확률 = 2/3) ≠ (3을 뽑을 확률 = 1/3) 이므로 확률에 오류가 있음을 알 수 있습니다.
모집단이 커질수록 이 확률의 차이는 무시해도 될 만큼 작아지며, 구현이 아주 간단하기 때문에, 모집단이 크고 확률의 정확도가 그리 중요하지 않은 경우에 쓰면 좋습니다. 다만 확률이 정확하면 훨씬 좋겠죠.
요약
심플하게 n을뽑았을때 다음은 n+1, n+2를 가져오는 방법 심플하고 목록이 많다면 좋지만 이경우 n을뽑았을경우 다음것이 무조건 n+1 이 고정되 버리기에 랜덤이라고 하기 조금 애매하다 리스트를 계속 섞어준다면 모르겠지만 굳이 섞고 싶지 않다
2. 모집단의 인덱스를 랜덤으로 뽑고, 모집단에서 원소 제거.
List<int> list에 1부터 n까지의 원소를 채운다.
list의 크기는 현재 n.
0~(n-1)의 숫자 중 "인덱스"를 랜덤으로 뽑고 해당 인덱스의 원소를 삭제한다.
list의 크기는 현재 (n-1).
0~(n-2)의 숫자 중 "인덱스"를 랜덤으로 뽑고 해당 인덱스의 원소를 삭제한다. ...
이러한 과정을 반복해서 뽑는 것입니다.
using System;
using System.Linq; // 배열 초기화 - Enumerable 사용
static void Main(string[] args)
{
Random random = new Random();
int N = Convert.ToInt32(Console.ReadLine());
bool[] selected = Enumerable.Repeat<bool>(false, N).ToArray<bool>();
int selectedCnt = 0;
while(selectedCnt < N)
{
int a = random.Next(0, N); // 1에서 N-1까지
while(selected[a] == true)
{
a = (a+1) % N;
}
Console.Write($"{a} ");
selected[a] = true;
selectedCnt++;
}
}O(N²)의 시간복잡도로, 실행 시간을 예측가능한 상태로 랜덤을 뽑을 수 있으며, 위의 방법과는 달리 우리가 통상적으로 생각하는 비복원 추출을 그대로 구현했기 때문에 확률도 정확합니다. 다만 메모리를 더 쓴다는 단점이 있는데,
내가 적용한 코드 - 목록에서 아예 제거
void Start()
{
test(MakeStatBonusList.stat1);
}
void test(List<Istat> origin)
{
int Count = picklist.Length;
Debug.Log(Count);
//여기서 스탯증강인지 특수 증강인지에 따라투리스트할지 그냥 받을지
List<Istat> list = origin.ToList();
for (int i = 0; i < Count; ++i)
{
int a = Random.Range(0, list.Count);
Debug.Log(a);
ChoiceSlot temp = picklist[i].GetComponent<ChoiceSlot>();
temp.stat = list[a];
picklist[i].gameObject.SetActive(true);
list.RemoveAt(a);
}
}리스트에서 제거하기 리스트를 불러온후 count 갯수만큼 뽑고 뽑은걸 제거하기
현재 리스트에서 뽑은것을 앞으로는 안나오게 하는방법과
뽑은 것이 다시 등장할수 있는 상태의 리스트 2개가 필요한데
위에 코드는 리스트를 클론으로 만들었기에 뽑은게 계속 리스트에 남아있음