MO640 - Questão para a prova oral

Número: 032

Enunciado:
Quanto à ordenação de permutações (baseado nos textos de transposição e troca de blocos) podemos afirmar que (considere perm(0)=0 e perm(n+1)=n+1):

1. Em um grafo de ciclos de uma permutação, as arestas cinzas são direcionadas de i+1 para i.
2. [perm(i), perm(i+1)] é um breakpoint se perm(i+1)=perm(i)+1.
3. Uma troca de blocos com parâmetros (i,j,k,l), realiza a troca de [perm(i) ... perm(j)] e [perm(k) ... perm(l)].
4. Numa transposição p(i,j,k) com i < j < k, trocamos [perm(i) ... perm(j-1)] e [perm(j) ... perm(k-1)].
5. NDA

Autor(a): Paulo Renato de Faria