pedrodaniel10 Escreveu:
Pode ser mais especifico ao que pretende obter e como está a fazer na prática com algum pormenor? O que está a desenvolver e como está a desenvolver ? Só por curiosidade.
Bem... é complicado, mas vou tentar...
Muito tempo atrás fiz um algorítimo em C de alta performance para armazenamento e localização de registros, com ordenação implicita.
Existia uma barreira sobre o espaço utilizado para armazenamento, que inviabilizaria a utilização para fins práticos em muitos cenários. Recentemente revisando o conceito de grafos tive uma ideia sobre como resolver o problema de espaço adicionando a flexibilidade dos grafos, mas preciso converter algumas estruturas para o conceito.
Hoje após o post que fiz aqui, pesquisei mais e encontrei que consigo gerar o mesmo resultado da análise combinatória com a soma dos termos de uma progressão aritmética para combinações únicas de 2 e 3 fatores.
Ou seja.
Código:
1 #include <stdio.h>
2
3 long long fatorial(int n)
4 {
5 return ( n == 0 || n == 1 ) ? 1 : n * fatorial(n-1) ;
6 }
7
8 int main(int argc, char ** argv)
9 {
10 int fatores=2;
11 int itens_combinacao = 2;
12 for ( ; fatores < 20; fatores++ ){
13 int v = fatorial(fatores) / ( fatorial(itens_combinacao) * f atorial( fatores - itens_combinacao ));
14 printf("C(%i,%i) = %i \n", fatores, itens_combinacao, v);
15 }
16 return 0;
17 }
Utiliza o conceito de análise combinatória, \(\binom{n}{2}\binom\) e gerando:
Código:
C(2,2) = 1
C(3,2) = 3
C(4,2) = 6
C(5,2) = 10
C(6,2) = 15
C(7,2) = 21
C(8,2) = 28
C(9,2) = 36
C(10,2) = 45
C(11,2) = 55
C(12,2) = 66
C(13,2) = 78
C(14,2) = 91
C(15,2) = 105
C(16,2) = 120
C(17,2) = 136
C(18,2) = 153
C(19,2) = 171
Código:
C(3,3) = 1
C(4,3) = 4
C(5,3) = 10
C(6,3) = 20
C(7,3) = 35
C(8,3) = 56
C(9,3) = 84
C(10,3) = 120
C(11,3) = 165
C(12,3) = 220
C(13,3) = 286
C(14,3) = 364
C(15,3) = 455
C(16,3) = 560
C(17,3) = 680
C(18,3) = 816
C(19,3) = 969
é o mesmo que fazer: \(S_(_n_) = \frac{ n . ( a_n + a_1 ) }{2}\)
Código:
1 #include <stdio.h>
2
3 int main(int argc, char ** argv)
4 {
5 int fatores = 2;
6 int itens_combinacao = 3;
7 for ( ; fatores <= 21; fatores++ )
8 {
9 // base 2
10 int v2 = ( (fatores * (fatores -1)) / 2 );
11 // base 3
12 int v3 = v2 * ( fatores - itens_combinacao + 1) / itens_combinacao;
13 // TODO: como calcular a base 4 ?
14 printf("S(%i) = %i\tS(%i) = %i\n", fatores, v2, fatores, v3 );
15 }
16 return 0;
17 }
18
Código:
S(2) = 1 S(2) = 0
S(3) = 3 S(3) = 1
S(4) = 6 S(4) = 4
S(5) = 10 S(5) = 10
S(6) = 15 S(6) = 20
S(7) = 21 S(7) = 35
S(8) = 28 S(8) = 56
S(9) = 36 S(9) = 84
S(10) = 45 S(10) = 120
S(11) = 55 S(11) = 165
S(12) = 66 S(12) = 220
S(13) = 78 S(13) = 286
S(14) = 91 S(14) = 364
S(15) = 105 S(15) = 455
S(16) = 120 S(16) = 560
S(17) = 136 S(17) = 680
S(18) = 153 S(18) = 816
S(19) = 171 S(19) = 969
S(20) = 190 S(20) = 1140
S(21) = 210 S(21) = 1330
Porém com um custo muito inferior ao da fatoração.
pedrodaniel10 Escreveu:
Como é apenas combinações 2 a 2. Segue sempre um padrão. O 1º elemento conjuga com os outros n-1 elementos. O segundo elemento com n-2 elementos etc...
Na verdade o problema 2 a 2 é apenas o primeiro passo da minha necessidade. O ideal seria conseguir calcular a Progreção Aritimetica para a análise combinatória distinta de qualquer número de fatores, mas estou com dificuldades de entender como fazê-lo a partir de 4 fatores combinatórios.
pedrodaniel10 Escreveu:
Se tivermos o conjunto \(\{u_1,u_2,u_3,...,u_n\}\)
Para n elementos, existem \(\binom{n}{2}=\binom{n-1}{1}+\binom{n-2}{1}+...+\binom{1}{1}+\binom{0}{1}=(n-1)+(n-2)+...+1+0=\sum_{k=0}^{n-1}k=\frac{n(n-1)}{2}\) combinações que, para as encontrar todas cresce com \(O(n^2)\) que é computacionalmente comportável.
\(A=\{u_1,u_2,u_3,...,u_n\}
B= \{u_1u_2,u_1u_2,...,u_{n-1}u_n\}\)
As combinações são sempre assim:
\(\left.\begin{matrix} u_1u_2\\ u_1u_3\\ ...\\ u_1u_n \end{matrix}\right\} \:n-1 \: \mathrm{termos}
\left.\begin{matrix} u_2u_3\\ u_2u_4\\ ...\\ u_2u_n \end{matrix}\right\} \:n-2 \: \mathrm{termos}
...
\left.\begin{matrix} u_{n-1u_n} \end{matrix}\right\}\:1\: \mathrm{termo}\)
Para encontrar o cardinal da combinação \(u_iu_j\) em B. Sendo que i<j e n o numero de elementos de A.
\(f(i,j)=\left (\sum_{k=n-i+1}^{n-1}k \right )+j-i~=\left [ \frac{k(k-1)}{2} \right ]_{n-i+1}^{n}+j-i= \frac{n(n-1)}{2}-\frac{(n-i+1)(n-i)}{2}+j-i=\frac{n(n-1)-(n-i+1)(n-i)}{2}+j-i=\frac{(i - 1) (2 n - i)}{2}+j-i\)
Desta feita fica com crescimento de \(O(1)\)
pedrodaniel10 Escreveu:
\(\frac{(i - 1) (2 n - i)}{2}+j-i\)
Genial. Acho que isto deve resolver por hora, vou voltar ao código e tentar adaptar isto a minha necessidade.