Número sequencial combinatório: diferenças entre revisões
Linha 20: | Linha 20: | ||
Demonstra-se abaixo uma fórmula genérica para cálculo do código CSN a partir de um dado vetor de elementos ''a'' previamente classificados em ordem crescente. |
Demonstra-se abaixo uma fórmula genérica para cálculo do código CSN a partir de um dado vetor de elementos ''a'' previamente classificados em ordem crescente. |
||
<math>csn = {n \choose r} - {\sum_{i=1,k=(n-a_{r-i+1})}^r {\{ \begin{matrix} {0}, & \mbox{se }k < i \\ {k \choose i}, & \mbox{se }k>=i \end{matrix} }}</math> |
<math>csn = {n \choose r} - {\sum_{i=1,k=(n-a_{r-i+1})}^r {\left \{ \begin{matrix} {0}, & \mbox{se }k < i \\ {k \choose i}, & \mbox{se }k>=i \end{matrix} \right . }}</math> |
||
Ou, alternativamente: |
Ou, alternativamente: |
||
<math>csn = {n! \over (r!(n-r)!)} - {\sum_{i=1,k=(n-a_{r-i+1})}^r {\{ \begin{matrix} {0}, & \mbox{se }k < i \\ {k! \over (i!(k-i)!)}, & \mbox{se }k>=i \end{matrix} |
<math>csn = {n! \over (r!(n-r)!)} - {\sum_{i=1,k=(n-a_{r-i+1})}^r {\left \{ \begin{matrix} {0}, & \mbox{se }k < i \\ {k! \over (i!(k-i)!)}, & \mbox{se }k>=i \end{matrix} \right . |
||
}}</math> |
}}</math> |
||
Revisão das 04h00min de 1 de julho de 2006
Na matemática, o número sequencial combinatório (CSN) de uma dada combinação refere-se a posição desta no universo de combinações possíveis de um subconjunto de tamanho r em um conjunto n estabelecido.
Assim, por exemplo, em um jogo de 49/6 combinações (n/r), a combinação 6-7-16-20-28-47 equivale ao índice 6991908 (exatamente o ponto central do número total de combinações). A mesma combinação tem o índice 45148858 em um jogo de 69/6 combinações.
Histórico
Históricamente a matemática sempre teve grande interesse em "combinações". As loterias e demais jogos de azar baseiam-se fortemente em análise combinatorial e probabilidade em seu funcionamento.
Nesse contexto, existem dois problemas recorrentes quando se trata desse ramo da matemática:
- Determinar o índice (ou posição lexicográfica ou ainda número sequencial combinatório) de uma dada combinação;
- Construir uma combinação dado um determinado índice CSN.
A primeira tentativa de solucionar esses problemas foi feita em 1974. Nesse ano, B.P. Buckles & M. Lybanon criaram um programa de computador que construía combinações simples dado um índice conhecido (algoritmo ACM #515). Depois disso, diversos outros algoritmos[1][2] surgiram com maior ou menor grau de complexidade, para atender outras classes de combinações.
Conversão notação combinatorial para CSN
Demonstra-se abaixo uma fórmula genérica para cálculo do código CSN a partir de um dado vetor de elementos a previamente classificados em ordem crescente.
Ou, alternativamente:
Onde:
n = número de elementos a serem combinados r = números por combinação a = vetor com a combinação desejada (a[1]=primeiro elemento)
Em notação computacional pode-se usar o seguinte algorítmo para realizar a conversão da notação combinatorial para o código CSN:
x = 0 Para i de 1 até r faça k = n - a[r-i+1] Se k >= i Então x = x + k!/(i!(k-i)!) // ou: x = x + combinação(k, i) Fim Se Fim Para CSN = (n!/(r!(n-r)!)) - x // ou: CSN = combinação(n, r) - x
Conversão notação CSN para combinatorial
Demonstra-se abaixo uma fórmula genérica para obtenção da combinação dado um código CSN qualquer.
Segue-se abaixo, em notação computacional, o algorítmo equivalente.
n = número de elementos a serem combinados r = números por combinação a = vetor para receber a combinação (a[1]=primeiro elemento) csn = código CSN de entrada
csn = combinação(n, r) - csn k = n + 1 Para i de r até 1 faça Repita k = k - 1 Se k >= i Então x = combinação(k, i) Senão x = 0 Fim Se Até x <= csn csn = csn - x a[r-i+1] = n - k Fim Para Se csn >= 0 Então a[r] = a[r] - csn Fim Se
Ver também
Referências
- Phillip J. Chase, Algorithm 382: combinations of M out of N objects [G6], Communications of the ACM, v.13 n.6, p.368, June 1970
- LEHMER, D.H. The machine tools of combinatorics. In Applied Combinatorial Mathematics, E.F. Beckenbach, Ed., Wiley, New York, 1964, pp. 5-30.
- C. N. Liu , D. T. Tang, Algorithm 452: enumerating combinations of m out of n objects [G6], Communications of the ACM, v.16 n.8, p.485, Aug. 1973
- Charles J. Mifsud, Algorithm 154: combination in lexicographical order, Communications of the ACM, v.6 n.3, p.103, March 1963
- NIJENHUIS, A., AND WILF, H.S. Combinatorial Algorithms. Academic Press, New York, 1975.
- PHILLIPS, J.P.N. Permutations of the elements of a vector in lexicographic order. Comput. J. 10, 4 (Oct. 1967), 311.
- Henry F. Walter, Algorithm 151: location of a vector in a lexicographically ordered list, Communications of the ACM, v.6 n.2, p.68, Feb. 1963
- M. L. Wolfson , H. V. Wright, Algorithm 160: combinatorial of M things taken N at a time, Communications of the ACM, v.6 n.4, p.161, April 1963