Combinações possíveis. Elementos de combinatória
Uma combinação é uma seleção não ordenada de elementos de um conjunto finito com número fixo e sem repetições de elementos. Diferentes combinações devem diferir em pelo menos um elemento, e a ordem dos elementos não importa. Por exemplo, do conjunto de todas as vogais das letras latinas (AEIOU), você pode fazer 10 combinações diferentes de 3 letras, formando os seguintes trigêmeos não ordenados:
AEI, AEO, AEU, AIO, AIU, AOU, EIO, EIU, EOU, IOU.
É interessante notar que das mesmas cinco letras você também pode obter 10 combinações diferentes se combiná-las 2 letras de cada vez, formando os seguintes pares não ordenados:
AE, AI, AO, AU, EI, EO, UE, IO, IU, OU.
No entanto, se você combinar as mesmas vogais latinas por 4, obterá apenas as seguintes 5 combinações diferentes:
AEIO, AEIU, AIOU, EIOU, AEOU.
Em geral, para denotar o número de combinações de n elementos diferentes de m elementos, é usado o seguinte simbolismo funcional, de índice ou vetorial (Appel):
Independentemente da forma de notação, o número de combinações de n elementos por m elementos pode ser determinado usando as seguintes fórmulas multiplicativas e fatoriais:
É fácil verificar que o resultado dos cálculos usando essas fórmulas coincide com os resultados do exemplo discutido acima com combinações de vogais em letras latinas. Em particular, com n=5 e m=3, os cálculos utilizando estas fórmulas darão o seguinte resultado:
No caso geral, as fórmulas para o número de combinações têm um significado combinatório e são válidas para quaisquer valores inteiros de n e m, tais que n > m > 0. Se m > n e m< 0, то число сочетаний равно 0, так как в этом случае основное множество из n элементов вообще не имеет подмножеств мощности m:
Além disso, é útil lembrar os seguintes números limites de combinações, que podem ser facilmente verificados por substituição direta nas fórmulas multiplicativa e fatorial:
Deve-se notar também que a fórmula multiplicativa permanece válida mesmo quando n é um número real, desde que m ainda seja um valor inteiro. Porém, então o resultado do cálculo que o utiliza, embora mantenha a validade formal, perde seu significado combinatório.
IDENTIDADES DE COMBINAÇÕES
O uso prático de fórmulas multiplicativas e fatoriais para determinar o número de combinações para valores arbitrários de n e m acaba sendo de pouca produtividade devido ao crescimento exponencial dos produtos fatoriais de seu numerador e denominador. Mesmo para valores relativamente pequenos de n e m, esses produtos geralmente excedem as capacidades de representação de números inteiros em sistemas modernos de computação e software. Além disso, seus valores acabam sendo significativamente maiores que o valor resultante do número de combinações, que pode ser relativamente pequeno. Por exemplo, o número de combinações de n=10 por m=8 elementos é de apenas 45. Porém, para encontrar esse valor usando a fórmula fatorial, você deve primeiro calcular valores muito maiores de 10! no numerador e 8! no denominador:
Para eliminar operações demoradas de processamento de grandes quantidades, para determinar o número de combinações, você pode usar várias relações de recorrência, que decorrem diretamente das fórmulas multiplicativas e fatoriais. Em particular, a seguinte relação de recorrência decorre da fórmula multiplicativa, o que nos permite levar a razão dos seus índices além do sinal do número de combinações:
Finalmente, manter o subscrito constante fornece a seguinte relação de recorrência, que é facilmente obtida a partir da fórmula fatorial para o número de combinações:
Após transformações elementares, as três relações de recorrência resultantes podem ser representadas nas seguintes formas:
Se agora somarmos os lados esquerdo e direito das 2 primeiras fórmulas e reduzirmos o resultado em n, obteremos uma importante relação de recorrência, que é chamada de identidade da adição de números de combinação:
A identidade de adição fornece uma regra básica de recorrência para determinar com eficiência o número de combinações para grandes valores de n e m, pois permite que as operações de multiplicação em produtos fatoriais sejam substituídas pelas operações de adição mais simples, e para números menores de combinações. Em particular, utilizando a identidade de adição, agora é fácil determinar o número de combinações de n=10 por m=8 elementos, que foi discutido acima, realizando a seguinte sequência de transformações recorrentes:
Além disso, várias relações úteis para calcular somas finitas podem ser derivadas da identidade de adição, em particular, a fórmula para soma por subscrito, que tem a seguinte forma:
Esta relação é obtida se na identidade de adição expandirmos a recorrência ao longo do termo com maior sobrescrito enquanto seu subscrito for maior que 0. O exemplo numérico a seguir ilustra esse processo de transformações recorrentes:
A fórmula de soma subscrita é frequentemente usada para calcular a soma das potências dos números naturais. Em particular, assumindo m=1, usando esta fórmula é fácil encontrar a soma dos primeiros n números da série natural:
Outra versão útil da fórmula de soma pode ser obtida expandindo a recorrência da identidade de adição ao longo do termo com o menor sobrescrito. O exemplo numérico a seguir ilustra esta versão de transformações recorrentes:
No caso geral, como resultado de tais transformações, obtém-se a soma dos números de combinações, ambos os índices diferem em um dos termos vizinhos, e a diferença nos índices permanece constante (no exemplo considerado, é também igual a um). Assim, obtemos a seguinte fórmula de soma para ambos os índices de números combinados:
Além das relações de recorrência e das fórmulas de soma discutidas acima, muitas outras identidades úteis para números de combinação foram obtidas na análise combinatória. O mais importante entre eles é identidade de simetria, que se parece com isto:
A validade da identidade de simetria pode ser verificada no exemplo a seguir comparando os números de combinações de 5 elementos por 2 e por (5 2) = 3:
A identidade de simetria tem um significado combinatório óbvio, pois, ao determinar o número de opções de seleção de m elementos de n elementos, estabelece simultaneamente o número de combinações dos restantes (nm) elementos não selecionados. A simetria indicada é obtida imediatamente substituindo m por (nm) na fórmula fatorial do número de combinações:
Números e identidades combinadas são amplamente utilizados em diversas áreas da matemática computacional moderna. No entanto, suas aplicações mais populares estão relacionadas ao binômio de Newton e ao triângulo de Pascal.
TEOREMA BINOMIAL
Para realizar diversas transformações e cálculos matemáticos, é importante ser capaz de representar qualquer potência natural de um binômio algébrico (binomial) na forma de um polinômio. Para potências pequenas, o polinômio desejado pode ser facilmente obtido multiplicando diretamente os binômios. Em particular, as seguintes fórmulas para o quadrado e o cubo da soma de dois termos são bem conhecidas no curso de matemática elementar:
No caso geral, para um grau arbitrário n de um binômio, a representação necessária na forma de um polinômio é fornecida pelo teorema binomial de Newton, que declara verdadeira a seguinte igualdade:
Essa igualdade é geralmente chamada de binômio de Newton. O polinômio do lado direito é formado pela soma dos produtos de n termos X e Y do binômio do lado esquerdo, e os coeficientes à frente deles são chamados de binomiais e são iguais ao número de combinações com índices, que são obtidos de seus poderes. Dada a popularidade particular da fórmula binomial de Newton na análise combinatória, os termos coeficiente binomial e número de combinações são geralmente considerados sinônimos.
Obviamente, as fórmulas da soma ao quadrado e ao cubo são casos especiais do teorema binomial para n=2 e n=3, respectivamente. Para lidar com graus superiores (n>3), deve-se usar a fórmula binomial de Newton. Sua aplicação para um binômio de quarto grau (n=4) é demonstrada pelo seguinte exemplo:
Deve-se notar que a fórmula binomial era conhecida antes mesmo de Newton pelos matemáticos medievais do Oriente Árabe e da Europa Ocidental. Portanto, seu nome geralmente aceito não é historicamente justo. O mérito de Newton é que ele generalizou esta fórmula para o caso de um expoente real arbitrário r, que pode assumir quaisquer valores racionais e irracionais positivos ou negativos. No caso geral, tal fórmula binomial de Newton tem uma soma infinita no lado direito e geralmente é escrita da seguinte forma:
Por exemplo, com um valor fracionário positivo do expoente r=1/2, levando em consideração os valores dos coeficientes binomiais, obtém-se a seguinte expansão:
No caso geral, a fórmula binomial de Newton para qualquer expoente é uma versão especial da fórmula de Maclaurin, que fornece a expansão de uma função arbitrária em uma série de potências. Newton mostrou que para |z|< 1 этот ряд сходится, и сумма в правой части становится конечной. При любой натуральной степени r = n в правой части также получается конечная сумма из (n+1) первых слагаемых, так как все C(n, k>n) = 0 . Se agora definirmos Z=X/Y e multiplicarmos os lados esquerdo e direito por Yn, obteremos uma versão da fórmula binomial de Newton discutida acima.
Apesar de sua universalidade, o teorema binomial mantém seu significado combinatório apenas para potências inteiras não negativas do binômio. Neste caso, pode ser usado para provar diversas identidades úteis para coeficientes binomiais. Em particular, as fórmulas para somar o número de combinações por subscrito e por ambos os índices foram discutidas acima. A identidade do somatório sobrescrito ausente pode ser facilmente obtida a partir da fórmula binomial de Newton, colocando X = Y = 1 ou Z = 1 nela:
Outra identidade útil estabelece a igualdade das somas dos coeficientes binomiais com números pares e ímpares. É imediatamente obtido a partir da fórmula binomial de Newton se X = 1 e Y = 1 ou Z = 1:
Finalmente, de ambas as identidades consideradas obtemos a identidade da soma dos coeficientes binomiais apenas com números pares ou ímpares:
Com base nas identidades consideradas e na regra recorrente de remoção de índices sob o sinal do número de combinações, uma série de relações interessantes podem ser obtidas. Por exemplo, se na fórmula de soma sobrescrito substituirmos n em todos os lugares por (n1) e removermos os índices em cada termo, obteremos a seguinte relação:
Utilizando técnica semelhante na fórmula da soma dos coeficientes binomiais com números pares e ímpares, é possível comprovar a validade, por exemplo, da seguinte relação:
Outra identidade útil permite calcular facilmente a soma dos produtos dos coeficientes binomiais localizados simetricamente de dois binômios de graus arbitrários n e k usando a seguinte fórmula de Cauchy:
A validade desta fórmula decorre da necessária igualdade de coeficientes para qualquer grau m da variável Z nos lados esquerdo e direito da seguinte relação idêntica:
No caso especial quando n=k=m, levando em consideração a identidade de simetria, obtém-se uma fórmula mais popular para a soma dos quadrados dos coeficientes binomiais:
Muitas outras identidades úteis para coeficientes binomiais podem ser encontradas na extensa literatura sobre análise combinatória. No entanto, a sua aplicação prática mais famosa está relacionada com o triângulo de Pascal.
TRIÂNGULO DE PASCAL
O triângulo aritmético de Pascal forma uma tabela numérica infinita composta de coeficientes binomiais. Suas linhas são ordenadas por potências de binômios de cima para baixo. Em cada linha, os coeficientes binomiais são organizados em ordem crescente dos sobrescritos dos números de combinação correspondentes, da esquerda para a direita. O triângulo de Pascal é geralmente escrito em forma isósceles ou retangular.
Mais visual e comum é o formato isósceles, onde os coeficientes binomiais, escalonados, formam um triângulo isósceles infinito. Seu fragmento inicial para binômios até o 4º grau (n=4) tem a seguinte forma:
Em geral, o triângulo isósceles de Pascal fornece uma regra geométrica conveniente para determinar coeficientes binomiais, que se baseia nas identidades de adição e na simetria das combinações de números. Em particular, de acordo com a identidade de adição, qualquer coeficiente binomial é a soma dos dois coeficientes da linha anterior mais próximos dele. De acordo com a identidade de simetria, o triângulo isósceles de Pascal é simétrico em relação à sua bissetriz. Assim, cada uma de suas linhas é um palíndromo numérico de coeficientes binomiais. As características algébricas e geométricas indicadas permitem expandir facilmente o triângulo isósceles de Pascal e encontrar de forma consistente os valores dos coeficientes binomiais de potências arbitrárias.
No entanto, para estudar várias propriedades do triângulo de Pascal, é mais conveniente usar o formato retangular formalmente mais estrito. Neste formato, é especificado por uma matriz triangular inferior de coeficientes binomiais, onde formam um triângulo retângulo infinito. O fragmento inicial do triângulo retângulo de Pascal para binômios até o 9º grau (n=9) tem a seguinte forma:
Geometricamente, tal mesa retangular é obtida deformando horizontalmente o triângulo isósceles de Pascal. Como resultado, as séries numéricas paralelas aos lados laterais do triângulo isósceles de Pascal se transformam em verticais e diagonais do triângulo retângulo de Pascal, e as linhas horizontais de ambos os triângulos coincidem. Ao mesmo tempo, as regras de adição e simetria dos coeficientes binomiais permanecem válidas, embora o triângulo retângulo de Pascal perca a simetria visual característica de sua contraparte isósceles. Para compensar isso, torna-se mais conveniente analisar formalmente as várias propriedades numéricas dos coeficientes binomiais para as horizontais, verticais e diagonais do triângulo retângulo de Pascal.
Iniciando a análise das horizontais do triângulo retângulo de Pascal, é fácil perceber que a soma dos elementos de qualquer linha com número n é igual a 2n de acordo com a fórmula de soma de binômios sobrescritos. Segue-se disso que a soma dos elementos acima de qualquer uma das linhas horizontais com número n é igual a (2 n 1). Este resultado torna-se bastante óbvio se o valor da soma dos elementos de cada horizontal for escrito no sistema numérico binário. Por exemplo, para n=4 esta adição pode ser escrita da seguinte forma:
Aqui estão mais algumas propriedades interessantes de horizontais que também estão relacionadas a potências de dois. Acontece que se o número horizontal for uma potência de dois (n=2 k), então todos os seus elementos internos (exceto os externos) são números pares. Pelo contrário, todos os números de uma linha horizontal serão ímpares se o seu número for um a menos que uma potência de dois (n=2 k 1). A validade destas propriedades pode ser verificada verificando a paridade dos coeficientes binomiais internos, por exemplo, nas horizontais n=4 e n=3 ou n=8 e n=7.
Seja agora o número da linha do triângulo retângulo de Pascal um número primo p. Então todos os seus coeficientes binomiais internos são divisíveis por p. Esta propriedade é fácil de verificar para pequenos valores de números primos de contorno. Por exemplo, todos os coeficientes binomiais internos da quinta horizontal (5, 10 e 5) são obviamente divisíveis por 5. Para provar este resultado para qualquer número primo horizontal p, você precisa escrever a fórmula multiplicativa para seus coeficientes binomiais da seguinte forma:
Como p é um número primo e, portanto, não é divisível por m!, o produto dos demais fatores do numerador desta fórmula deve ser divisível por m! para garantir um valor inteiro do coeficiente binomial. Segue-se que a razão entre colchetes é um número natural N e o resultado desejado torna-se óbvio:
A partir deste resultado, podemos estabelecer que os números de todas as retas horizontais do triângulo de Pascal, cujos elementos internos são divisíveis por um determinado número primo p, são potências de p, ou seja, têm a forma n=p k. Em particular, se p=3, então o número primo p divide não apenas todos os elementos internos da linha 3, conforme estabelecido acima, mas, por exemplo, o 9º horizontal (9, 36, 84 e 126). Por outro lado, no triângulo de Pascal é impossível encontrar uma linha horizontal cujos elementos internos sejam todos divisíveis por um número composto. Caso contrário, o número de tal linha horizontal deve ser simultaneamente uma potência dos divisores primos do número composto pelo qual todos os seus elementos internos são divididos, mas isso é impossível por razões óbvias.
As considerações consideradas permitem-nos formular o seguinte critério geral para a divisibilidade dos elementos horizontais do triângulo de Pascal. O máximo divisor comum (MDC) de todos os elementos internos de qualquer linha horizontal do triângulo de Pascal com número n é igual ao número primo p se n=pk ou 1 em todos os outros casos:
GCD(Cmn) = ( ) para qualquer 0< m < n .
Concluindo a análise das horizontais, vale considerar mais uma propriedade interessante que possuem as séries de coeficientes binomiais que as formam. Se os coeficientes binomiais de qualquer linha horizontal com número n forem multiplicados por potências sucessivas do número 10, e então todos esses produtos forem somados, o resultado será 11 n. A justificativa formal para este resultado é a substituição dos valores X=10 e Y=1 (ou Z=1) na fórmula binomial de Newton. O exemplo numérico a seguir ilustra o cumprimento desta propriedade para n=5:
A análise das propriedades das verticais do triângulo retângulo de Pascal pode começar com o estudo das características individuais de seus elementos constituintes. Formalmente, cada vertical m é formada pela seguinte sequência infinita de coeficientes binomiais com um sobrescrito constante (m) e um incremento do subscrito:
Obviamente, quando m=0 obtém-se uma sequência de uns, e quando m=1 forma-se uma série de números naturais. Quando m=2 a vertical é composta por números triangulares. Cada número triangular pode ser representado em um plano na forma de um triângulo equilátero, que é preenchido com objetos arbitrários (núcleos) dispostos em um padrão xadrez. Neste caso, o valor de cada número triangular T k determina o número de núcleos representativos, e o índice mostra quantas linhas de núcleos são necessárias para representá-lo. Por exemplo, 4 números triangulares iniciais representam as seguintes configurações do número correspondente de símbolos nucleares "@":
Deve-se notar que de maneira semelhante podem-se considerar os números quadrados S k , que são obtidos pela quadratura dos números naturais e, em geral, os números figurados poligonais formados pelo preenchimento regular de polígonos regulares. Em particular, os 4 números quadrados iniciais podem ser representados da seguinte forma:
Voltando à análise das verticais do triângulo de Pascal, podemos notar que a próxima vertical em m=3 é preenchida com números tetraédricos (piramidais). Cada um desses números P k especifica o número de núcleos que podem ser organizados na forma de um tetraedro, e o índice determina quantas camadas triangulares horizontais de fileiras de núcleos são necessárias para representá-lo no espaço tridimensional. Neste caso, todas as camadas horizontais devem ser representadas como números triangulares sucessivos. Os elementos das seguintes verticais do triângulo de Pascal para m>3 formam séries de números hipertetraedais, que não possuem uma interpretação geométrica visual no plano ou no espaço tridimensional, mas correspondem formalmente a análogos multidimensionais de números triangulares e tetraédricos.
Embora as séries numéricas verticais do triângulo de Pascal tenham as características de forma individual consideradas, para elas é possível calcular as somas parciais dos valores dos elementos iniciais da mesma forma, utilizando a fórmula para somar os números de combinações por subscrito . No triângulo de Pascal, esta fórmula tem a seguinte interpretação geométrica. A soma dos valores dos n coeficientes binomiais superiores de qualquer vertical é igual ao valor do elemento da próxima vertical, que está localizado uma linha abaixo. Este resultado também é consistente com a estrutura geométrica dos números triangulares, tetraédricos e hipertetraédicos, uma vez que a representação de cada um desses números consiste em camadas centrais que representam números de ordem inferior. Em particular, o enésimo número triangular Tn pode ser obtido somando todos os números naturais que representam suas camadas lineares:
Da mesma forma, não é difícil encontrar o número tetraédrico Pn calculando a seguinte soma dos primeiros n números triangulares que constituem suas camadas centrais horizontais:
Além das horizontais e verticais no triângulo retângulo de Pascal, podem-se traçar fileiras diagonais de elementos, cujo estudo de propriedades também é de algum interesse. Nesse caso, geralmente é feita uma distinção entre diagonais descendentes e ascendentes. As diagonais descendentes são paralelas à hipotenusa do triângulo retângulo de Pascal. Eles são formados por séries de coeficientes binomiais com incremento de ambos os índices. Devido à identidade da simetria, as diagonais descendentes coincidem nos valores de seus elementos com as linhas verticais correspondentes do triângulo de Pascal e, portanto, repetem todas as suas propriedades discutidas acima. A correspondência indicada pode ser traçada pela coincidência dos valores dos elementos da diagonal descendente e da vertical com qualquer número n, se os zeros verticais não forem levados em consideração:
As diagonais ascendentes formam séries numéricas geometricamente perpendiculares à hipotenusa do triângulo retângulo de Pascal. Eles são preenchidos com coeficientes binomiais com decremento do menor e incremento do sobrescrito. Em particular, as 7 diagonais ascendentes superiores formam a seguinte sequência numérica sem levar em conta os zeros à direita:
Em geral, o número diagonal ascendente n contém os seguintes coeficientes binomiais, cuja soma dos índices de cada um deles é igual a (n1):
Em virtude da identidade de adição para números de combinação, cada elemento da diagonal é igual à soma de dois elementos correspondentes em índices das duas diagonais ascendentes anteriores. Isso permite que cada diagonal ascendente subsequente seja construída pela soma aos pares de elementos horizontais adjacentes das duas diagonais anteriores, expandindo infinitamente o triângulo de Pascal ao longo da diagonal. O seguinte fragmento do triângulo de Pascal ilustra a construção de uma diagonal ascendente número 8 ao longo das diagonais numeradas 6 e 7:
Com este método de construção, a soma dos elementos de qualquer diagonal ascendente, a partir da 3ª, será igual à soma dos elementos das duas diagonais ascendentes anteriores, e as 2 primeiras diagonais consistem em apenas um elemento, o valor dos quais é 1. Os resultados dos cálculos correspondentes formam a seguinte série numérica, segundo a qual é possível verificar a validade da propriedade considerada das diagonais ascendentes do triângulo retângulo de Pascal:
Analisando esses números, você pode ver que de acordo com uma lei semelhante, forma-se a conhecida sequência de números de Fibonacci, onde cada número seguinte é igual à soma dos dois anteriores, e os dois primeiros números são iguais a 1:
Assim, podemos tirar a seguinte conclusão importante: as somas diagonais dos elementos do triângulo de Pascal constituem a sequência de Fibonacci. Esta propriedade permite-nos estabelecer outra característica interessante do triângulo de Pascal. Expandindo a fórmula de Fibonacci recursivamente, é fácil provar que a soma dos primeiros n números de Fibonacci é igual a (F n+2 1).
Portanto, a soma dos coeficientes binomiais que preenchem as n diagonais superiores também é igual a (F n+2 1). Segue-se que a soma das primeiras n diagonais do triângulo de Pascal é 1 menor que a soma dos coeficientes binomiais que estão em sua diagonal com o número (n+2).
Concluindo, deve-se notar que as propriedades consideradas das horizontais, verticais e diagonais do triângulo de Pascal não esgotam a enorme variedade de possibilidades que conectam vários aspectos matemáticos que à primeira vista nada têm em comum. Tais propriedades incomuns nos permitem considerar o triângulo de Pascal um dos sistemas numéricos mais perfeitos, cujas capacidades não podem ser listadas e são difíceis de superestimar.
O algoritmo para cálculo do número de combinações utilizando o triângulo de Pascal é apresentado a seguir:
Função privada SochTT (ByVal n como inteiro, ByVal k como inteiro) As Double Dim i As Integer Dim j As Integer Dim TT () As Double ReDim TT (n, k) For i = 0 To n TT (0, i) = 1 TT (i, i) = 1 Próximo Para i = 2 Para n Para j = 1 Para i - 1 TT (i, j) = TT (i - 1, j - 1) + TT (i - 1, j) Próximo Próximo SochTT = TT (n, k) Função Final
Se você precisar calcular o número de combinações muitas vezes, pode ser mais conveniente construir o triângulo de Pascal uma vez e depois receber os dados do array.
Dim TT () As Double Private Sub CreateTT () ReDim TT (0, 0) BuildTT 0, 0 End Sub Private Function SochTT (ByVal n As Integer, ByVal k As Integer) As Double If n > Ubound (TT) Then BuildTT Ubound (TT) + 1, n SochTT = TT (n, k) Função final Private Sub TerminateTT () ReDim TT (0, 0) End Sub Private Sub BuildTT (ByVal start As Integer, ByVal end As Integer) Dim i As Integer Dim j As Integer ReDim Preserve TT (fim, fim) For i = início Para fim TT (0, i) = 1 TT (i, i) = 1 Próximo If fim< 2 Then Exit Sub If start < 2 Then start = 2 For i = start To end For j = 1 To i - 1 TT (i, j) = TT (i - 1, j - 1) + TT (i - 1, j) Next Next End Sub
Primeiro você precisa chamar o procedimento CreateTT. Você pode então obter o número de combinações usando a função SochTT. Quando você não precisar mais do triângulo, chame o procedimento TerminateTT. No código acima, ao chamar a função SochTT, se o triângulo ainda não tiver sido concluído no nível exigido, ele será concluído usando o procedimento BuildTT. A função então obtém o elemento desejado do array TT e o retorna.
Dim X () Como Inteiro Dim Contador () Como Inteiro Dim K Como Inteiro Dim N Como Inteiro Public Sub Soch() Dim i As Integer N = CInt(InputBox("Enter N")) K = CInt(InputBox("Enter K ")) K = K + 1 ReDim X(N) For i = 1 To N X(i) = i Next txtOut.Text = "" ReDim Counter(K) Counter(0) = 1 SochGenerate 1 End Sub Private Sub SochGenerate( ByVal c As Integer) Dim i As Integer Dim j As Integer Dim n1 As Integer Dim Out() As Integer Dim X1() As Integer If c = K Then ReDim Out(K) X1 = X For i = 1 To K - 1 n1 = 0 Para j = 1 Para N Se X1(j)<>0 Então n1 = n1 + 1 Se n1 = Contador(i) Então Out(i) = X1(j) X1(j) = 0 Sair para End If Next txtOut.Text = txtOut.Text & CStr(Out(i)) Próximo txtOut.Text = txtOut.Text & vbCrLf Else For Counter (c) = Counter (c - 1) To N - c + 1 SochGenerate c + 1 Next End If End Sub
LISTANDO COMBINAÇÕES DE NÚMEROS NATURAIS
Para resolver muitos problemas práticos, é necessário listar todas as combinações de cardinalidade fixa que podem ser obtidas a partir dos elementos de um determinado conjunto finito, e não apenas determinar o seu número. Tendo em conta a possibilidade sempre existente de numeração inteira dos elementos de qualquer conjunto finito, na maioria dos casos é permitido limitar-nos à utilização de algoritmos de enumeração de combinações de números naturais. O mais natural e simples deles é o algoritmo para listar combinações de números naturais em ordem lexigráfica.
Para descrever formalmente este algoritmo, é conveniente assumir que o conjunto principal, cujas combinações de m elementos devem ser listadas, formam números naturais consecutivos de 1 a n. Então qualquer combinação de m Como resultado da ordenação, o valor em cada posição de tal vetor de combinações acaba naturalmente sendo limitado em valor acima e abaixo da seguinte forma: O algoritmo lexigráfico gera sequencialmente tais vetores de combinação, começando com o menor vetor lexigraficamente, onde todas as posições contêm os seguintes valores mínimos possíveis de elementos iguais aos seus índices: Cada vetor de combinação sucessivo é formado a partir do atual após varrer seus elementos da esquerda para a direita para encontrar o elemento mais à direita que ainda não atingiu seu valor limite: O valor de tal elemento deve ser aumentado em 1. A cada elemento à direita dele deve ser atribuído o menor valor possível, que é 1 maior que seu vizinho à esquerda. Após essas alterações, o próximo vetor de combinações terá a seguinte composição elementar: Assim, o próximo vetor de combinação será lexigraficamente maior que o anterior, pois os valores de seus elementos iniciais (j1) são iguais em valor, e o valor do elemento na posição j é 1 maior que o do anterior. . A relação especificada de ordem lexigráfica crescente é garantidamente satisfeita em todas as iterações do algoritmo. O resultado é uma sequência lexigráfica crescente, que é completada pelo maior vetor de combinação lexigraficamente, onde os elementos em todas as posições possuem os seguintes valores máximos: O algoritmo lexigráfico considerado é ilustrado pelo exemplo a seguir, onde é necessário listar em ordem lexigráfica crescente todas as 15 combinações de n=6 primeiros números naturais por m=4 números, ou seja, todos os possíveis subconjuntos de 4 elementos da geração principal conjunto (1, 2, 3, 4, 5, 6) de 6 elementos. Os resultados do cálculo são apresentados na tabela a seguir: Neste exemplo, os maiores valores permitidos de números nas posições dos vetores de combinação são, respectivamente, 3, 4, 5 e 6. Para facilitar a interpretação dos resultados, em cada vetor de combinação, o elemento mais à direita, que tem ainda não atingiu o seu valor máximo, está sublinhado. Os índices numéricos de vetores de combinação determinam seus números em ordem lexigráfica. No caso geral, o número lexigráfico N de qualquer combinação de n elementos por m pode ser calculado usando a seguinte fórmula, onde, por razões cosméticas, o simbolismo de Appel é usado para denotar os números de combinações: Em particular, os seguintes cálculos utilizando esta fórmula para o número de combinação (1, 3, 4, 6) de n=6 elementos de m=4 em ordem lexigráfica darão o resultado N=8, que corresponde ao exemplo discutido acima: No caso geral, utilizando a identidade para a soma dos números de combinações de ambos os índices, é possível mostrar que o número da menor combinação lexigraficamente (1, ... i, ... m) quando calculado usando este fórmula será sempre igual a 1: É também óbvio que o número da maior combinação lexigraficamente (m, … nm+i, … n) quando calculado usando esta fórmula será igual ao número de combinações de n elementos por m: A fórmula para calcular números de combinação lexigráfica pode ser usada para resolver o problema inverso, onde é necessário determinar o vetor de combinação por seu número em ordem lexigráfica. Para resolver tal problema inverso, ele deve ser escrito na forma de uma equação, onde todos os valores desconhecidos dos elementos do vetor da combinação desejada (C 1, ... C i, ... C m ) estão concentrados no número de combinações de seu lado direito, e a diferença conhecida L do número de combinações é escrita no lado esquerdo de n elementos cada m e o número da combinação necessária N: A solução para esta equação é fornecida pelo seguinte algoritmo “ganancioso”, durante cujas iterações os valores dos elementos do vetor da combinação desejada são selecionados sequencialmente. Na iteração inicial, é selecionado o valor mínimo possível (dentro de suas limitações) de C 1, no qual o primeiro termo do lado direito terá um valor máximo não superior a L: Agora o lado esquerdo de L deve ser reduzido pelo primeiro número de combinações no lado direito com o valor selecionado de C 1, e da mesma forma determinar o valor de C 2 na segunda iteração: Da mesma forma, todas as iterações subsequentes devem ser realizadas para selecionar os valores de todos os outros elementos C i da combinação desejada, até o último elemento C m: Por razões óbvias, o valor do último elemento C m pode ser determinado com base na igualdade do seu número de combinações ao valor residual do lado esquerdo de L: Deve-se notar que o valor do último elemento da combinação C m pode ser encontrado de forma ainda mais simples, sem enumerar seus valores possíveis: A implementação das iterações do algoritmo considerado é ilustrada pelo seguinte exemplo, onde é necessário determinar combinações com o número N=8 em ordem lexigráfica, se n=6 e m=4: A capacidade algorítmica de determinar uma combinação de um determinado número em ordem lexigráfica pode ser usada em várias direções. Em particular, ao listar as combinações em ordem lexigráfica, é necessário garantir o retorno a qualquer combinação obtida anteriormente, bastando saber apenas o seu número. Além disso, torna-se possível gerar combinações em qualquer ordem, que é regulada por uma sequência dada arbitrariamente de seus números lexigráficos. Agora apresentamos um algoritmo para geração de combinações em ordem lexicográfica: 2 para i:= 1 para k fazer A[i] := i; 5 comece a escrever(A,…, A[k]); 6 se A[k] = n então p:= p 1 senão p:= k; 8 para i:= k até p fazer A[i] := A[p] + i p + 1 COMBINAÇÕES COM ELEMENTOS DE REPETIÇÃO Ao contrário de uma combinação clássica, onde todos os elementos são diferentes, uma combinação com repetições forma uma seleção desordenada de elementos de um conjunto finito, onde qualquer elemento pode aparecer com frequência indefinida e não está necessariamente presente em uma única cópia. Nesse caso, o número de repetições de elementos geralmente é limitado apenas pelo comprimento da combinação, sendo consideradas diferentes combinações que diferem em pelo menos um elemento. Por exemplo, escolhendo 4 números opcionalmente diferentes do conjunto 1, 2 e 3, você pode criar as seguintes 15 combinações com repetições: 1111 1112 1113 1122 1123 1133 1222 1223 1233 1333 2222 2223 2233 2333 3333.
Em geral, combinações com repetições podem ser formadas selecionando n elementos de tipos arbitrários. No entanto, eles sempre podem ser associados a números naturais consecutivos de 1 a n. Então, qualquer combinação de m números opcionalmente diferentes neste intervalo pode ser escrita na forma vetorial, organizando-os em ordem não decrescente da esquerda para a direita: Naturalmente, com esta forma de notação, quaisquer elementos vizinhos podem ser iguais devido à possibilidade de repetições ilimitadas. No entanto, cada vetor de combinação com repetições de n elementos por m pode ser associado a um vetor de combinação de (n+m−1) elementos por m, que é construído da seguinte forma: É claro que para quaisquer valores dos elementos do vetor f, os elementos do vetor C são garantidos como diferentes e estritamente ordenados em ordem crescente de seus valores no intervalo de 1 a (n+m1) : A presença de uma correspondência biunívoca entre os elementos dos vetores de combinação f e C nos permite propor o seguinte método simples para listar sistematicamente combinações com repetições de n elementos por m. Basta listar, por exemplo, em ordem lexigráfica, todas as combinações C de (n+m1) elementos de m, transformando sequencialmente os elementos de cada um deles nos elementos correspondentes de combinações com repetições f usando a seguinte fórmula: Como resultado, forma-se uma sequência de vetores de combinações com repetições de elementos, que são dispostos na ordem gerada pela listagem das combinações correspondentes sem repetições de elementos. Em particular, para obter a sequência acima de combinações de 3 dígitos 1, 2 e 3 com repetições de 4 dígitos, é necessário listar em ordem lexigráfica todas as combinações sem repetições de 6 dígitos 1,2,3,4, 5 e 6 têm 4 dígitos cada, convertendo-os conforme indicado. O exemplo a seguir mostra essa conversão da combinação (1,3,4,6) com o número lexicográfico 8: A correspondência considerada um-a-um entre combinações com e sem repetições de elementos significa que seus conjuntos são igualmente poderosos. Portanto, no caso geral, o número de combinações com repetições de n elementos por m é igual ao número de combinações sem repetições de (n+m1) elementos por m. Usando o mesmo simbolismo para denotar os números de combinações com repetições f e sem repetições C, esta igualdade pode ser escrita da seguinte forma: É fácil verificar que para o exemplo considerado acima, onde n=3 e m=4, o número de combinações de repetições será igual a 15, o que coincide com o resultado da sua listagem direta: Deve-se notar que, diferentemente da versão clássica, os valores dos parâmetros de combinação com repetições n e m não estão diretamente relacionados entre si, portanto f(n,m)>0 para qualquer combinação de seus valores positivos. As condições de contorno correspondentes são determinadas a partir da igualdade entre os valores de (n+m1) e (n1) ou (n+m1) e m: Também deveria ser bastante óbvio que se m for igual a 1, então nenhuma repetição de elementos será possível e, portanto, para qualquer valor positivo de n>0 a seguinte igualdade será verdadeira: Além disso, para números de combinações com repetições para quaisquer valores positivos de n e m, é válida a seguinte relação de recorrência, que é semelhante à identidade de adição para números de combinações sem repetições de elementos: Na verdade, ele se transforma na identidade de adição indicada mediante substituição formal dos números correspondentes de combinações sem repetições em seus lados esquerdo e direito: A relação de recorrência considerada pode ser utilizada para determinar efetivamente o número de combinações com repetições, quando é importante eliminar as operações intensivas em mão-de-obra de cálculo de produtos fatoriais e substituí-las por operações de adição mais simples. Neste caso, para calcular o valor de f(n,m), basta aplicar esta relação de recorrência até obter a soma dos termos da forma f(1,m) e f(i,1), onde i assume valores na faixa de n a 1. Por definição de quantidade tais termos são iguais a 1 e i, respectivamente. O exemplo a seguir ilustra o uso desta técnica de transformação para o caso de n=3 e m=4: LISTANDO COMBINAÇÕES BINÁRIAS Ao implementar combinações em hardware ou programação em linguagem assembly, é importante poder processar registros de combinação em formato binário. Neste caso, qualquer combinação de n elementos de m deve ser especificada na forma de um número binário de n bits (B n,...B j,...B 1), onde m dígitos unitários indicam os elementos do combinação, e os dígitos restantes (nm) têm valores zero. Obviamente, com esta forma de notação, diferentes combinações devem diferir na disposição dos dígitos 1, e existem apenas C(n,m) maneiras de organizar m unidades ou (nm) zeros em um conjunto binário de n bits. Por exemplo, a tabela a seguir lista todas as 6 combinações binárias, que fornecem números binários de 4 bits para todas as combinações de 4 elementos de um conjunto arbitrário (E 1 , E 2 , E 3 , E 4 ) por 2: No caso geral, a tarefa de enumerar tais combinações binárias se resume a uma busca sistemática de todos os conjuntos binários de n bits com diferentes arranjos de m um e (nm) zero bits. Na forma mais simples, essa pesquisa é implementada por vários métodos de transposição de bits adjacentes com deslocamento (algoritmos de deslocamento transpositivo). Estes são algoritmos iterativos e seus nomes refletem a natureza das operações executadas em cada etapa. Os procedimentos iterativos dos algoritmos de deslocamento transpositivo formam sequências de combinações binárias que começam com um conjunto binário, onde todos os uns estão concentrados nos dígitos de ordem inferior (à direita), e terminam quando todos os 1's estão nos dígitos de ordem superior ( à esquerda): Embora correspondam nas combinações inicial e final, essas sequências diferem na ordem em que os conjuntos binários intermediários são listados. No entanto, em todos os casos, cada combinação binária subsequente é formada a partir da anterior como resultado da execução das operações de transposição e deslocamento correspondentes. Ao mesmo tempo, vários algoritmos de deslocamento transpositivo diferem na maneira como selecionam um par de bits para transposição e um grupo de bits para deslocamento. Esta especificidade é discutida abaixo para algoritmos de transposição com deslocamento para a esquerda e para a direita. No algoritmo de transposição com deslocamento à esquerda, em cada etapa, a próxima combinação binária é obtida da atual, substituindo o par de dígitos mais à esquerda 01 por 10 (transposição) e deslocando o grupo de dígitos unitários iniciais, se houver, para perto de o par 10 obtido após a transposição (shift). Se neste caso não houver unidades nos dígitos iniciais da combinação binária atual, então o deslocamento não será realizado, mesmo quando a unidade inicial for obtida após a transposição nesta etapa. O deslocamento também não é realizado quando não há zeros nos bits mais significativos antes do par 10 obtido após a transposição. As ações consideradas são ilustradas pelo seguinte exemplo de realização de duas iterações sucessivas deste algoritmo, onde em uma iteração (15) apenas a transposição (T") é realizada, e na outra iteração (16) a transposição é complementada por um deslocamento ( T"+S"): No algoritmo de transposição para a direita, etapas conceitualmente semelhantes são executadas em cada etapa. Somente a transposição garante que os bits mais à direita de 01 sejam substituídos por 10 (em vez dos mais à esquerda) e então todos os bits à direita sejam deslocados para os bits menos significativos. Como antes, o deslocamento é realizado somente se houver unidades que possam ser deslocadas para a direita. As ações consideradas são ilustradas pelo seguinte exemplo de realização de duas iterações sucessivas deste algoritmo, onde em uma iteração (3) apenas a transposição (T") é realizada, e na outra iteração (4) a transposição é complementada por um deslocamento ( T"+S"): Deve-se notar que as iterações de ambos os algoritmos podem ser escritas na forma aditiva se as combinações binárias forem interpretadas como números inteiros no sistema numérico de base 2. Em particular, para o algoritmo de transposição com deslocamento à direita, cada próxima combinação binária (B" n ,…B" j , …B" 1), sempre pode ser obtido a partir da combinação atual (B n,…B j,…B 1) realizando as operações de adição de inteiros usando a seguinte fórmula aditiva: Nesta fórmula aditiva, os expoentes das potências de dois f e t denotam, respectivamente, o número de dígitos zero de ordem inferior da combinação binária atual e o número de unidades consecutivas à esquerda deles. Por exemplo, para a 4ª combinação binária (001110) de n=6 dígitos f =1 e t =3. Portanto, calcular a próxima combinação binária usando a fórmula aditiva na iteração 5 dará o seguinte resultado, equivalente a realizar as operações de transposição e deslocamento: Para uma análise comparativa dos algoritmos de transposição considerados com deslocamentos para a esquerda e para a direita, é aconselhável comparar as sequências de combinações binárias que eles geram em suas iterações. A tabela a seguir mostra duas sequências de combinações binárias de 4 elementos de 2, que são obtidas pelos algoritmos de deslocamento para a esquerda (TSL) e para a direita (TSR), respectivamente: Comparando essas 2 sequências, você pode ver que elas são espelho reverso. Isso significa que quaisquer duas combinações binárias localizadas nelas à mesma distância das extremidades mutuamente opostas de suas sequências são uma imagem espelhada uma da outra, ou seja, coincidem quando a indexação dos bits em qualquer uma delas é invertida. Por exemplo, o segundo padrão binário desde o início da sequência TSL (0101) é uma imagem espelhada do padrão binário (1010) que é o segundo a partir do final da sequência TSR. Em geral, qualquer combinação binária com o número i de uma sequência é uma imagem espelhada de uma combinação binária com o número (ni+1) de outra sequência. Esta relação entre estas sequências é consequência da natureza simétrica das operações de transposição e deslocamento nos dois algoritmos considerados para enumeração de combinações binárias. Ressalta-se que o formato binário também pode ser utilizado para registrar combinações com repetições de elementos. Para fazer isso, é necessário estabelecer uma correspondência um a um entre combinações com repetições e combinações binárias, que são construídas da seguinte forma. Seja uma combinação arbitrária com repetições, que é obtida escolhendo m elementos opcionalmente diferentes dos n elementos do conjunto gerador. Para estabelecer a correspondência desejada, você deve primeiro adicionar todos os elementos do conjunto formador (cat) à combinação e, em seguida, classificar a concatenação resultante (sort) para que todos os elementos idênticos fiquem lado a lado. O resultado é uma sequência de (n+m) elementos, onde existem n grupos de elementos idênticos. Haverá um total de (n+m1) lacunas entre elementos, entre as quais haverá (n1) lacunas entre grupos de elementos idênticos e m lacunas entre elementos dentro de grupos. Para maior clareza, você pode colocar os símbolos “|” nos espaços indicados. e correspondentemente. Se agora combinarmos 1 com os espaços entre os grupos (|) e 0 com todos os outros espaços (), obteremos uma combinação binária. É formado por um conjunto binário de (n+m1) bits, onde (n1) são unidades e m zero bits, cuja localização corresponde exclusivamente à combinação original com repetições dos elementos n a m. A técnica de transformação considerada é ilustrada pelo seguinte exemplo de construção de uma combinação binária (1001101) usando uma combinação com repetições (BBD), cujos elementos são selecionados do conjunto gerador das cinco primeiras letras latinas: Em geral, o número de tais conjuntos binários determina o número de maneiras de organizar (n1) unidades (ou m zeros) em (n+m1) dígitos binários. Este valor é obviamente igual ao número de combinações de (n+m1) por (n1) ou por m, ou seja, C(n+m1,n1) ou C(n+m1,m), que é igual ao número de combinações com repetições f( n,m) de n elementos, m cada. Assim, tendo uma correspondência um a um entre combinações com repetições e combinações binárias, é legítimo reduzir a enumeração de combinações com repetições à enumeração de combinações binárias, por exemplo, utilizando algoritmos de transposição com deslocamento para a esquerda ou para a direita. Depois disso, você só precisa restaurar as combinações necessárias com repetições usando as combinações binárias resultantes. Isso sempre pode ser feito usando a seguinte técnica de recuperação. Deixe o conjunto principal, a partir dos quais se formam combinações com repetições de m elementos não necessariamente diferentes, ser ordenado de forma arbitrária para que cada um de seus elementos tenha um certo número de série de 1 a n. Vamos implementar também a enumeração de combinações binárias de (n+m1) dígitos binários, onde (n1) unidades e m dígitos zero. Cada combinação binária resultante pode ser complementada à esquerda com um dígito unitário fictício, e todos os dígitos unitários podem ser numerados da esquerda para a direita com números inteiros de 1 a n. Então, o número de zeros consecutivos após cada i-ésima unidade da combinação binária será igual ao número de instâncias do i-ésimo elemento do conjunto principal na combinação correspondente com repetições. A técnica considerada é ilustrada pelo exemplo a seguir, onde, por meio de uma combinação binária (1001101), é restaurada uma combinação com repetições de BBD, cujos elementos são selecionados do conjunto gerador das cinco primeiras letras latinas, escritas em ordem alfabética , e o sobrelinha indica elementos que estão ausentes nesta combinação: Ao realizar ações semelhantes nas condições deste exemplo, você pode listar todas as 35 combinações binárias que formam conjuntos binários de 7 bits, onde existem 4 uns e 3 zeros, e restaurar as combinações correspondentes com repetições de 5 elementos de 3. O inverno se aproximava e Khoma e Suslik decidiram estocar ervilhas. Durante todo o dia eles correram para o celeiro e carregaram vários grupos: Khoma, quatro, e Suslik, dois. À noite, eles contaram todas as vagens que haviam colhido e se perguntaram como dividir essas ervilhas agora. Khoma argumentou que se ele arrastasse o dobro de Suslik de cada vez, então deveria obter o dobro de ervilhas. Suslik objetou razoavelmente a isso que, em primeiro lugar, a velocidade de Khoma é visivelmente menor que a de Suslik e, em segundo lugar, quem sabe, talvez Khoma tenha fugido apenas uma ou duas vezes, e no resto do tempo ele ficou ocioso... Ajude seus amigos a entender pelo menos um pouco essa situação difícil. Determine todas as opções possíveis para quantos frutos Suslik trouxe e quantos Khoma. Na primeira linha há um número par natural M – o número de cápsulas roubadas, 2 ≤ M ≤ 1000. Todas as combinações possíveis das quantidades de frutos trazidos por Suslik e Khoma, uma combinação por linha. Cada combinação representa dois inteiros não negativos separados por um espaço: o primeiro número é o número de frutos trazidos por Suslik, o segundo – trazido por Khoma. Classifique as combinações em ordem decrescente do primeiro número. #incluir usando namespace std; int principal()( int a, b = 0; cin >> uma; enquanto (a >= 0 ) ( corte<<
a
<<
" "
<<
b
<<
"\n"
;
uma -= 4 ; b+= 4; retornar 0; Seja a o número de frutos trazidos por Homa e b o número de frutos trazidos por Suslik. Como, de acordo com as condições do problema, Khoma carregava apenas quatro frutos, consideraremos a = a-4 e b = b + 4 para assim enumerar todas as combinações possíveis dos números de frutos trazidos por Suslik e Khoma. Vamos também usar um loop enquanto, que repetirá a ação descrita acima até \geq 0. Na resposta imprimimos todas as combinações possíveis dos números de pods trazidos pelos amigos, um por linha, ordenados em ordem decrescente do primeiro número. Exemplo // Combinações de 3 de 52 for (int i1 = 0; i1< 50; ++i1)
for (int i2 = i1+1; i2 < 51; ++i2)
for (int i3 = i2+1; i3 < 52; ++i3)
// ...
Aqui veremos um problema mais complexo, cuja solução não encontrei no RuNet (no entanto, darei um link, mas essa fórmula está claramente incorreta) - com base na própria combinação (neste caso, um conjunto de três números) encontre seu índice. Suponhamos, para maior definição, após ordenar i1 = 3, i2 = 7, i3 = 12. Um algoritmo de geração típico é gerar combinações de 2 de 52, e para cada combinação em um loop aninhado, geramos combinações de 3 de 50 e verificamos se os índices (i3, i4, i5) na combinação aninhada não não coincidem com os índices (i1, i2) em combinação externa: Código C++ // COMBINAÇÃO EXTERNA para (int i1 = 0; i1< 51; ++i1)
for (int i2 = i1+1; i2 < 52; ++i2)
// ВНУТРЕННЕЕ СОЧЕТАНИЕ
for (int i3 = 0; i3 < 50; ++i3)
if (i3 != i1 && i3 != i2)
for (int i4 = i3+1; i4 < 51; ++i4)
if (i4 != i1 && i4 != i2)
for (int i5 = i4+1; i5 < 52; ++i5)
if (i5 != i1 && i5 != i2)
// ...
Código C++ se (i3 >= i1) --i3; se (i3 >= i2) --i2; // semelhante para i4, i5 Código de exemplo para índice dividido por 2, 3, 47 int get_split_2_3_47_index(int i1, int i2, int i3, int i4, int i5) ( // Índice da combinação de 2 de 52, multiplicado por C(3, 50) int offset = ((52*51 - (51-i1) *(52-i1)) / 2 + (i2 - i1 - 1)) * 19600; // “Reindexar” o grupo interno para que a numeração seja 0...49 if (i3 > = i1) --i3; if (i3 >= i2) --i3; if (i4 >= i1) --i4; if (i4 >= i2) --i4; if (i5 >= i1) --i5 ; if (i5 >= i2) --i5; // Agora adicione o índice da combinação por 3 // 0: // SUM para n = 0 por i3-1 COMBINATIONS (2, 49-n) // = SUM para m = 50-i3 por 49 (m * (m-1) / 2) deslocamento += (19600 - (((49-i3)*(50-i3)*(99-2*i3)) / 6 - ((49-i3)*(50-i3 )) / 2) / 2); // 1: // SOMA para n = i3+1 a i4-1 COMBINAÇÕES (1, 49-n) offset += (( (48-i3)*(49-i3) - (49-i4)*(50-i4)) / 2); // 2: // SOMA para n = i4+1 a i5-1 (1) deslocamento + = (i5 - i4 - 1); deslocamento de retorno ; ) Em geral, eu dividiria os algoritmos combinatórios nas seguintes classes: Número de combinações Combinação de n Por k chamado de conjunto k elementos selecionados dos dados n elementos. Conjuntos que diferem apenas na ordem dos elementos (mas não na composição) são considerados idênticos; é por isso que as combinações diferem dos posicionamentos. Número de combinações de n Por k
igual ao coeficiente binomial Por um valor fixo n função geradora de números de combinações com repetições de n Por ké: A função geradora bidimensional de números de combinações com repetições é: Fundação Wikimedia. 2010. 70 setenta 67 68 69 70 71 72 73 40 50 60 70 80 90 100 Fatoração: 2×5×7 Notação romana: LXX Binário: 100 0110 ... Wikipedia Número leve, um número condicional que expressa exclusivamente o externo condições durante a fotografia (geralmente o brilho do assunto e a fotossensibilidade do material fotográfico utilizado). Qualquer valor de E. h. pode ser selecionado diversas vezes. número de abertura de combinações... ... Grande Dicionário Enciclopédico Politécnico Uma forma de número que distingue dois objetos tanto em relação a um único objeto quanto em relação a muitos objetos. Esta forma não existe no russo moderno, mas permanecem vestígios de sua influência. Então, combinações de duas tabelas (cf. plural... ... Dicionário de termos linguísticos Matemática combinatória, combinatória, um ramo da matemática dedicado à resolução de problemas de escolha e organização de elementos de um determinado conjunto, geralmente finito, de acordo com determinadas regras. Cada uma dessas regras determina o método de construção... ... Enciclopédia Matemática Em combinatória, uma combinação de by é um conjunto de elementos selecionados de um determinado conjunto contendo diferentes elementos. Conjuntos que diferem apenas na ordem dos elementos (mas não na composição) são considerados idênticos, essas combinações ... ... Wikipedia Envolvido no estudo de eventos cuja ocorrência não é conhecida com certeza. Permite-nos julgar a razoabilidade de esperar a ocorrência de alguns eventos em comparação com outros, embora muitas vezes seja desnecessário atribuir valores numéricos às probabilidades dos eventos... ... Enciclopédia de Collier 1) o mesmo que análise combinatória matemática. 2) Uma seção de matemática elementar associada ao estudo do número de combinações, sujeitas a certas condições, que podem ser compostas a partir de um determinado conjunto finito de objetos... ... Grande Enciclopédia Soviética - (paradoxos gregos inesperados, estranhos) em sentido amplo: uma afirmação que diverge acentuadamente da opinião geralmente aceita e estabelecida, uma negação do que parece “incondicionalmente correto”; num sentido mais restrito, duas afirmações opostas, pois... ... Enciclopédia Filosófica - (ou o princípio das inclusões e exclusões) uma fórmula combinatória que permite determinar a cardinalidade da união de um número finito de conjuntos finitos, que no caso geral podem se cruzar entre si... Wikipedia Uma teoria matemática preocupada em determinar o número de diferentes maneiras de distribuir determinados objetos em uma ordem conhecida; é especialmente importante na teoria das equações e na teoria das probabilidades. As tarefas mais simples deste tipo são... ... Dicionário Enciclopédico F.A. Brockhaus e I.A. EfronDados de entrada
Saída
Testes
Dados de entrada
Saída
6
\\ 6 \; 0 \\ 2 \; 4
11
\\ 11\;0 \\ 7\;4 \\ 3\;8
18
\\ 18\;0 \\ 14\;4 \\ 10\;8 \\ 6\;12 \\ 2\;16
Código do programa
A solução do problema
Índice de combinação
Cada combinação, permutação, arranjo e outros objetos combinatórios podem ser associados a um índice - este é o número em que aparece ao iterar por meio deste algoritmo.
Existe a opção de pesquisar “de frente”. Ligamos o contador de combinações, pegamos o algoritmo acima e tentamos de tudo até chegarmos à opção desejada. Esta opção tem uma complexidade de tempo muito elevada, por isso iremos descartá-la.
Vamos supor que a entrada contenha os números i1, i2, i3. Em primeiro lugar, precisamos organizá-los em ordem crescente (observe que o próprio algoritmo de geração, dado acima, sempre os produz de forma ordenada, embora o próprio conceito de “combinação” implique uma ordem arbitrária).
Isso significa que “passamos” por todas as combinações onde i1 era igual a 0, 1 e 2.
Para i1 = 0, passamos por C(2, 51) combinações, já os índices i1, i2 passam por todas as combinações de 2 dos 51 números.
Para i1 = 1 passamos por combinações C(2, 50).
Para i1 = 2 passamos por combinações C(2, 49).
No total, passamos por SUM (de n = 0 a n = i1-1) C(2, 51-n).
Para i1 = 3, vamos considerar as combinações pelas quais passamos enquanto percorríamos o índice i2 (e para nós começa com i2 = i1+1 = 4).
Quando i2 = 4, combinações C(1, 47) aprovadas, quando i2 = 5, combinações C(1, 46) aprovadas, quando i2 = 6, combinações C(1, 45) aprovadas.
Por analogia completa, para i2 = 7 consideramos as combinações que o índice i3 percorreu.
Obtemos a fórmula geral:
O índice de combinação necessário = SOMA (de n = 0 a i1-1) C(2, 51-n) + SOMA (de n = i1+1 a i2-1) C(1, 51-n) + SOMA (de n = i2+1 a i3-1) C (0, 51-n).Índice de subconjunto
Na combinatória existe um objeto mais complexo - o particionamento em subconjuntos. Por exemplo, dividir um conjunto de 52 elementos em três subconjuntos de, digamos, 2, 3 e 47 elementos, respectivamente, onde a ordem dos elementos dentro de cada subconjunto não é importante. (A propósito, uma combinação de 2 de 52 é simplesmente um caso especial de divisão em dois subconjuntos de 2 e 50 elementos, respectivamente).
Novamente, cada partição tem seu próprio índice.
Acontece que nosso algoritmo para encontrar o índice de combinação pode ser modificado para encontrar o índice de partição.
Deve-se notar que precisamos organizar os índices da “combinação externa” i1, i2 entre si, e os índices i3, i4, i5 entre si, mas independentemente dos dois primeiros.
Deve-se também levar em consideração que em uma “combinação aninhada” estamos trabalhando essencialmente com um conjunto de 50 elementos, mas os índices i3, i4, i5 precisam ser “deslocados” de uma certa forma para que não mudem de 0 a 51, mas de 0 a 49:
(por assim dizer, cortamos os índices i1, i2 do nosso conjunto de 52 elementos e depois deslocamos o conjunto restante para fechar os buracos, enquanto os índices i3-i5 são deslocados).
Deve-se levar em conta que dentro de cada combinação “externa” temos exatamente C(3, 50) combinações “aninhadas”.
Então o algoritmo será reduzido ao seguinte:
COMBINATION_INDEX (i1, i2 de 52) * COMBINATION_NUMBER BY_3_OF_50 + COMBINATION_INDEX (i3, i4, i5 de 50 após a mudança do índice). Trazendo algoritmos para complexidade constante
Devo observar imediatamente que ocorre um “erro” na fórmula se, por exemplo, i1 = 0 (contamos a soma para n = de 0 a -1) ou i2 = 1 (contamos a soma de 1 a 0). Na verdade, nesses casos a soma correspondente deve ser considerada igual a zero e o resultado estará correto.
Devo também prestar atenção à complexidade de tempo dos nossos algoritmos: eles têm complexidade linear, desde que consideremos C como um tempo constante. Isso já é muito melhor do que força bruta.
Mas na verdade (no nosso caso 52) nada nos impede de reduzir o algoritmo a uma complexidade constante. Para isso, aplicaremos conhecimentos de matemática e calcularemos analiticamente todos os valores.
Por exemplo, o número de combinações C(2, K), se você “expandi-lo” na forma de uma fórmula K! / ((K-2)! * 2!), reduz a um polinômio de 2º grau. E como o temos sob o sinal de soma, podemos aplicar as fórmulas para a soma das enésimas potências dos números na série natural (ver Wikipedia) e obter um único polinômio de 3º grau. O que obviamente tem complexidade de tempo constante. (Além disso, o “erro” que citei no início do subtítulo não se manifesta de forma alguma; a fórmula permanece correta).
Repito, isso para uma dimensão fixa do conjunto base. Porém, tenho certeza que com a ajuda da metaprogramação você poderá “ensinar” o compilador para que ele faça esse trabalho para você. Posfácio
No meu simulador de pôquer (Texas Hold'em), eu queria calcular e armazenar antecipadamente as probabilidades de vitória para todas as combinações possíveis das cartas da minha mão (2 peças) e de todas as cartas do flop (3 cartas na mesa). o conjunto 52 por 2, 3, 47 subconjuntos.
Calculado e salvo.
Mas quando chegou a hora de ler dados de um arquivo para uma combinação específica, eu realmente não queria calcular algo por muito tempo ou pesquisar em um arquivo de gigabyte. Agora apenas determino o deslocamento no arquivo e leio diretamente o que preciso.
Seria interessante ter um livro de referência sobre algoritmos combinatórios para todos os objetos combinatórios, incluindo permutações, combinações, posicionamentos, subconjuntos, combinações com repetições, posicionamentos com repetições. Fórmulas explícitas
Ligações
Veja o que é “Número de combinações” em outros dicionários:
Livros