Número sequencial combinatório: diferenças entre revisões
remoção de informação sem fontes que foi contestada. |
|||
Linha 43: | Linha 43: | ||
CSN = (n!/(r!(n-r)!)) - x |
CSN = (n!/(r!(n-r)!)) - x |
||
// ou: CSN = combinação(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. |
|||
<math> |
|||
Q(x) = \left ( |
|||
\left |
|||
\{ \begin{matrix} {1}, & \mbox{se }x \le 0 \\ |
|||
{\prod_{k=1}^{n} { |
|||
\left ( |
|||
\left |
|||
\{ \begin{matrix} |
|||
{(k+1) \over k} |
|||
, & \mbox{se }{k \choose {r - x + 1}} \le |
|||
({n \choose r} - csn - |
|||
\left ( |
|||
\left |
|||
\{ \begin{matrix} {0}, & \mbox{se }x \le 1 \\ |
|||
{ |
|||
\sum_{i=1}^{x-1} |
|||
{ |
|||
{Q(x - 1) \choose (r - i + 1)} |
|||
} |
|||
}, & \mbox{se }x > 1 |
|||
\end{matrix} |
|||
\right ) |
|||
\right . |
|||
) |
|||
\\ |
|||
{1}, & \mbox{se }falso |
|||
\end{matrix} |
|||
\right ) |
|||
\right . |
|||
}} , & \mbox{se }x > 0 |
|||
\end{matrix} |
|||
\right ) |
|||
\right . |
|||
{- 1} |
|||
</math> |
|||
<math> |
|||
A(x) = n - Q(x) |
|||
</math> |
|||
Segue-se abaixo, em notação computacional, o algoritmo 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 |
|||
Este algoritmo nao funciona. A pessoa que editou no wikipedia, ou nao testou este algotitmo, ou nao tem a minima ideia do que ta falando. |
|||
== {{Ver também}} == |
== {{Ver também}} == |
Revisão das 15h16min de 19 de outubro de 2013
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 combinático) 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 algoritmo 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] (edito para salientar que na codificaçao sera k=n-a(r-i) visto o array começar na posiçao zero) 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
Ver também
Referências gerais
- 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