générer une séquence avec toutes les permutations

Question

Comment puis-je générer la séquence la plus courte avec toutes les permutations possibles? Pour la longueur 2, la réponse est 121, car cette liste contient 12 et 21, qui sont toutes permutations possibles.

Pour longueur 3 la réponse est 123121321, parce que cette liste contient toutes les permutations possibles: 123, 231, 312, 121 (invalides), 213, 132, 321.

Chaque numéro (dans une permutation donnée) peut seulement se produire une fois.

Answer 1

Cet algorithme glouton produit des séquences minimales assez courtes.

MISE À JOUR: Notez que for n ≥ 6, this algorithm does not produce the shortest possible string!

• Faire une collection de toutes les permutations.
• Supprime la première permutation de la collection.
• Soit une = la première permutation.
• Recherchez la séquence de la collection qui présente le plus grand chevauchement avec la fin de a. S'il y a une égalité, choisissez la séquence en premier dans l'ordre lexicographique. Supprimez la séquence sélectionnée de la collection et ajoutez la partie qui ne se chevauche pas à la fin de a. Répétez cette étape jusqu'à ce que la collection soit vide.

La curieuse étape de rupture d'égalité est nécessaire pour l'exactitude; casser la cravate au hasard semble plutôt entraîner des chaînes plus longues.

J'ai vérifié (en écrivant un programme beaucoup plus long et plus lent) que la réponse donnée par cet algorithme pour la longueur 4, 123412314231243121342132413214321, est en effet la réponse la plus courte. Cependant, pour la longueur 6, elle produit une réponse de longueur 873, qui est plus longue que la solution la plus courte connue. L'algorithme est 0 (n!).

Une mise en œuvre dans le python:

import itertools 

def costToAdd(a, b): 
    for i in range(1, len(b)): 
     if a.endswith(b[:-i]): 
      return i 
    return len(b) 

def stringContainingAllPermutationsOf(s): 
    perms = set(''.join(tpl) for tpl in itertools.permutations(s)) 
    perms.remove(s) 
    a = s 
    while perms: 
     cost, next = min((costToAdd(a, x), x) for x in perms) 
     perms.remove(next) 
     a += next[-cost:] 
    return a 

La longueur des chaînes générées par cette fonction sont 1, 3, 9, 33, 153, 873, 5913, ... qui semble être this integer sequence.

J'ai un pressentiment que vous pouvez faire mieux que O (n !).

Answer 2

• Créer toutes les permutations.
• Que chaque permutation représente un nœud dans un graphique .
• Maintenant, pour deux états ajouter un bord avec une valeur 1 si elles partagent n-1 chiffres (pour la source de la fin , et pour la cible de la fin ), deux si elles partagent n-2 chiffres et bientôt.
• Maintenant, vous êtes à gauche pour trouver le chemin le plus court contenant n vertices.

Answer 3

Voici un algorithme rapide qui produit une chaîne courte contenant toutes les permutations. Je suis sûr qu'il donne la réponse la plus courte possible, mais je n'ai pas une preuve complète en main.

Explication. Ci-dessous un arbre de toutes les permutations. L'image est incomplète. Imaginez que l'arbre continue pour toujours vers la droite.

1 --+-- 12 --+-- 123 ... 
    |  | 
    |  +-- 231 ... 
    |  | 
    |  +-- 312 ... 
    | 
    +-- 21 --+-- 213 ... 
      | 
      +-- 132 ... 
      | 
      +-- 321 ... 

Les nœuds au niveau k de cet arbre sont toutes les permutations de longueur k. En outre, les permutations sont dans un ordre particulier avec un lot de chevauchement entre chaque permutation et ses voisins au-dessus et au-dessous de .

Pour être précis, le premier enfant de chaque nœud est trouvé en ajoutant simplement le symbole suivant à la fin. Par exemple, le premier enfant de 213 serait 2134. Le reste des enfants sont trouvés en tournant au premier enfant à gauche un symbole à une fois. La rotation 2134 produirait 1342, 3421, 4213.

Compte tenu de tous les noeuds à un niveau donné et les enchaînant, qui se chevauchent autant que possible, produit les chaînes 1, 121, 123121321, etc.

Le longueur de la n cette chaîne est the sum for x=1 to n of x!. (Vous pouvez le prouver en observant à quel point non-chevauchement qui existe entre les permutations voisines frères et soeurs se chevauchent dans tout sauf 1 symbole;. Cousins ​​germains se chevauchent dans tout sauf 2 symboles,. Etc.)

Esquisse de la preuve. Je n'ai pas complètement prouvé que c'est la meilleure solution, mais voici un croquis de la façon dont la preuve procéderait. Tout d'abord montrer que toute chaîne contenant n permutations distinctes a une longueur n - 1. Ensuite, montrer que l'ajout d'une chaîne contenant n +1 permutations distinctes a une longueur de 2 n + 1. C'est, l'ajout d'un plus la permutation vous coûtera deux chiffres. Procéder en calculant la longueur minimale de chaînes contenant _n P _r et _n P r + 1 permutations distinctes, jusqu'à n!. En bref, cette séquence est optimale parce que vous ne pouvez pas l'aggraver quelque part dans l'espoir de l'améliorer ailleurs. C'est déjà localement optimal partout. Tous les mouvements sont forcés.

Algorithme. Compte tenu de tout ce contexte, l'algorithme est très simple. Marcher cet arbre à la profondeur désirée et enchaîner tous les nœuds à cette profondeur.

Heureusement, nous n'avons pas besoin de construire l'arbre en mémoire.

def build(node, s): 
    """String together all descendants of the given node at the target depth.""" 
    d = len(node) # depth of this node. depth of "213" is 3. 
    n = len(s)  # target depth 
    if d == n - 1: 
     return node + s[n - 1] + node # children of 213 join to make "2134213" 
    else: 
     c0 = node + s[d]     # first child node 
     children = [c0[i:] + c0[:i] for i in range(d + 1)] # all child nodes 
     strings = [build(c, s) for c in children] # recurse to the desired depth 
     for j in range(1, d + 1): 
      strings[j] = strings[j][d:] # cut off overlap with previous sibling 
     return ''.join(strings)   # join what's left 

def stringContainingAllPermutationsOf(s): 
    return build(s[:1], s) 

Performances. Le code ci-dessus est déjà beaucoup plus rapide que mon autre solution, et il fait beaucoup de couper et coller de grandes chaînes que vous pouvez optimiser. L'algorithme peut être fait pour fonctionner dans le temps et la mémoire proportionnelle à la taille de la sortie.