90
edits
Changes
Jump to navigation
Jump to search
→3. Permutações
==='''3. Permutações'''===
Nós já mostramos como contar e gerar combinações usando Maple. Podemos agora introduzir recursos análogos do Maple para trabalhar com permutações. As funções Maple correspondentes para permutações são “numbperm”''numbperm'', “permute” ''permute'' e “randperm”''randperm''. Já que todas estão no pacotes “combinat”''combinat'', devem ser carregadas antes de serem usadas.
'''''with(combinat):'''''
'''''numbperm([S,U,C,C,E,S,S]);'''''
'''''randperm([S,U,C,C,E,S,S]);'''''
'''''randperm(5);'''''
Usando o pacote “combstruct”''combstruct'', esses exemplos são feitos da seguinte forma:
'''''with(combstruct):'''''
'''''count(Permutation([S,U,C,C,E,S,S]));'''''
'''''draw(Permutation(5));'''''
A função “subsets” ''subsets'' permite gerar todos os subconjuntos de um conjunto dado. Já que os subconjuntos e combinações são apenas diferentes nomes para a mesma coisa, você pode usar essa função para gerar combinações. A função “subsets” ''subsets'' retorna uma tabela que contém duas entradas. Uma é chamada “nextvalue”''nextvalue'', e é um procedimento para gerar a próxima combinação, e a outra é “finished”''finished'', uma flag true/flase false que informa quando todas elas foram geradas.
'''''S := combinat[subsets](a,b):'''''
'''''while not S[finished] do'''''
'''''od;'''''
Usando “combstruct”''combstruct'', uma faz a mesma coisa usando a função “iterstructs”''iterstructs''. O procedimento “iterstructs” ''iterstructs'' também retorna uma tabela, mas dessa vez usa as funções “next” ''next'' e “finished” ''finished'' para iterar.
'''''S := iterstructs(Subset(a,b)):'''''
'''''while not finished(S) do'''''
''''' nextstruct(S);'''''
'''''od;'''''
Usando “iterstructs”''iterstructs'', podemos também iterar sobre permutações e tradições. Em adição, nós podemos especificar que tamanho de objeto nós queremos ver.
'''''P := iterstructs(Permutation([a,b,b]), size=2):'''''
'''''while not finished(P) do'''''
Pelo fatos das função de permutação Maple poderem resolver problemas de permutação com elementos indistinguíveis tão facilmente quanto sem elementos indistinguíveis, alguns dos exercícios do texto se tornam triviais. Por exemplo, exercício 266 pergunta quantas strings diferentes podem ser formadas com as letras em MISSISSIPPI usando todas as letras.
A solução pode ser encontrada em um passo:
'''''numbperm([M,I,S,S,I,S,S,I,P,P,I]);'''''
A questão 299 é similar, mas envolve alguns passos extras. Ela pergunta quantas strings diferentes podem ser feitas a partir das letras em ORONO, usando uma ou todas as letras. Para achar a solução, primeiramente calculamos o número de 1-permutações, depois com 2-permutações, etc.
'''''total := 0:'''''
'''''total;'''''
Existem 633 strings possíveis usando uma ou todas as letras em ORONO. 644 se nós contarmos as string com 0 letras.
'''''numbperm([O,R,O,N,O],0);'''''Usando o pacote “combstruct”''combstruct'', nós podemos achar a resposta em um passo.
'''''with(combstruct):'''''
'''''count(Permutation([O,R,O,N,O]), size='allsizes');'''''
Também existem funções para fazer partições de inteiros. (Uma partição de inteiro é um modo de escrever um inteiro '''n''' como a soma de inteiros positivos, onde ordem não importa. Então <math>5=1+1+3</math> é uma partição de inteiro do 5.) Junto ao ''numbpart'', ''partition'' e ''randpart'', existem funções para gerar partições, uma por vez, baseada em uma dada ordem canônica. Todas estas funções são parte do pacote ''combinat'' que deve, consequentemente, ser carregado antes de você acessá-las.
'''''with(combinat):'''''
O número de partições de um dado inteiro pode ser contado usando o procedimento “numbpart”''numbpart''.
'''''seq(numbpart(i), i = 1..20);'''''
As partições de um inteiro podem ser computadas usando a função “partition”''partition''.
'''''partition(5);'''''
Isso constrói as partições de seu argumento como uma lista de listas, cada sublista representando uma partição.
