Fórum de Matemática
DÚVIDAS? Nós respondemos!

Um Fórum em Português dedicado à Matemática
Data/Hora: 28 mar 2024, 18:15

Os Horários são TMG [ DST ]




Fazer Nova Pergunta Responder a este Tópico  [ 7 mensagens ] 
Autor Mensagem
MensagemEnviado: 21 fev 2017, 13:25 
Offline

Registado: 21 fev 2017, 13:01
Mensagens: 4
Localização: Campinas
Agradeceu: 1 vez(es)
Foi agradecido: 0 vez(es)
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.


Topo
 Perfil  
 
MensagemEnviado: 21 fev 2017, 13:27 
Offline

Registado: 21 fev 2017, 13:01
Mensagens: 4
Localização: Campinas
Agradeceu: 1 vez(es)
Foi agradecido: 0 vez(es)
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.


Topo
 Perfil  
 
MensagemEnviado: 21 fev 2017, 13:53 
Offline

Registado: 21 mar 2016, 01:35
Mensagens: 94
Localização: Rio de Janeiro
Agradeceu: 2 vezes
Foi agradecido: 31 vezes
No seu exemplo é só fazer as combinações com "a" e o bc já seria o próximo. Teria uma questão pra facilitar?


Topo
 Perfil  
 
MensagemEnviado: 21 fev 2017, 13:57 
Offline

Registado: 21 fev 2017, 13:01
Mensagens: 4
Localização: Campinas
Agradeceu: 1 vez(es)
Foi agradecido: 0 vez(es)
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.


Topo
 Perfil  
 
MensagemEnviado: 21 fev 2017, 20:59 
Offline

Registado: 11 jan 2015, 02:31
Mensagens: 539
Localização: Covilhã
Agradeceu: 7 vezes
Foi agradecido: 298 vezes
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)\)


Topo
 Perfil  
 
MensagemEnviado: 22 fev 2017, 02:24 
Offline

Registado: 21 fev 2017, 13:01
Mensagens: 4
Localização: Campinas
Agradeceu: 1 vez(es)
Foi agradecido: 0 vez(es)
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.


Topo
 Perfil  
 
MensagemEnviado: 22 fev 2017, 03:15 
Offline

Registado: 11 jan 2015, 02:31
Mensagens: 539
Localização: Covilhã
Agradeceu: 7 vezes
Foi agradecido: 298 vezes
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\)


Topo
 Perfil  
 
Mostrar mensagens anteriores:  Ordenar por  
Fazer Nova Pergunta Responder a este Tópico  [ 7 mensagens ] 

Os Horários são TMG [ DST ]


Quem está ligado:

Utilizadores a ver este Fórum: Nenhum utilizador registado e 47 visitantes


Criar perguntas: Proibído
Responder a perguntas: Proibído
Editar Mensagens: Proibído
Apagar Mensagens: Proibído
Enviar anexos: Proibído

Pesquisar por:
Ir para: