21 fev 2017, 13:25
21 fev 2017, 13:27
Glaudiston Escreveu:Pensemos em uma análise combinatória de 4 elementos em uma combinação sem repetição de 2 elementos:
{ a, b, c, d }
Aplicando a análise temos o resultado 6:
Entendendo que a combinação foi feita de maneira ordenada, temos
ab, ac, ad, bc, bd, cd
Conjunto de origem:
1o Elemento Origem = a
2o Elemento Origem = b
3o Elemento Origem = c
4o Elemento Origem = d
Combinação resultante:
1o Elemento = ab
2o Elemento = ac
3o Elemento = ad
4o Elemento = bc
6o Elemento = bd
6o Elemento = cd
Dado que temos as variáveis conjunto de origem, e quantidade de elementos:
Existe alguma format de identificar a posição de um elemento sem ter que correr todos os itens?
Reformulando:
É possível identificar a posição "bc" com o valor 4 sem verificar os outros elementos ?
PS: Este é meu primeiro post, então me desculpem se não estiver formatado na forma padrão do forum.
21 fev 2017, 13:53
21 fev 2017, 13:57
3,14159265 Escreveu:No seu exemplo é só fazer as combinações com "a" e o bc já seria o próximo. Teria uma questão pra facilitar?
21 fev 2017, 20:59
22 fev 2017, 02:24
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.
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 }
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(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
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
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
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...
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\)
22 fev 2017, 03:15
#include <stdio.h>
int main(){
int fatores = 2;
for ( ; fatores <= 21; fatores++ ){
// base 2
int v2 = ( (fatores * (fatores -1)) / 2 );
// base 3
int v3 = v2 * ( fatores - 2) / 3;
// base 4
int v4 = v3*(fatores - 3)/4;
printf("S(%i) = %i\tS(%i) = %i\tS(%i) = %i\n", fatores, v2, fatores, v3, fatores, v4);
}
return 0;
}
S(2) = 1 S(2) = 0 S(2) = 0
S(3) = 3 S(3) = 1 S(3) = 0
S(4) = 6 S(4) = 4 S(4) = 1
S(5) = 10 S(5) = 10 S(5) = 5
S(6) = 15 S(6) = 20 S(6) = 15
S(7) = 21 S(7) = 35 S(7) = 35
S(8) = 28 S(8) = 56 S(8) = 70
S(9) = 36 S(9) = 84 S(9) = 126
S(10) = 45 S(10) = 120 S(10) = 210
S(11) = 55 S(11) = 165 S(11) = 330
S(12) = 66 S(12) = 220 S(12) = 495
S(13) = 78 S(13) = 286 S(13) = 715
S(14) = 91 S(14) = 364 S(14) = 1001
S(15) = 105 S(15) = 455 S(15) = 1365
S(16) = 120 S(16) = 560 S(16) = 1820
S(17) = 136 S(17) = 680 S(17) = 2380
S(18) = 153 S(18) = 816 S(18) = 3060
S(19) = 171 S(19) = 969 S(19) = 3876
S(20) = 190 S(20) = 1140 S(20) = 4845
S(21) = 210 S(21) = 1330 S(21) = 5985