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.

Partilhar no Sapo Links Partilhar no del.icio.us Partilhar no Digg Partilhar no Twitter Partilhar no StumbleUpon Partilhar no MySpace Partilhar no Facebook

Comentários Comentários Imagem do Feed RSS

1 2

Alix

Bom dia Marco,

Entendi. Um dos volumes do Art of Computer Programming parece-me que tem todos estes algoritmos explicados, encontrei também o que acredito ser o equivalente ao CSN para permutações em http://en.wikipedia.org/wiki/Factorial_number_system vou tentar implementar isto hoje, quanto às repetições, tanto de combinações como permutações, é que ainda não encontrei nada... Se por acaso tropeçares nos outros algoritmos diz-me alguma coisa por favor. =)

Abraço

Marco

Olá alixaxel!

O pseudo-código de um algoritmo, normalmente, não tem estruturas de controle de erros, até porque linguagens diferentes têm soluções diferentes. No entanto, os dois casos referidos nem são tanto uma questão de controlo de erros, mas de controlo lógico (que poderá ser feito dentro ou fora da função, depende do resto da aplicação):

1) Para k = 1, a combinação correspondente ao csn é {csn} (os subsets contém apenas um elemento, logo, esse elemento é igual à posição em n). Logo, nem sequer se chamaria este algoritmo para calcular esse caso, é um desperdício de processamento;

2) As combinações têm que vir ordenadas, lógico. Ordená-las dentro do algoritmo é irrelevante, porque qualquer aplicação que use estes algoritmos terá, com toda a certeza, algoritmos de ordenação das combinações, que dependem da estrutura de dados usada para guardar as combinações.

Já não tenho a certeza absoluta em relação a combinações com repetição, mas tenho para aqui algures algoritmos semelhantes para permutações. Não sei é bem onde... ;)

alixaxel

Olá Marco!

 

Desconhecia este algoritmo, é extremamente elegante... Muito obrigado por o divulgares e disponibilizares o código-fonte! Contudo, notei duas coisas no pseudo-código que podem correr mal em determinadas circunstâncias:

1) se k = 1 em csnParaCombinação(), combinação[k - 2] não irá existir

2) se a combinação não for ordenada em combinaçãoParaCsn(), é devolvido um CSN errado

 

Seguindo esta última linha de pensamento, queria-te perguntar se tens conhecimento de derivações do algoritmo para combinações com repetição de elementos [(n + k - 1)! / (k! * (n - 1)!)], permutações [n! / (k! * (n - k)!)] e permutações com repetições de elementos [n^k]?

 

Abraço

Marco

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.

Helder

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;

 

aurelioleonel

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

Marco

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

aurelioleonel

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

Marco

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...

Marco

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

1 2

Comentários Deixar um comentário

 Categorias
 Arquivo
 Projectos em Destaque
 Últimas Postas no Blog
 Últimos Comentários do Blog