Générer la liste de toutes les permutations possibles d’une chaîne

Question

Comment pourrais-je aller sur la génération d’une liste de toutes les permutations possibles d’une chaîne entre x et y de caractères, contenant une liste de variables de caractères.

N’importe quelle langue fonctionnerait, mais il devrait être portable.

Answer 1

Il y a plusieurs façons de le faire. Les méthodes courantes d'utiliser la récursivité, memoization, ou de la programmation dynamique. L'idée de base est que vous devez produire une liste de toutes les chaînes de caractères de longueur 1, puis, à chaque itération, pour toutes les chaînes produites dans la dernière itération, ajouter cette chaîne concaténée avec chaque caractère de la chaîne individuellement. (l'indice de variable dans le code ci-dessous permet de suivre le début de la dernière et de la prochaine itération)

Certains pseudo-code:

list = originalString.split('')
index = (0,0)
list = [""]
for iteration n in 1 to y:
  index = (index[1], len(list))
  for string s in list.subset(index[0] to end):
    for character c in originalString:
      list.add(s + c)

vous pouvez avoir besoin de supprimer toutes les chaînes moins de x en longueur, ils seront les premiers (x-1) * len(originalString) les entrées dans la liste.

---

Mike Stone a écrit:

Pour info, alumb du pseudocode a un bug...

Bon appel de Mike. J'ai modifié ma solution pour résoudre ce problème et à une initialisation de bug.

Answer 2

son mieux d’utiliser la recherche inverse

Answer 3

Vous allez obtenir un grand nombre de chaînes, c'est sûr...

Où x et y est de savoir comment vous définissez et r est le nombre de caractères que nous sélectionnons de --si je suis à vous comprendre correctement. Vous devriez certainement générer ces que de besoin et de ne pas se la couler douce et de dire, de générer un powerset, puis filtrer la longueur des chaînes.

La suivante n'est certainement pas la meilleure façon de générer ces, mais c'est intéressant de côté, aucun-le-moins.

Knuth (volume 4, fascicule 2, 7.2.1.3) nous dit que (s,t)-combinaison est équivalent à s+1 choses prises t à la fois avec la répétition, un (s,t)-combinaison est la notation utilisée par Knuth qui est égal à . Nous pouvons comprendre cela en générant d'abord chaque (s,t)-combinaison sous forme binaire (donc de longueur (s+t)) et en comptant le nombre de " 0 " à gauche de chaque 1.

10001000011101 --> devient la permutation: {0, 3, 4, 4, 4, 1}

Answer 4

Solution non récursive selon Knuth, exemple Python :

Answer 5

Certains code Java basé sur la réponse de Sarpde travail :