Este post é uma reedição de um post meu no euromilhoes.com.

Em primeiro lugar, o que é o CSN? O CSN é o Número Sequencial Combinatório (Combinatorial Sequence Number) de uma dada combinação, quando estas se encontram ordenadas lexicograficamente, isto é, tendo como exemplo C(50,5), da [1, 2, 3, 4, 5] até à [46, 47, 48, 49, 50]. Neste caso, os CSN’s seriam o 1 e o 2.118.760.

Uma forma de calcular os CSN’s, e vice-versa, seria simplesmente construir todo o desdobramento até ao CSN pretendido, ou até à chave pretendida. Don’t. É estúpido, é um desperdício de ciclos de processamento e é péssima programação. Sobretudo, se já alguém pensou no assunto e se os algoritmos são do domínio público. Mesmo que não saibam, pesquisem antes de cometer uma barbaridade deste tamanho.

Vamos então aos ditos…

O algoritmo para calcular a combinação a partir do CSN é uma engenhosa obra prima de B. P. Buckles e M. Lyabanon, publicada em 1974.

função csnParaCombinação(csn, n, k)
    seja limite_inferior = 0;
    seja r = 0;
    seja combinação = [0...k-1]
 
    para cada i, sendo i = 0, enquanto i < k - 1, incrementar i
        combinação[i] = 0;
        se(i != 0) combinação[i] = combinação[i - 1];

        fazer
            combinação[i] =  combinação[i] + 1;
            r = númeroDeCombinações(n - combinação[i], (k - 1) - i); // lembram-se desta função?
            limite_inferior = limite_inferior + r;
        enquanto (limite_inferior < csn);
 
        limite_inferior = limite_inferior - r;
    fim de para;
 
    combinação[k - 1] = combinação[k - 2] + csn - limite_inferior;
 
    devolve combinação;
fim de função;

Para começar, quero-vos dizer que parece bem mais complicado do que na realidade é. Os comentários na minha implementação em C# poderão ajudar-vos a perceber melhor.

Depois, reparem como a última posição da combinação é tratada à parte, duma maneira perfeitamente elegante, usando os valores do CSN pedido e do último limite inferior calculado.

Mas passemos, então, à manobra inversa, calcular o CSN a partir da combinação. O seguinte algoritmo não tem, que eu saiba, autores oficiais. A sua simplicidade decorre de ser um negativo quase perfeito da função anterior.

função combinaçãoParaCsn(combinação, n)
    seja k = combinação.tamanho();
    seja limite_inferior = 0;
    seja r= 0;
 
    para cada i, sendo i = 1, enquanto i <= k, incrementar i
        r = n - combinação[k - i];
        se (r >= i)
            limite_inferior = limite_inferior + númeroDeCombinações(r, i);
        fim de se;
    fim de para;
 
    devolve númeroDeCombinações(n, k) - limite_inferior;
fim de função;

Podem ver, na segunda instrução do para, que a combinação está a ser percorrida de trás para a frente, e o limite inferior está a ser contado como o que falta até ao fim, sendo finalmente subtraído ao número de combinações total para nos dar o CSN.

O código fonte das minhas implementações em C# fazem parte da classe CombTools, disponível no projecto Combinatorica.

Olá, Helder.

Leia esta posta sobre como calcular o número de combinações. Vai reparar que a sua forma de calcular é pouco prática, e rebenta bastante cedo, visto que a função factorial(n) vai rebentar com n > 12.

Oi Aurélio,

Eu também estou convertendo a biblioteca para Delphi... vi seu comentário, e acabei implementando a função numeroDeCombinacoes desta maneira:

function numeroDeCombinacoes (n, k : integer) : double;
begin
    if n < k then
    begin
        result := 0.0;
    end
    else
    begin
        result := fatorial(n) / (fatorial(k) * fatorial (n-k));
    end;
end;

function fatorial (n: integer):integer;
var i: integer;
begin
    Result := 1;
    for i := 2 to n do
        Result := Result * i;
end;

Boa noite campeão

  Graças a Deus e a vc eu terminei os algoritimos do CSN em delphi que vc postou aqui como exemplo, o minimo que eu posso lhe contribuir e enviando oas fontes em delphi para vc, é só vc mandar seu e-mail para aurelioleonel@gmail.com que com prazer eu te enviarei, para vc testar, tem limitações pois algumas variavéis eu defeni com inteiro, e se vc colocar  100, 20 vai dar erro, mais isso é corrigivel pois para mim só interassa de 25,15 pois jogo na lotofácil ok!!! fico no aguardo e tenha uma boa sorte

Marcos Aurélio

!= é diferente. Em Delphi acho que é <>.

Ola Campeão

   Mais uma vez obrigado, a respeito do Begin..End da linha 11 do algorito que eu fiz, tambem achei que faltava, mais eu fiz masi de 15 testes, comparando com outro programa que eu tenho e os valores foram iguais.

  Quando eu chegar em casa vou analizar o que vc me postou e retornarei assim que fizer os testes OK!

A proposito o que siguinifica o ponto de exclamação neste item (i != 0)

Desde já agradeço

Marcos Aurélio

Estive a rever e a formatar o código que colocou e acho que falta ali um begin e um end no if da linha 11...

Tem estado a bater certo? Faça vários testes com resultados conhecidos; se essa função ficar engatada, daqui para a frente só vai piorar...

Começando pelo fim, ponto 3: e se fizer var combinacao: Array of Integer; e logo a seguir SetLength(combinacao, k - 1);? É que se puser lá um número inteiro directamente, perde a flexibilidade da função.

Ponto 1. Sim, cada item do array é inicializado a zero. Há linguagens que não precisam disto, mas o Delphi acho que sim.

Ponto 2.1. O então é logo a seguir. Como as linguagens em que costumo trabalhar não têm then, costumo esquecer-me. Deverá ler-se se(i != 0) então combinação[i] = combinação[i - 1];

Ponto 2.2. O fazer ... enquanto é uma estrutura repeat ... until

Campeão Bom Dia

  Otem consegui fazer a funcão

numeroDeCombinacoes(n, k : Integer) ficou perfeita

veja o algoritimo

Function numeroDeCombinacoes(n, k : Integer) : Variant;
Var Dif,  i : Integer;
Combinacoes : Double;
Begin
	If n < k Then Abort; // o valor de n não pode ser menor que k, com este comando nada e  executado  

	// Iniciando
	I := 0;
	Dif := n - k ;

	If k < Dif  Then
		Dif := k;
		k := n - Dif;

	Combinacoes := k +  1;

	If Dif = 0 Then
		Combinacoes := 1
	Else If  Dif >= 2 Then
		For i := 2 To dif Do //enquanto i não chegar ao valor de dif
			combinacoes := (combinacoes * (k + i)) / i;

	Result := Combinacoes;  // devolve a quantidade de combinações de n,k
	//exemplo  numeroDeCombinacoes(10, 5) é igual a 252 combinações
End;

Só estou apanhando na funcao

CsnParaCombinacao(csn, n, k)

Vamos la as duvidas

1-

para cada i, sendo i = 0, enquanto i < k - 1, incrementar i      combinação[i] = 0;

não estou entendendo este laço

todo array tem que receber zero primeiro?

2-

se(i != 0) combinação[i] = combinação[i - 1];       fazer         combinação[i] =  combinação[i] + 1;

não estou vendo o então: e esse "fazer" é o que?

3-

combinacao[0..k-1] o delphi não aceita, pode ser um numero fixo assim combinacao[0..24]

Desde ja agradeço

Marcos aurélio

Campeão boa Noite

    Mais uma vez muito obrigado agora ja dar para entender o algoritimo, mais ainda vai sugir duvidas e eu vou aos seus pés lhe perguntas, assim que estiver pronto, eu postare pedidoo seu e-mailpra viaros fontes do projeto, e ele completo ok uma abraço

Marcos Aurélio

Boas noites, Aurelio.

Essa função, numeroDeCombinações, está aqui explicada (é a última). Sim, é preciso implementar também.

A função tamanho() devolve o tamanho do array. Em Delphi, há-de ser qualquer coisa do estilo k = Length(oMeuArray).

Sim, as CSN são isso mesmo; por exemplo, para combinações de 8, 5 a 5, o CSN 1 é 1-2-3-4-5, o CSN 2 é 1-2-3-4-6, o CSN 3 é 1-2-3-4-7, e por aí fora até ao CSN 56, que é 4-5-6-7-8.