Fórum de Matemática | DÚVIDAS? Nós respondemos! https://forumdematematica.org/ |
|
É possível identificar a posição de uma combinação em uma análise combinatória? https://forumdematematica.org/viewtopic.php?f=19&t=12359 |
Página 1 de 1 |
Autor: | Glaudiston [ 21 fev 2017, 13:25 ] |
Título da Pergunta: | É possível identificar a posição de uma combinação em uma análise combinatória? |
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 5o 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 2 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. |
Autor: | Glaudiston [ 21 fev 2017, 13:27 ] |
Título da Pergunta: | Re: É possível identificar a posição de uma combinação em uma análise combinatória? |
Desculpem... postei e encontrei alguns erros... como não consigo editar, vou postar novamente... corrigindo... 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. |
Autor: | 3,14159265 [ 21 fev 2017, 13:53 ] |
Título da Pergunta: | Re: É possível identificar a posição de uma combinação em uma análise combinatória? |
No seu exemplo é só fazer as combinações com "a" e o bc já seria o próximo. Teria uma questão pra facilitar? |
Autor: | Glaudiston [ 21 fev 2017, 13:57 ] |
Título da Pergunta: | Re: É possível identificar a posição de uma combinação em uma análise combinatória? |
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? O meu exemplo é apenas ilustrativo, o contexto que quero aplicar existirá milhões de "elementos origem", combinados em 2 elementos, e o custo de fazer as combinações seria impraticável. Preciso de uma fórmula para identificar com precisão a posição da combinação gerada. Isto é para aplicação em software que processa grafos. |
Autor: | pedrodaniel10 [ 21 fev 2017, 20:59 ] |
Título da Pergunta: | Re: É possível identificar a posição de uma combinação em uma análise combinatória? [resolvida] |
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. 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... 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)\) |
Autor: | Glaudiston [ 22 fev 2017, 02:24 ] |
Título da Pergunta: | Re: É possível identificar a posição de uma combinação em uma análise combinatória? |
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. |
Autor: | pedrodaniel10 [ 22 fev 2017, 03:15 ] |
Título da Pergunta: | Re: É possível identificar a posição de uma combinação em uma análise combinatória? |
As combinações podem ser todas obtidas do triângulo de Pascal e com isso tem algumas propriedades inerentes. Por notação: \(k^{\underline{n}}=\underbrace{k(k-1)(k-2)...(k-[n-1])}\\ \mathrm{\; \; \; \; \; \; \;\; \;\; \;\;\;\;\; \; n \: fatores}\) Assim temos que: \(\binom{n}{s}=\frac{n^{\underline{s}}}{s!}\) Pelo que é fácil obter o seguinte ou o anterior. \(\binom{n}{s+1}=\binom{n}{s}\cdot \frac{n-s}{s+1}\) Por exemplo para obter o 4 do 3 basta multiplicar o 3 por \(\frac{n-3}{4}\) que foi exatamente o que fez para obter o v3. Código: #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; } Que tem como output: Código: 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 Por exemplo para obter o 5 do 2 também é possivel. \(\binom{n}{2}=\frac{n(n-1)}{2} \binom{n}{5}=\frac{n^{\underline{5}}}{5!}=\frac{n(n-1)(n-2)(n-3)(n-4)}{120}=\frac{n(n-1)}{2}\cdot \frac{(n-2)(n-3)(n-4)}{3\times 4\times 5}=\binom{n}{2}\cdot \frac{(n-2)(n-3)(n-4)}{60}\) Para encontrar em que posição se encontra seja 2 a 2, 3 a 3 etc.. sempre existe uma fórmula fechada. Apenas é feita à base da composição. Como por exemplo para as combinações 3 a 3 com h<i<j: \(f(h,i,j)=\left ( \sum_{k=n-h+1}^{n-1}\frac{k^{\underline{2}}}{2} \right )+\left (\sum_{k=n-i+1}^{n-h-1}k \right )+j-i\) |
Página 1 de 1 | Os Horários são TMG [ DST ] |
Powered by phpBB® Forum Software © phpBB Group https://www.phpbb.com/ |