Algoritmo para selecionar uma combinação única e aleatória de valores?

Digamos que eu tenha valores distintos e quero selecionar x deles aleatoriamente. O que é um algoritmo eficiente para fazer isso? Eu poderia simplesmente chamar rand() x times, mas o desempenho seria ruim se x , y fosse grande.

Note que são necessárias combinações aqui: cada valor deve ter a mesma probabilidade de ser selecionado, mas sua ordem no resultado não é importante. Claro, qualquer algoritmo que gerasse permutações se qualificaria, mas gostaria de saber se é possível fazer isso de maneira mais eficiente sem o requisito de ordem aleatória.

Como você gera eficientemente uma lista de K inteiros não repetidos entre 0 e um limite superior? N cobre este caso para permutações.

Robert Floyd inventou um algoritmo de amostragem para essas situações. Geralmente é superior a embaralhar e depois pegar os primeiros x elementos, já que não requer armazenamento de O (y). Como originalmente escrito, ele assume valores de 1..N, mas é trivial produzir 0..N e / ou usar valores não-contíguos simplesmente tratando os valores que ele produz como subscripts em um vetor / array / whatever.

No pseuocode, o algoritmo funciona assim (roubando da coluna Programming Pearls de Jon Bentley “Uma amostra de Brilliance”).

 initialize set S to empty for J := NM + 1 to N do T := RandInt(1, J) if T is not in S then insert T in S else insert J in S 

Esse último bit (inserindo J se T já estiver em S) é a parte complicada. A linha inferior é que assegura a probabilidade matemática correta de inserir J de modo que produza resultados imparciais.

É O (x) 1 e O (1) em relação ao armazenamento de y , O (x) .

Note que, de acordo com a tag combinações na questão, o algoritmo apenas garante a igualdade de probabilidade de cada elemento que ocorre no resultado, não da ordem relativa deles no mesmo.


1 O (x 2 ) no pior dos casos para o mapa hash envolvido, que pode ser desprezado, pois é um caso patológico praticamente inexistente, onde todos os valores têm o mesmo hash

Supondo que você quer que o pedido seja random também (ou não se importe em ser random), eu usaria apenas um shuffle truncado de Fisher-Yates. Inicie o algoritmo de reprodução aleatória, mas pare depois de selecionar os primeiros valores x , em vez de “selecionar aleatoriamente” todos os y deles.

Fisher-Yates funciona da seguinte maneira:

  • selecione um elemento aleatoriamente e troque-o pelo elemento no final da matriz.
  • Recurse (ou mais provavelmente iterar) no restante da matriz, excluindo o último elemento.

Etapas após o primeiro não modificam o último elemento da matriz. Passos após os dois primeiros não afetam os dois últimos elementos. Etapas após o primeiro x não afetam os últimos elementos x. Então, nesse ponto, você pode parar – o topo da matriz contém dados selecionados uniformemente aleatoriamente. A parte inferior da matriz contém elementos um pouco randoms, mas a permutação que você obtém deles não é uniformemente distribuída.

É claro que isso significa que você jogou fora a matriz de input – se isso significa que você precisa fazer uma cópia antes de iniciar, e x é pequeno comparado com y, então copiar toda a matriz não é muito eficiente. Note que, se tudo o que você vai usar no futuro é mais seleções, então o fato de estar em uma ordem um tanto aleatória não importa, você pode simplesmente usá-la novamente. Se você fizer a seleção várias vezes, poderá fazer apenas uma cópia no início e amortizar o custo.

Se você realmente só precisa gerar combinações – onde a ordem dos elementos não importa – você pode usar combinadics como eles são implementados, por exemplo, aqui por James McCaffrey .

Compare isso com k-permutações , onde a ordem dos elementos é importante.

No primeiro caso (1,2,3) , (1,3,2) , (2,1,3) , (2,3,1) , (3,1,2) , (3,2,1 ) são considerados os mesmos – no segundo, são considerados distintos, embora contenham os mesmos elementos.

No caso de você precisar de combinações, você pode realmente precisar gerar apenas um número random (embora possa ser um pouco grande) – que pode ser usado diretamente para encontrar a combinação m . Como esse número random representa o índice de uma combinação específica, segue-se que seu número random deve estar entre 0 e C (n, k) . O cálculo de combinações pode levar algum tempo também.

Pode não valer a pena – além da resposta de Jerry e Federico é certamente mais simples do que implementar combinadics. No entanto, se você realmente só precisa de uma combinação e você está grampeado sobre como gerar o número exato de bits randoms que são necessários e nenhum mais … 😉

Embora não esteja claro se você deseja combinações ou permutas de k, aqui está um código em C # para o último (sim, poderíamos gerar apenas um complemento se x> y / 2, mas então teríamos uma combinação que deveria ser embaralhado para obter uma real permutação de k):

 static class TakeHelper { public static IEnumerable TakeRandom( this IEnumerable source, Random rng, int count) { T[] items = source.ToArray(); count = count < items.Length ? count : items.Length; for (int i = items.Length - 1 ; count-- > 0; i--) { int p = rng.Next(i + 1); yield return items[p]; items[p] = items[i]; } } } class Program { static void Main(string[] args) { Random rnd = new Random(Environment.TickCount); int[] numbers = new int[] { 1, 2, 3, 4, 5, 6, 7 }; foreach (int number in numbers.TakeRandom(rnd, 3)) { Console.WriteLine(number); } } } 

Outra implementação, mais elaborada, que gera permutações de k , que eu tive por aí e acredito que seja, de certa forma, uma melhoria em relação aos algoritmos existentes, se você precisar apenas iterar sobre os resultados. Embora também precise gerar x números randoms, ele usa apenas a memory O (min (y / 2, x)) no processo:

  ///  /// Generates unique random numbers ///  /// Worst case memory usage is O(min((emax-imin)/2, num)) ///  ///  /// Random source /// Inclusive lower bound /// Exclusive upper bound /// Number of integers to generate /// Sequence of unique random numbers public static IEnumerable UniqueRandoms( Random random, int imin, int emax, int num) { int dictsize = num; long half = (emax - (long)imin + 1) / 2; if (half < dictsize) dictsize = (int)half; Dictionary trans = new Dictionary(dictsize); for (int i = 0; i < num; i++) { int current = imin + i; int r = random.Next(current, emax); int right; if (!trans.TryGetValue(r, out right)) { right = r; } int left; if (trans.TryGetValue(current, out left)) { trans.Remove(current); } else { left = current; } if (r > current) { trans[r] = left; } yield return right; } } 

A idéia geral é fazer um shuffle de Fisher-Yates e memorizar as transposições na permutação . Não foi publicado em qualquer lugar nem recebeu qualquer revisão por pares. Eu acredito que é uma curiosidade em vez de ter algum valor prático. No entanto, estou muito aberto a críticas e geralmente gostaria de saber se você encontrar algo de errado com isso – por favor, considere isso (e adicionar um comentário antes de downvoting).

Uma pequena sugestão: se x >> y / 2, provavelmente é melhor selecionar aleatoriamente elementos y – x, então escolha o conjunto complementar.

Se, por exemplo, você tem 2 ^ 64 valores distintos, você pode usar um algoritmo de chave simétrica (com um bloco de 64 bits) para reorganizar rapidamente todas as combinações. (por exemplo Blowfish).

 for(i=0; i 

Isso não é random no sentido puro, mas pode ser útil para o seu propósito. Se você quiser trabalhar com um número arbitrário de valores distintos seguindo técnicas criptográficas, é possível, mas é mais complexo.

O truque é usar uma variação de shuffle ou, em outras palavras, um shuffle parcial.

 function random_pick( a, n ) { N = len(a); n = min(n, N); picked = array_fill(0, n, 0); backup = array_fill(0, n, 0); // partially shuffle the array, and generate unbiased selection simultaneously // this is a variation on fisher-yates-knuth shuffle for (i=0; i=0; i--) // O(n) times { selected = backup[ i ]; value = a[ N ]; a[ N ] = a[ selected ]; a[ selected ] = value; N++; } return picked; } 

OBSERVE que o algoritmo é estritamente O(n) no tempo e no espaço , produz seleções imparciais (é um embaralhamento imparcial parcial ) e não destrutivo no array de input (como seria um shuffle parcial), mas isso é opcional

adaptado daqui

atualizar

outra abordagem que utiliza apenas uma única chamada a PRNG (gerador de números pseudo-randoms) em [0,1] por IVAN STOJMENOVIC, “SOBRE GERAÇÃO PARALELA ADAPTATIVA E ALEATÓRIA DE OBJECTOS COMBINATÓRIOS” (secção 3 ), de O(N) (piores caso) complexidade

insira a descrição da imagem aqui

Aqui está uma maneira simples de fazer isso, que só é ineficiente se Y for muito maior que X

 void randomly_select_subset( int X, int Y, const int * inputs, int X, int * outputs ) { int i, r; for( i = 0; i < X; ++i ) outputs[i] = inputs[i]; for( i = X; i < Y; ++i ) { r = rand_inclusive( 0, i+1 ); if( r < i ) outputs[r] = inputs[i]; } } 

Basicamente, copie o primeiro X de seus valores distintos para sua matriz de saída e, em seguida, para cada valor restante, decida aleatoriamente include ou não esse valor.

O número random também é usado para escolher um elemento de nossa matriz de saída (mutável) a ser substituída.