ATUALIZAÇÃO: de acordo com os comentários, vamos fazer alguns esclarecimentos.

Estou tentando entender a solução para a seguinte tarefa: Gere aleatoriamente um conjunto de elementos M a partir de uma matriz de tamanho N. Cada elemento deve ter a mesma probabilidade de ser escolhido.

Encontrei a seguinte solução (eu já liessa questão, mas não responde à minha pergunta):

int rand(Random random, int min, int max) {
  return random.nextInt(1 + max - min) + min;
}

char[] generateArray(char[] original, int subsetSize) {
  char[] subset = new char[subsetSize];
  Random random = new Random();

  for (int i = 0; i < subsetSize; i++) {
    subset[i] = original[i];
  }
  for (int i = subsetSize; i < original.length; i++) {
    int r = rand(random,0, i);
    boolean takeIthElement = r < subsetSize;
    if (takeIthElement) {
      subset[r] = original[i];
    }
  }

  return subset;
}
// rand() function returns inclusive value 
// i.e. rand(0, 5) will return from 0 to 5

Este código foi encontrado no livro "Cracking the coding entrevista" (Seção Hard, Tarefa 3). O autor explica o seguinte:

Suponha que tenhamos um algoritmo capaz de extrair um conjunto aleatório dem elementos de uma matriz de tamanhon - 1. Como podemos usar esse algoritmo para extrair um conjunto aleatório dem elementos de uma matriz de tamanhon? Podemos primeiro extrair um conjunto aleatório de tamanho m do primeiron - 1 elementos. Então, só precisamos decidir searray[n] deve ser inserido em nosso subconjunto (o que exigiria a retirada de um elemento aleatório). Uma maneira fácil de fazer isso é escolher um número aleatório k de 0 a n. E sek < me insiraarray[n] para dentrosubset[k]. Isso inserirá "razoavelmente" (ou seja, com probabilidade proporcional)array[n] no subconjunto e remova "razoavelmente" um elemento aleatório do subconjunto. É ainda mais limpo escrever iterativamente. Nesta abordagem, inicializamos um subconjunto de matriz para ser o primeirom elementos no original. Em seguida, iteramos pela matriz, começando no elementominserindoarray[i] no subconjunto na posição (aleatória)k sempre quek < m.

Eu acho que o autor queria dizer que precisamos gerarnão configurado, mas matriz. Portanto, acho que as descrições de tarefas corretas devem ser: Gere aleatoriamente ummatriz de elementos M a partir de uma matriz de tamanho N. Cada elemento deve ter a mesma probabilidade de ser escolhido.

Se for verdade, o código acima não funciona corretamente. Razões:

Por exemplo, temos uma matriz{'1', '2', 'a', 'b'} em = 2Portanto, devemos ter probabilidades qualificadas para gerar os seguintes conjuntos:

{1, 2}; {2, 1}; {1, a}; {a, 1}; {1, b}; {b, 1}; {a, 2}; {2, a}; {b, 2}; {2, b}; {a, b}; {b, a}

Minha preocupação aqui é que a função nunca irá gerar os seguintes conjuntos:{2, 1}; {2, a}; {2, b}

Então, isso significa que está incorreto.