목록에서 n 개의 임의 요소 가져 오기

목록에서 n 개의 임의 요소 가져 오기?

---

에서 n 개의 임의의 요소를 ArrayList<E>어디에서 있습니까? 이상적으로는 take()대체하지 않고 다른 x 요소를 소유하기 위해 메소드를 연속적으로 호출 할 수 있기를 바랍니다 .

---

두 가지 주요 방법.

1. 사용 :Random#nextInt(int)

   List<Foo> list = createItSomehow();
   Random random = new Random();
   Foo foo = list.get(random.nextInt(list.size()));
   

   그러나 연속 n호출이 고유 한 요소를 반환 보장은 없습니다 .

2. 사용 :Collections#shuffle()

   List<Foo> list = createItSomehow();
   Collections.shuffle(list);
   Foo foo = list.get(0);
   

   통해이를 n증가 된 인덱스로 고유 한 요소 를 가져올 수 있습니다 (목록 자체에 고유 한 요소가 포함 되어 있다고 가정 ).

---

Java 8 Stream 접근 방식이 궁금한 경우; 아니요, 기본 제공되지 않습니다. Comparator#randomOrder()표준 API 와 같은 것은 없습니다 (아직?). 엄격한 Comparator계약을 시도 할 수 있습니다. (배포가 꽤 끔찍하지만).

List<Foo> list = createItSomehow();
int random = new Random().nextInt();
Foo foo = list.stream().sorted(Comparator.comparingInt(o -> System.identityHashCode(o) ^ random)).findFirst().get();

Collections#shuffle()대신 더 잘 사용하십시오 .

---

지금까지 고유 제안 된 대부분의 솔루션은 시도하여 전체 목록 셔플 또는 연속 선택을 제안합니다.

그러나 Durstenfeld 알고리즘 (당시 가장 인기있는 Fisher-Yates 변형)을 사용할 수 있습니다.

Durstenfeld의 해결은 "struck"번호를 각 반복에서 마지막으로 확인되지 않은 번호로 교체하여 목록의 끝으로 이동하는 것입니다.

위의 사항으로 인해 전체 목록을 섞을 필요는 없지만 필요한 요소 수만큼 많은 단계에 대해 루프를 실행합니다. 이 알고리즘은 우리가 완벽한 랜덤 함수를 사용할 경우 목록 마지막 N 개의 요소가 100 % 랜덤임을 보장합니다.

배열 / 목록에서 미리 정해진 (최대) 양의 임의의 요소를 선택해야하는 많은 실제 시나리오 중에서 최적화 된 방법은 사용자가 사전에 숫자를있는 Texas Poker와 같은 다양한 카드 게임에 매우 유용합니다. 게임당 사용할 카드 수; 일반적으로 덱에는 수의 카드 만 필요합니다.

public static <E> List<E> pickNRandomElements(List<E> list, int n, Random r) {
    int length = list.size();

    if (length < n) return null;

    //We don't need to shuffle the whole list
    for (int i = length - 1; i >= length - n; --i)
    {
        Collections.swap(list, i , r.nextInt(i + 1));
    }
    return list.subList(length - n, length);
}

public static <E> List<E> pickNRandomElements(List<E> list, int n) {
    return pickNRandomElements(list, n, ThreadLocalRandom.current());
}

---

목록에서 n 개의 요소를 연속적으로 선택하고 계속해서 교체하지 않고 그렇게 할 수있는 요소를 무작위로 순열 한 다음 n 개의 블록에서 청크를 제거하는 것이 가장 좋습니다. 목록을 무작위로 수정하면 선택한 각 블록에 대한 통계적 무작위성을 보장합니다. 이 작업을 수행하는 가장 쉬운 방법은 .Collections.shuffle

---

간단하고 명확함

   // define ArrayList to hold Integer objects
    ArrayList<Integer> arrayList = new ArrayList<>();

    for (int i = 0; i < maxRange; i++) {
        arrayList.add(i + 1);
    }

    // shuffle list
    Collections.shuffle(arrayList);

    // adding defined amount of numbers to target list
    ArrayList<Integer> targetList = new ArrayList<>();
    for (int j = 0; j < amount; j++) {
        targetList.add(arrayList.get(j)); 
    }

    return targetList;

---

이 작업을 수행하는 공정한 방법은 n 번째 반복에서 목록을보고 n 번째 요소를 선택지 여부를 계산하는 것입니다. 이는 기본적으로 요소 수에 대해 선택해야하는 항목 수의 비율입니다. 나머지 목록에서 사용할 수 있습니다. 예를 들면 :

public static <T> T[] pickSample(T[] population, int nSamplesNeeded, Random r) {
  T[] ret = (T[]) Array.newInstance(population.getClass().getComponentType(),
                                    nSamplesNeeded);
  int nPicked = 0, i = 0, nLeft = population.length;
  while (nSamplesNeeded > 0) {
    int rand = r.nextInt(nLeft);
    if (rand < nSamplesNeeded) {
      ret[nPicked++] = population[i];
      nSamplesNeeded--;
    }
    nLeft--;
    i++;
  }
  return ret;
}

(이 코드는 목록에서 무작위 샘플 을 고르기 위해 무작위 샘플 을 내가 복사했습니다 .)

---

다음 클래스를 사용하십시오.

import java.util.Enumeration;
import java.util.Random;

public class RandomPermuteIterator implements Enumeration<Long> {
    int c = 1013904223, a = 1664525;
    long seed, N, m, next;
    boolean hasNext = true;

    public RandomPermuteIterator(long N) throws Exception {
        if (N <= 0 || N > Math.pow(2, 62)) throw new Exception("Unsupported size: " + N);
        this.N = N;
        m = (long) Math.pow(2, Math.ceil(Math.log(N) / Math.log(2)));
        next = seed = new Random().nextInt((int) Math.min(N, Integer.MAX_VALUE));
    }

    public static void main(String[] args) throws Exception {
        RandomPermuteIterator r = new RandomPermuteIterator(100);
        while (r.hasMoreElements()) System.out.print(r.nextElement() + " ");
    }

    @Override
    public boolean hasMoreElements() {
        return hasNext;
    }

    @Override
    public Long nextElement() {
        next = (a * next + c) % m;
        while (next >= N) next = (a * next + c) % m;
        if (next == seed) hasNext = false;
        return  next;
    }
}

---

임의의 요소를 계속 선택하고 요소를 다시 선택하지 마십시오.

public static <E> List<E> selectRandomElements(List<E> list, int amount)
{
    // Avoid a deadlock
    if (amount >= list.size())
    {
        return list;
    }

    List<E> selected = new ArrayList<>();
    Random random = new Random();
    int listSize = list.size();

    // Get a random item until we got the requested amount
    while (selected.size() < amount)
    {
        int randomIndex = random.nextInt(listSize);
        E element = list.get(randomIndex);

        if (!selected.contains(element))
        {
            selected.add(element);
        }
    }

    return selected;
}

이론적으로는 끝없이 말할 수 있습니다 실제로는 괜찮습니다. 전체 원본 목록에 가까울수록 실행이 느려질 수 있습니다. 임의의 하위 목록을 선택하는 요점은 아닙니다.

---

다른 답변에서 언급했듯이 Collections.shuffle복사 때문에 소스 목록이 클 때별로 효율적이지 않습니다. 다음은 Java 8 한 줄짜리입니다.

• 소스에서 많은 요소가 필요하지 않은 경우 ArrayList와 같은 임의 액세스 목록에서 충분히 효율적입니다.
• 소스를 수정하지 않습니다
• 귀하에게 매우 중요하지 않은 경우 고유성을 보장하지 않습니다. 100 개 중에서 5 개를 선택하면 요소가 고유 할 가능성이 매우 높습니다.

암호:

private static <E> List<E> pickRandom(List<E> list, int n) {
  return new Random().ints(n, 0, list.size()).mapToObj(list::get).collect(Collectors.toList());
}

그러나 빠른 임의 액세스가없는 목록 (예 : LinkedList)의 경우 복잡성은 n*O(list_size).

---

다음 클래스는 모든 유형의 목록에서 N 개의 항목을 검색합니다. 시드를 제공하면 각 실행에서 동일한 목록이 반환되고 그렇지 않으면 새 목록의 항목이 각 실행에서 변경됩니다. 주요 메서드를 실행하는 동작을 확인할 수 있습니다.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Random;

public class NRandomItem<T> {
    private final List<T> initialList;

    public NRandomItem(List<T> list) {
        this.initialList = list;
    }

    /**
     * Do not provide seed, if you want different items on each run.
     * 
     * @param numberOfItem
     * @return
     */
    public List<T> retrieve(int numberOfItem) {
        int seed = new Random().nextInt();
        return retrieve(seed, numberOfItem);
    }

    /**
     * The same seed will always return the same random list.
     * 
     * @param seed,
     *            the seed of random item generator.
     * @param numberOfItem,
     *            the number of items to be retrieved from the list
     * @return the list of random items
     */
    public List<T> retrieve(int seed, int numberOfItem) {
        Random rand = new Random(seed);

        Collections.shuffle(initialList, rand);
        // Create new list with the number of item size
        List<T> newList = new ArrayList<>();
        for (int i = 0; i < numberOfItem; i++) {
            newList.add(initialList.get(i));
        }
        return newList;
    }

    public static void main(String[] args) {
        List<String> l1 = Arrays.asList("Foo", "Bar", "Baz", "Qux");
        int seedValue = 10;
        NRandomItem<String> r1 = new NRandomItem<>(l1);

        System.out.println(String.format("%s", r1.retrieve(seedValue, 2)));
    }
}

참고 URL : https://stackoverflow.com/questions/4702036/take-n-random-elements-from-a-liste