Combinações

Suponha-se que se pretende escrever ordenadamente todas as combinações de p elementos num conjunto de n elementos. Está definida uma ordem no conjunto de n elementos N’. Uma vez que se trata de um conjunto finito, existe uma bijecção de N’ para o conjunto N={1,2,…,n-1,n}. Se I[n,p] corresponder ao conjunto de todas as combinações de p elementos em N, pode-se definir uma ordenação natural em I[n,p], dada pela ordenação lexicográfica. Desta forma, os elementos de I[n,p] ficam convenientemente indexados.

Pretende-se elaborar um algoritmo que, dado um determinado valor inteiro, determine a combinação de I[n,p] com essa ordem. Para o efeito, analisam-se alguns exemplos para tentar determinar a existência de um padrão. Considere-se a combinação de 3 elementos num conjunto de 5:

blackcombinacoes

Na figura já está assinalado o padrão. Se C(n,p) representa o número de combinações de p elementos num conjunto de n, no total existem C(5,3) para este caso. A quantidade de uns na primeira coluna é C(4,2) que corresponde às combinações dos restantes elementos das colunas seguintes (existem duas posições para colocar um total de quatro elementos, pois o 1 já foi utilizado). Este padrão é recursivo nas colunas. O pseudocódigo que se segue permite dar uma ideia de um possível algoritmo:

input n
input p<=n
input 1<=index<=C(n,p)
dimension result with p elements
foreach k in result ordered index list do
begin
    n <- n-1
    p <- p-1
    j <- n
    temp <- 0
    while sum(C(i,p),i=n dowto j)<=index and j>=p do
    begin
        increment temp
        increment j
    end
    index <- index-sum(C(i,p),i=n downto j-1)
    n <- j-1
    result[k] <- k+temp-1
end
return result

O pseudocódigo apresentado carece de elegância de apresentação. O pormenor a ter em conta na respectiva análise consiste no facto das combinações estarem a ser construídas com base na adição de um determinado valor à posição no vector de resultados. De seguida, apresenta-se o algoritmo escrito em maple que implementa um procedimento direccionado para o problema supracitado.

iInt2Comb:=proc(ind::nonnegint,numTot::nonnegint,numComb::nonnegint) local i,temp,cont,n,p,res,r,q:
if ind<=0 then ERROR(`Invalid index`):fi:
if numComb=0 then ERROR(`Empty list to apply`):fi:
temp:=numbcomb(numTot,numComb):
if ind>temp then ERROR(`Index out of range`):fi:
if numComb=1 then RETURN([ind]):fi:
res:=[0$numComb]:
n:=numTot:p:=numComb-1:temp:=-1:r:=ind:q:=r:
for cont from 1 to numComb-1 do
while q>0 do
n:=n-1:
#if p<0 then p:=n+p: fi:
q:=q-numbcomb(n,p):
temp:=temp+1:
od:
r:=q+numbcomb(n,p):q:=r: #print(cat(`r=`,r)):
res[cont]:=cont+temp:    #print(res):
temp:=temp-1:
p:=p-1:
od:
res[numComb]:=res[numComb-1]+r:
RETURN(res):
end:

Apesar de ter apresentado a título de curiosidade, uma possível aplicação do algoritmo está relacionada com a representação de grupos de transformações de coordenadas a polinómios de várias variáveis, módulo algum ideal de codimensão finita. Uma vez que existe uma relação íntima entre combinações e monómios homogénios, é possível atribuir um índice a cada monómio, o qual permite construir a respectiva representação matricial.

Para perceber a relação entre combinações e monómios homogénios, observe-se que, por exemplo, todos os monómios de grau 4 nas variáveis x e y podem ser identificados com todas as combinações de 4 elementos tiradas do conjunto {x,x,x,x,y,y,y,y} onde a combinação [x,x,y,y] corresponde ao monómio xy2.

Sobre Sérgio O. Marques

Licenciado em Física/Matemática Aplicada (Astronomia) pela Faculdade de Ciências da Universidade do Porto e Mestre em Matemática Aplicada pela mesma instituição, desenvolvo trabalho no PTC (Porto Technical Centre) - Yazaki como Administrador de bases-de-dados. Dentro o meu leque de interesses encontram-se todos os temas afins às disciplinas de Matemática, Física e Astronomia. Porém, como entusiasta, interesso-me por temas relacionados com electrónica, poesia, música e fotografia.
Esta entrada foi publicada em Computadores e Internet. ligação permanente.

Deixe uma Resposta

Preencha os seus detalhes abaixo ou clique num ícone para iniciar sessão:

Logótipo da WordPress.com

Está a comentar usando a sua conta WordPress.com Terminar Sessão / Alterar )

Imagem do Twitter

Está a comentar usando a sua conta Twitter Terminar Sessão / Alterar )

Facebook photo

Está a comentar usando a sua conta Facebook Terminar Sessão / Alterar )

Google+ photo

Está a comentar usando a sua conta Google+ Terminar Sessão / Alterar )

Connecting to %s