Permutações com subsequências proibidas

15

Deixe [n] denotar o conjunto {1,...,n} e C (n, k) denotam o conjunto de todas as combinações de k de elementos de [n] sem repetição. Seja p=p1p2...pk ser um -tuple em . Dizemos que uma permutação do conjunto evita se não houver k-tupla de números inteirosC ( n , k ) π : [ n ] [ n ] [ n ] p i 1 < i 2 < . . . < i k π ( i 1 ) = p 1 ,kC(n,k)π:[n][n][n]pi1<i2<...<iktal que

π(i1)=p1,π(i2)=p2,...,π(ik)=pk.

Por exemplo, se , a permutação evita como uma subsequência, enquanto a permutação não.12453 134 1 2 3 5 4n=51245313412354

Pergunta: Seja uma constante. Dado um conjunto de -tuples, encontrar uma permutação , que evitem cada -tuple em . S C ( n , k ) k π : [ n ] [ n ] k SkSC(n,k)kπ:[n][n]kS

  1. Existe um algoritmo para esse problema que é polinomial eme ? Aqui é dado em unário. Um algoritmo rodando no tempo seria bom.|P|nnnf(k)|P|g(k)
  2. Ou esse problema é NP-completo?

Quaisquer referências para esse problema ou sugestões de algoritmos são bem-vindas. Observe que a noção de permutação que evita a subsequência definida acima não é a mesma que a noção de padrão de evitação de permutação, onde apenas a ordem relativa dos elementos é importante e que parece ser bem estudada na combinatória.

Mateus de Oliveira Oliveira
fonte
Você quer fazer uma permutação aleatória e verificar se ela não viola nenhuma restrição em S? Um algoritmo de tempo polinomial aleatório seria melhor que nada. k é assumido como uma constante, portanto é por definição pequeno. Mas não vejo como isso funcionaria eficientemente se S tivesse muitas restrições. Já que, pela resposta de David, o problema é NPC para k = 3, estou um pouco cético quanto ao fato de um algoritmo aleatório ser eficiente. Poderia explicar um pouco sua ideia?
Mateus de Oliveira Oliveira
Desculpe, eu esqueci que você tem um conjunto de tuplas proibidas. Não há garantia de que a amostragem por rejeição seja eficiente.
DW

Respostas:

13

k=3n

David Eppstein
fonte