Gostaria de gerar eficientemente uma lista de permutações "válidas" a partir de uma lista fornecida.
Por meio de um exemplo simples, suponha que eu gostaria de gerar as permutações de [1,2,3]onde 3está em uma das duas primeiras posições. Meu resultado de retorno seria então[[3,1,2], [3,2,1], [1,3,2],[2,3,1]]
Atualmente, posso resolver esse problema filtrando cada permutação em um loop. Não preciso gerar todas as permutações, pois posso usar uma bijeção de inteiros para uma permutação, apenas para economizar memória.
De qualquer forma, esse método não é realmente viável quando minha lista começa a crescer - há simplesmente muitas permutações para percorrer.
Um exemplo mais realista é que eu gostaria de gerar as permutações de [1,2,...20]com comprimento 10, onde minhas regras são algo como [1,2]deve aparecer nos três primeiros lugares (em qualquer ordem), [3,4]deve terminar nos cinco primeiros lugares (em qualquer ordem) e assim por diante (para qualquer entrada razoável do usuário).
Há 6.704425728 E+11valores para verificar no loop aqui, então, na verdade, são muitos.
Meus pensamentos iniciais são de que pode haver duas maneiras de fazer isso:
- Gere apenas permutações válidas usando as regras para gerar subpermutações e, em seguida, combine-as.
- De alguma forma, represente as permutações em uma árvore e aplique filtragem na árvore. Dessa forma, se um nó falhar em uma regra, todos os filhos desse nó também falharão na regra. Isso permitiria reduzir drasticamente a verificação em muitos casos (dependendo das regras).
Alguém já teve alguma experiência fazendo algo assim e poderia fornecer alguma orientação? Ou isso é simplesmente um problema complicado que requer computação monumental?