Como você escrever este algoritmo para grandes combinações da forma mais compacta?

StackOverflow https://stackoverflow.com/questions/956542

Pergunta

O número de combinações de itens k que podem ser recuperados a partir de itens N é descrito pela seguinte fórmula. 

             N! 
c =  ___________________ 
       (k! * (N - k)!)

Um exemplo seria quantas combinações de 6 Balls pode ser desenhado a partir de um tambor de 48 Balls num sorteio.

Optimize esta fórmula para ser executado com o menor complexidade O tempo

Esta questão foi inspirado no novo motor WolframAlpha matemática eo fato de que ele pode calcular extremamente grandes combinações muito rapidamente. por exemplo. e uma discussão posterior sobre o tema em outro fórum.

http://www97.wolframalpha.com/input/?i = 20000000 + Escolha + 15000000

Vou postar algumas informações / links de que a discussão após algumas pessoas tomar uma facada em solução.

Qualquer língua é aceitável.

Foi útil?

Solução

Observe que WolframAlpha retorna um "Decimal aproximação". Se você não precisa de uma precisão absoluta, você poderia fazer a mesma coisa, calculando os fatoriais com de Stirling Aproximação .

Agora, aproximação de Stirling requer a avaliação de (n / e) ^ n, onde e é a base do logaritmo natural, que será, de longe, a operação mais lenta. Mas isso pode ser feito usando as técnicas descritas em outra stackoverflow pós .

Se você usar precisão dupla e repetiu quadratura para realizar a exponenciação, as operações serão:

  • 3 avaliações de uma aproximação de Stirling, cada ó exigindo (N log N) multiplicações e uma avaliação de raiz quadrada.
  • 2 multiplicações
  • 1 divisões

O número de operações provavelmente poderia ser reduzido com um pouco de inteligência, mas a complexidade tempo total vai ser O (log n) com esta abordagem. Muito manejável.

EDIT: Há também obrigado a ser um monte de literatura acadêmica sobre este tema, dado o quão comum este cálculo é. Uma biblioteca boa universidade poderia ajudá-lo a segui-lo para baixo.

EDIT2:. Além disso, como as pontas de outra resposta, os valores serão facilmente transbordar dupla, portanto, um tipo de ponto flutuante com precisão muito prolongado terá de ser utilizado para mesmo moderadamente grandes valores de k e n

Outras dicas

Python: O (min [ k , n - k ] 2 ) 

def choose(n,k):
    k = min(k,n-k)
    p = q = 1
    for i in xrange(k):
        p *= n - i
        q *= 1 + i
    return p/q

Análise:

  • O tamanho de p e q irá aumentar linearmente dentro do ciclo, se n-i e 1+i pode ser considerado como tendo tamanho constante.
  • O custo de cada multiplicação, então, também aumentam linearmente.
  • Esta soma de todas as iterações torna-se uma série aritmética sobre k.

A minha conclusão: O (k 2 )

Se reescrito para usar números de ponto flutuante, as multiplicações será operações atômicas, mas vamos perder muita precisão. Ele ainda transborda para choose(20000000, 15000000). (Não é uma grande surpresa, já que o resultado seria em torno de 0,2119620413 × 10 4.884.378 .) 

def choose(n,k):
    k = min(k,n-k)
    result = 1.0
    for i in xrange(k):
        result *= 1.0 * (n - i) / (1 + i)
    return result

Eu resolvê-lo em Mathematica : 

Binomial[n, k]

O homem, que era fácil ...

Python:? aproximação em O (1)

Usando implementação python decimal para calcular uma aproximação. Uma vez que não utilizar qualquer circuito externo, e os números são limitados em tamanho, eu acho que vai executar no O (1). 

from decimal import Decimal

ln = lambda z: z.ln()
exp = lambda z: z.exp()
sinh = lambda z: (exp(z) - exp(-z))/2
sqrt = lambda z: z.sqrt()

pi = Decimal('3.1415926535897932384626433832795')
e = Decimal('2.7182818284590452353602874713527')

# Stirling's approximation of the gamma-funciton.
# Simplification by Robert H. Windschitl.
# Source: http://en.wikipedia.org/wiki/Stirling%27s_approximation
gamma = lambda z: sqrt(2*pi/z) * (z/e*sqrt(z*sinh(1/z)+1/(810*z**6)))**z

def choose(n, k):
  n = Decimal(str(n))
  k = Decimal(str(k))
  return gamma(n+1)/gamma(k+1)/gamma(n-k+1)

Exemplo: 

>>> choose(20000000,15000000)
Decimal('2.087655025913799812289651991E+4884377')
>>> choose(130202807,65101404)
Decimal('1.867575060806365854276707374E+39194946')

Qualquer superior, e ele irá transbordar. O expoente parece estar limitada a 40 milhões.

Dado um número razoável de valores para n e K, calcula-los com antecedência e usar uma tabela de pesquisa.

É esquivando-se a questão de alguma forma (você está transferindo o cálculo), mas é uma técnica útil se você está tendo para determinar um grande número de valores.

MATLAB:

  • O caminho do trapaceiro (usando o built-in função de NCHOOSEK ):? 13 caracteres, O () 

    nchoosek(N,k)

  • Meu solução: 36 caracteres, O (min (k, N-k)) 

    a=min(k,N-k);
prod(N-a+1:N)/prod(1:a)

Eu sei que esta é uma pergunta muito antigo, mas eu lutei com uma solução para este problema por um longo tempo até que eu encontrei um muito simples escrito em VB 6 e depois de portá-la para C #, aqui está o resultado: 

public int NChooseK(int n, int k)
{
    var result = 1;
    for (var i = 1; i <= k; i++)
    {
        result *= n - (k - i);
        result /= i;
    }

    return result;
}

O código final é tão simples que você não vai acreditar que vai funcionar até que você executá-lo.

Além disso, o artigo original dá alguma boa explicação sobre como ele chegou ao algoritmo final .

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top