Combinatória em Python

A biblioteca python padrão, iniciando na versão 2.2, fornece muitas ferramentas para gerar objetos combinatórios, mas não consegui encontrar um único artigo na Internet que contasse detalhes sobre como trabalhar com eles. Por isso, decidi corrigir essa omissão.

Para começar, falarei sobre combinatória e suas fórmulas básicas. Se você já conhece esta seção da matemática, pode pular estes parágrafos.

Suponha que tenhamos uma sequência composta por n letras diferentes e desejemos calcular todas as maneiras de reorganizá-las de maneira a obter uma nova linha. Para a primeira posição na linha, podemos escolher uma das n letras que temos, para a segunda posição uma das n- 1as letras e assim por diante. Como resultado, obtemos o produto n (n-1) ... * 1 = n! o número de permutações de n elementos sem repetição .

Agora imagine que o número de letras em uma string é limitado. Temos n letras disponíveis e queremos calcular o número de maneiras de criar uma cadeia de comprimento k a partir delas, onde k <n, cada letra que podemos usar apenas uma vez. Em seguida, podemos colocar uma das n letras na primeira posição da linha, uma das n-1 na segunda posição e uma das n-k + 1 na k-ésima posição. O número total de linhas será igual a n (n - 1) (n - 2) ... (n - k + 2) (n - k + 1) = n! / (Nk)! o número de canais de n a k . Se a singularidade das letras não for necessária, obteremos a fórmula n ... n n = n ^ k o número de colocações de n a k com repetições .

Antes disso, classificamos as seqüências levando em consideração a ordem dos elementos e se a ordem não importa para nós. Por exemplo, temos n balas diferentes e queremos escolher k entre elas para dar a um amigo e k <n. Quantas maneiras existem para escolher k balas de n sem levar em conta a ordem? A resposta é simples: no início, encontraremos um posicionamento de n por k sem repetição, mas os mesmos conjuntos de doces com ordem diferente de sequência serão repetidos. Quantas maneiras existem para reorganizar k balas? É isso mesmo, uma permutação de k elementos sem repetição. A resposta final: os posicionamentos de n por k são divididos por permutações de k sem repetições. Formula $$$n! / (n-k)! / k!$o número de combinações de n por k .

Considere o caso mais complicado: temos n caixas cada uma das quais contém muitos doces do mesmo gosto, mas em caixas diferentes os gostos são diferentes. Quantas maneiras existem de fazer um presente para um amigo com k doces e qual o mesmo sabor que pode ocorrer inúmeras vezes? Como o pedido não importa para nós, vamos organizar os doces para presentes da seguinte forma: no início, haverá sucessivamente doces do primeiro sabor, depois do segundo e assim por diante, e colocaremos correspondências entre doces de diferentes gostos, se os doces de algum gosto estiverem ausentes no presente - as partidas que deveriam delimitar esse gosto à esquerda e à direita ficarão lado a lado. Além disso, obtemos uma sequência que consiste em k doces e correspondências n-1, pois existem apenas n gostos e as separam. Agora observe que, pela localização das correspondências, podemos restaurar o conjunto original. A resposta será o número de maneiras de colocar uma correspondência n-1 em uma célula n + k-1 sem levar em conta a ordem, que é igual ao número de combinações de n + k-1 por n-1, a fórmula: $$$(n + k-1)! / k! / (n-1)!$o número de combinações de n a k com repetições .

Agora, consideraremos vários problemas na combinatória para consolidar o material.

Tarefa 1

Existem 20 pessoas, quantas maneiras existem para emparelhá-las
Solução: considere a primeira pessoa, quantas maneiras existem para escolher um par para ele: $$$20-1 = 19$, pegue a segunda pessoa, quantas maneiras existem para escolher um par para ele: $$$20-2-1 = 17$. Resposta: 19 !!! = 654729075

Tarefa 2

Existem 10 homens e 10 meninas, quantas maneiras existem para dividi-las em empresas que consistem no mesmo número de homens e meninas, uma empresa vazia não é considerada
Solução:
Método 1: o número de maneiras de montar uma empresa de um homem e uma garota é igual ao produto do número de maneiras de escolher uma garota e o número de maneiras de escolher um homem. O número de maneiras de escolher uma garota de 10 é igual a uma combinação de 10 a 1 sem repetição, é semelhante aos homens, portanto, vamos acertar as contas. Em seguida, calculamos da mesma forma as combinações de 10 a 2, de 10 a 3, e assim por diante até a combinação de 10 a 10. A fórmula final: $$$(10! / (10-1)! / 1!) ^ 2 + (10! / (10-2)! / 2!) ^ 2 + ... + (10! / (10-10)! / 10!) ^ 2$.
Método 2: considere os muitos homens que estão na empresa e as muitas meninas que não estão na companhia dela. Para esse conjunto, você pode restaurar definitivamente a empresa, e o número de pessoas nela é sempre igual a 10, pois $$$k + (10 - k) = 10$, k - o número de homens na empresa, $$ - o número de meninas não incluídas nele. O número de tais conjuntos é igual ao número de combinações de 20 a 10; na resposta final, também subtrairemos um para não levar em conta a empresa vazia quando houver 10 meninas em nosso conjunto. A fórmula final: $$$20! / (20-10)! / 10! - 1 = US $ 18475$.

Então, descobrimos a teoria, agora aprenderemos como gerar objetos combinatórios usando a biblioteca python padrão.
Trabalharemos com a biblioteca itertools

from itertools import * 

Usando a função permutações , você pode gerar todas as permutações para um objeto iterável.

Exemplo 1

 for i in permutations('abc'): print(i, end=' ') # abc acb bac bca cab cba print() for i in permutations('abb'): print(i, end=' ') # abb abb bab bba bab bba 

Com base na segunda chamada, observamos que os mesmos elementos em posições diferentes são considerados diferentes.

Exemplo 2

 for i in permutations('abc', 2): print(i, end=' ') # ab ac ba bc ca cb 

A colocação difere da permutação pelo limite do número de células disponíveis

Exemplo 3

 for i in product('abc', repeat=2): print(i, end=' ') # aa ab ac ba bb bc ca cb cc 

Com layouts de repetição, é possível iterar facilmente sobre todas as seqüências de comprimento fixo que consistem em caracteres específicos

Exemplo 4

 for i in combinations('abcd', 2): print(i, end=' ') # ab ac ad bc bd cd 

Usando combinações sem repetições, é possível iterar em todos os conjuntos de letras não repetidas de uma determinada sequência, matriz ou outro objeto iterável sem levar em consideração a ordem

Exemplo 5

 for i in combinations_with_replacement('abcd', 2): print(i, end=' ') # aa ab ac ad bb bc bd cc cd dd 

O resultado é semelhante a chamar combinações , mas conjuntos com os mesmos elementos também são adicionados ao resultado.

Materiais:
N.V. Gorbachev "Coleção de problemas das olimpíadas em matemática"
Documentação Python em russo