[C#] C #의 List <T>에서 N 개의 임의 원소 선택

많은 수학적으로 수정 된 솔루션이 실제로 모든 가능성에 도달하지 못하기 때문에 이는 실제로는 생각보다 어려운 문제입니다 (아래에서 자세히 설명).

먼저, 구현하기 쉽고 정확한 경우 임의 숫자 생성기가 있습니다.

(0) Kyle의 대답은 O (n)입니다.

(1) n 쌍 [(0, rand), (1, rand), (2, rand), …]의 목록을 생성하고 두 번째 좌표로 정렬하고 첫 번째 k를 사용하십시오 (k는 = 5) 임의의 부분 집합을 구하는 지수. O (n log n) 시간이지만 구현하기가 쉽다고 생각합니다.

(2) 빈 목록 s = []를 초기화하여 k 개의 랜덤 원소의 인덱스가되도록합니다. 무작위로 {0, 1, 2, …, n-1}에서 숫자 r을 선택하고 r = rand % n을 s에 추가하십시오. 다음으로 r = rand % (n-1)을 취하고 s를 고수하십시오. 충돌을 피하기 위해 s보다 # 요소를 r에 더하십시오. 다음으로 r = rand % (n-2)를 취하고 s에 k 개의 고유 한 요소가있을 때까지 동일한 작업을 수행하십시오. 최악의 경우 실행 시간이 O (k ^ 2)입니다. k << n의 경우 더 빠를 수 있습니다. 정렬을 유지하고 인접한 간격을 추적하면 O (k log k)로 구현 할 수 있지만 더 많은 작업입니다.

@Kyle-네 말이 맞아, 나는 네 대답에 동의한다고 생각했다. 나는 처음에 급히 그것을 읽었고, 실수로 고정 확률 k / n을 가진 각 요소를 순차적으로 선택한다고 잘못 생각하고 있었지만 잘못 생각했을 것입니다. 미안합니다.

자, 이제 키커 : 무증상 (고정 k, n 증가)에는 n ^ k / k가 있습니다! n 개의 요소 중 k 개의 요소 서브 세트의 선택 [이것은 근사치 (n choose k)]입니다. n이 크고 k가 그다지 작지 않으면이 숫자는 엄청납니다. 표준 32 비트 난수 생성기에서 기대할 수있는 최상의 사이클 길이는 2 ^ 32 = 256 ^ 4입니다. 따라서 1000 개의 요소 목록이 있고 무작위로 5를 선택하려는 경우 표준 난수 생성기가 모든 가능성을 달성 할 방법이 없습니다. 그러나 더 작은 세트에 대해 잘 작동하고 항상 “임의로”보이는 선택에 만족하는 경우 이러한 알고리즘은 정상입니다.

부록 :이 글을 쓴 후에는 아이디어 (2)를 올바르게 구현하는 것이 까다 롭다는 것을 깨달았 으므로이 대답을 분명히하고 싶었습니다. O (k log k) 시간을 얻으려면 O (log m) 검색 및 삽입을 지원하는 배열과 유사한 구조가 필요합니다. 균형 잡힌 이진 트리가이를 수행 할 수 있습니다. 이러한 구조를 사용하여 s라는 배열을 작성하면 의사 파이썬이 있습니다.

# Returns a container s with k distinct random numbers from {0, 1, ..., n-1}
def ChooseRandomSubset(n, k):
  for i in range(k):
    r = UniformRandom(0, n-i)                 # May be 0, must be < n-i
    q = s.FirstIndexSuchThat( s[q] - q > r )  # This is the search.
    s.InsertInOrder(q ? r + q : r + len(s))   # Inserts right before q.
  return s

위의 영어 설명을 효율적으로 구현하는 방법을 확인하기 위해 몇 가지 샘플 사례를 검토하는 것이 좋습니다.

답변

    static IEnumerable<SomeType> PickSomeInRandomOrder<SomeType>(
        IEnumerable<SomeType> someTypes,
        int maxCount)
    {
        Random random = new Random(DateTime.Now.Millisecond);

        Dictionary<double, SomeType> randomSortTable = new Dictionary<double,SomeType>();

        foreach(SomeType someType in someTypes)
            randomSortTable[random.NextDouble()] = someType;

        return randomSortTable.OrderBy(KVP => KVP.Key).Take(maxCount).Select(KVP => KVP.Value);
    }

  for i from n − 1 downto 1 do
       j ← random integer with 0 ≤ j ≤ i
       exchange a[j] and a[i]

  for (i = n − 1; i >= n-k; i--)
  {
       j = random integer with 0 ≤ j ≤ i
       exchange a[j] and a[i]
  }

 .AsEnumerable().OrderBy(n => Guid.NewGuid()).Take(5);