Número sequencial combinatório: diferenças entre revisões
Linha 1: | Linha 1: | ||
⚫ | |||
⚫ | |||
⚫ | |||
==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. |
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. |
||
Linha 7: | Linha 15: | ||
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 [http://portal.acm.org/citation.cfm?id=355739&coll=portal&dl=ACM ACM #515]). Depois disso, diversos outros algoritmos[http://www.saliu.com/bbs/messages/348.htm][http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dv_vstechart/html/mth_lexicograp.asp ] surgiram com maior ou menor grau de complexidade, para atender outras classes de combinações. |
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 [http://portal.acm.org/citation.cfm?id=355739&coll=portal&dl=ACM ACM #515]). Depois disso, diversos outros algoritmos[http://www.saliu.com/bbs/messages/348.htm][http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dv_vstechart/html/mth_lexicograp.asp ] surgiram com maior ou menor grau de complexidade, para atender outras classes de combinações. |
||
==Definição== |
|||
⚫ | |||
⚫ | |||
⚫ | |||
==Conversão notação combinatorial para CSN== |
==Conversão notação combinatorial para CSN== |
Revisão das 18h06min de 30 de junho de 2006
Na matemática, o número sequencial combinatório 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 - CSN) 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 o algorítmo para obtenção da combinação dado um código CSN qualquer.
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