Générer une liste de toutes les permutations possibles d'une chaîne
https://stackoverflow.com/questions/361
-
08-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Comment pourrais-je générer une liste de toutes les permutations possibles d'une chaîne entre x et y caractères de longueur, contenant une liste variable de caractères.
N’importe quelle langue fonctionnerait, mais elle devrait être portable.
La solution
Il y a plusieurs moyens de le faire.Les méthodes courantes utilisent la récursivité, la mémorisation ou la programmation dynamique.L'idée de base est que vous produisez une liste de toutes les chaînes de longueur 1, puis à chaque itération, pour toutes les chaînes produites lors de la dernière itération, ajoutez cette chaîne concaténée avec chaque caractère de la chaîne individuellement.(l'index variable dans le code ci-dessous garde la trace du début de la dernière et de la prochaine itération)
Un pseudocode :
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 devrez alors supprimer toutes les chaînes de longueur inférieure à x, ce seront les premières entrées (x-1) * len(originalString) de la liste.
Autres conseils
Il vaut mieux utiliser le backtracking
#include <stdio.h>
#include <string.h>
void swap(char *a, char *b) {
char temp;
temp = *a;
*a = *b;
*b = temp;
}
void print(char *a, int i, int n) {
int j;
if(i == n) {
printf("%s\n", a);
} else {
for(j = i; j <= n; j++) {
swap(a + i, a + j);
print(a, i + 1, n);
swap(a + i, a + j);
}
}
}
int main(void) {
char a[100];
gets(a);
print(a, 0, strlen(a) - 1);
return 0;
}
Vous allez avoir beaucoup de ficelles, c'est sûr...
\sum_{i=x}^y{\frac{r!}{{(r-i)}!}} http://www.codecogs.com/eq.latex?%5Csum_%7Bi=x%7D%5Ey% 20%7B%20%5Cfrac%7Br!%7D%7B%7B(r-i)%7D!%7D%20%7D
Où, x et y sont la façon dont vous les définissez et r est le nombre de caractères parmi lesquels nous sélectionnons - si je vous comprends bien.Vous devez absolument les générer selon vos besoins et ne pas être négligent et dire, générer un ensemble de puissances, puis filtrer la longueur des chaînes.
Ce qui suit n’est certainement pas la meilleure façon de les générer, mais c’est néanmoins un aparté intéressant.
Knuth (volume 4, fascicule 2, 7.2.1.3) nous dit que la combinaison (s,t) est équivalente à s+1 choses prises t à la fois avec répétition - une combinaison (s,t) est une notation utilisée par Knuth qui est égal à {t \choose {s+t} http://www.codecogs.com/eq.latex?%7Bt%20%5Cchoose%20%7Bs+t%7D%7D.Nous pouvons comprendre cela en générant d’abord chaque combinaison (s,t) 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}
Solution non récursive selon Knuth, exemple Python :
def nextPermutation(perm):
k0 = None
for i in range(len(perm)-1):
if perm[i]<perm[i+1]:
k0=i
if k0 == None:
return None
l0 = k0+1
for i in range(k0+1, len(perm)):
if perm[k0] < perm[i]:
l0 = i
perm[k0], perm[l0] = perm[l0], perm[k0]
perm[k0+1:] = reversed(perm[k0+1:])
return perm
perm=list("12345")
while perm:
print perm
perm = nextPermutation(perm)
Vous pourriez regarder "Énumérer efficacement les sous-ensembles d'un ensemble", qui décrit un algorithme pour faire une partie de ce que vous voulez : générer rapidement tous les sous-ensembles de N caractères de la longueur x à y.Il contient une implémentation en C.
Pour chaque sous-ensemble, vous devrez toujours générer toutes les permutations.Par exemple, si vous vouliez 3 caractères de "abcde", cet algorithme vous donnerait "abc", "abd", "abe"...mais il faudrait permuter chacun pour obtenir "acb", "bac", "bca", etc.
Du code Java fonctionnel basé sur La réponse de Sarp:
public class permute {
static void permute(int level, String permuted,
boolean used[], String original) {
int length = original.length();
if (level == length) {
System.out.println(permuted);
} else {
for (int i = 0; i < length; i++) {
if (!used[i]) {
used[i] = true;
permute(level + 1, permuted + original.charAt(i),
used, original);
used[i] = false;
}
}
}
}
public static void main(String[] args) {
String s = "hello";
boolean used[] = {false, false, false, false, false};
permute(0, "", used, s);
}
}
Voici une solution simple en C#.
Il génère uniquement les permutations distinctes d'une chaîne donnée.
static public IEnumerable<string> permute(string word)
{
if (word.Length > 1)
{
char character = word[0];
foreach (string subPermute in permute(word.Substring(1)))
{
for (int index = 0; index <= subPermute.Length; index++)
{
string pre = subPermute.Substring(0, index);
string post = subPermute.Substring(index);
if (post.Contains(character))
continue;
yield return pre + character + post;
}
}
}
else
{
yield return word;
}
}
Il y a beaucoup de bonnes réponses ici.Je suggère également une solution récursive très simple en C++.
#include <string>
#include <iostream>
template<typename Consume>
void permutations(std::string s, Consume consume, std::size_t start = 0) {
if (start == s.length()) consume(s);
for (std::size_t i = start; i < s.length(); i++) {
std::swap(s[start], s[i]);
permutations(s, consume, start + 1);
}
}
int main(void) {
std::string s = "abcd";
permutations(s, [](std::string s) {
std::cout << s << std::endl;
});
}
Note:les chaînes avec des caractères répétés ne produiront pas de permutations uniques.
Je viens de préparer ça rapidement dans Ruby :
def perms(x, y, possible_characters)
all = [""]
current_array = all.clone
1.upto(y) { |iteration|
next_array = []
current_array.each { |string|
possible_characters.each { |c|
value = string + c
next_array.insert next_array.length, value
all.insert all.length, value
}
}
current_array = next_array
}
all.delete_if { |string| string.length < x }
end
Vous pourriez examiner l'API du langage pour les fonctions de type permutation intégrées, et vous pourrez peut-être écrire du code plus optimisé, mais si les chiffres sont si élevés, je ne suis pas sûr qu'il existe un moyen d'obtenir beaucoup de résultats. .
Quoi qu'il en soit, l'idée derrière le code est de commencer par une chaîne de longueur 0, puis de garder une trace de toutes les chaînes de longueur Z où Z est la taille actuelle dans l'itération.Ensuite, parcourez chaque chaîne et ajoutez chaque caractère à chaque chaîne.Enfin, à la fin, supprimez ceux qui étaient inférieurs au seuil x et renvoyez le résultat.
Je ne l'ai pas testé avec une entrée potentiellement dénuée de sens (liste de caractères nulle, valeurs étranges de x et y, etc.).
Ceci est une traduction de la version Ruby de Mike, en Common Lisp :
(defun perms (x y original-string)
(loop with all = (list "")
with current-array = (list "")
for iteration from 1 to y
do (loop with next-array = nil
for string in current-array
do (loop for c across original-string
for value = (concatenate 'string string (string c))
do (push value next-array)
(push value all))
(setf current-array (reverse next-array)))
finally (return (nreverse (delete-if #'(lambda (el) (< (length el) x)) all)))))
Et une autre version, légèrement plus courte et utilisant davantage de fonctionnalités de boucle :
(defun perms (x y original-string)
(loop repeat y
collect (loop for string in (or (car (last sets)) (list ""))
append (loop for c across original-string
collect (concatenate 'string string (string c)))) into sets
finally (return (loop for set in sets
append (loop for el in set when (>= (length el) x) collect el)))))
Voici une solution récursive simple en C# :
Méthode:
public ArrayList CalculateWordPermutations(string[] letters, ArrayList words, int index)
{
bool finished = true;
ArrayList newWords = new ArrayList();
if (words.Count == 0)
{
foreach (string letter in letters)
{
words.Add(letter);
}
}
for(int j=index; j<words.Count; j++)
{
string word = (string)words[j];
for(int i =0; i<letters.Length; i++)
{
if(!word.Contains(letters[i]))
{
finished = false;
string newWord = (string)word.Clone();
newWord += letters[i];
newWords.Add(newWord);
}
}
}
foreach (string newWord in newWords)
{
words.Add(newWord);
}
if(finished == false)
{
CalculateWordPermutations(letters, words, words.Count - newWords.Count);
}
return words;
}
Appel:
string[] letters = new string[]{"a","b","c"};
ArrayList words = CalculateWordPermutations(letters, new ArrayList(), 0);
En Perl, si vous souhaitez vous limiter à l'alphabet minuscule, vous pouvez faire ceci :
my @result = ("a" .. "zzzz");
Cela donne toutes les chaînes possibles entre 1 et 4 caractères en minuscules.Pour les majuscules, changez "a" à "A" et "zzzz" à "ZZZZ".
Pour les cas mixtes, cela devient beaucoup plus difficile et probablement impossible avec l'un des opérateurs intégrés de Perl comme celui-ci.
...et voici la version C :
void permute(const char *s, char *out, int *used, int len, int lev)
{
if (len == lev) {
out[lev] = '\0';
puts(out);
return;
}
int i;
for (i = 0; i < len; ++i) {
if (! used[i])
continue;
used[i] = 1;
out[lev] = s[i];
permute(s, out, used, len, lev + 1);
used[i] = 0;
}
return;
}
permuter (ABC) -> A.perm(BC) -> A.perm[B.perm(C)] -> A.perm[(*BC), (CB*)] -> [(*UNC.-B.), (BUNC), (C.-B.UN*), (*UNCB), (CUNB), (CBUN*)] Pour supprimer les doublons lors de l'insertion de chaque vérification de l'alphabet pour voir si la chaîne précédente se termine par le même alphabet (pourquoi?-exercice)
public static void main(String[] args) {
for (String str : permStr("ABBB")){
System.out.println(str);
}
}
static Vector<String> permStr(String str){
if (str.length() == 1){
Vector<String> ret = new Vector<String>();
ret.add(str);
return ret;
}
char start = str.charAt(0);
Vector<String> endStrs = permStr(str.substring(1));
Vector<String> newEndStrs = new Vector<String>();
for (String endStr : endStrs){
for (int j = 0; j <= endStr.length(); j++){
if (endStr.substring(0, j).endsWith(String.valueOf(start)))
break;
newEndStrs.add(endStr.substring(0, j) + String.valueOf(start) + endStr.substring(j));
}
}
return newEndStrs;
}
Imprime toutes les permutations sans doublons
Réponse Ruby qui fonctionne :
class String
def each_char_with_index
0.upto(size - 1) do |index|
yield(self[index..index], index)
end
end
def remove_char_at(index)
return self[1..-1] if index == 0
self[0..(index-1)] + self[(index+1)..-1]
end
end
def permute(str, prefix = '')
if str.size == 0
puts prefix
return
end
str.each_char_with_index do |char, index|
permute(str.remove_char_at(index), prefix + char)
end
end
# example
# permute("abc")
Solution récursive en C++
int main (int argc, char * const argv[]) {
string s = "sarp";
bool used [4];
permute(0, "", used, s);
}
void permute(int level, string permuted, bool used [], string &original) {
int length = original.length();
if(level == length) { // permutation complete, display
cout << permuted << endl;
} else {
for(int i=0; i<length; i++) { // try to add an unused character
if(!used[i]) {
used[i] = true;
permute(level+1, original[i] + permuted, used, original); // find the permutations starting with this string
used[i] = false;
}
}
}
La récursion Java suivante imprime toutes les permutations d'une chaîne donnée :
//call it as permut("",str);
public void permut(String str1,String str2){
if(str2.length() != 0){
char ch = str2.charAt(0);
for(int i = 0; i <= str1.length();i++)
permut(str1.substring(0,i) + ch + str1.substring(i,str1.length()),
str2.substring(1,str2.length()));
}else{
System.out.println(str1);
}
}
Voici la version mise à jour de la méthode "permut" ci-dessus qui fait n !(n factoriel) appels moins récursifs par rapport à la méthode ci-dessus
//call it as permut("",str);
public void permut(String str1,String str2){
if(str2.length() > 1){
char ch = str2.charAt(0);
for(int i = 0; i <= str1.length();i++)
permut(str1.substring(0,i) + ch + str1.substring(i,str1.length()),
str2.substring(1,str2.length()));
}else{
char ch = str2.charAt(0);
for(int i = 0; i <= str1.length();i++)
System.out.println(str1.substring(0,i) + ch + str1.substring(i,str1.length()),
str2.substring(1,str2.length()));
}
}
import java.util.*;
public class all_subsets {
public static void main(String[] args) {
String a = "abcd";
for(String s: all_perm(a)) {
System.out.println(s);
}
}
public static Set<String> concat(String c, Set<String> lst) {
HashSet<String> ret_set = new HashSet<String>();
for(String s: lst) {
ret_set.add(c+s);
}
return ret_set;
}
public static HashSet<String> all_perm(String a) {
HashSet<String> set = new HashSet<String>();
if(a.length() == 1) {
set.add(a);
} else {
for(int i=0; i<a.length(); i++) {
set.addAll(concat(a.charAt(i)+"", all_perm(a.substring(0, i)+a.substring(i+1, a.length()))));
}
}
return set;
}
}
Voici une version non récursive que j'ai imaginée, en javascript.Il n'est pas basé sur celui non récursif de Knuth ci-dessus, bien qu'il présente certaines similitudes dans l'échange d'éléments.J'ai vérifié son exactitude pour les tableaux d'entrée comportant jusqu'à 8 éléments.
Une optimisation rapide serait de pré-voler le out tableau et éviter push().
L'idée de base est la suivante :
Étant donné un seul tableau source, générez un premier nouvel ensemble de tableaux qui échangent tour à tour le premier élément avec chaque élément suivant, laissant à chaque fois les autres éléments tranquilles.par exemple:étant donné 1234, générer 1234, 2134, 3214, 4231.
Utilisez chaque tableau de la passe précédente comme graine pour une nouvelle passe, mais au lieu d'échanger le premier élément, échangez le deuxième élément avec chaque élément suivant.De plus, cette fois, n’incluez pas le tableau d’origine dans la sortie.
Répétez l'étape 2 jusqu'à ce que vous ayez terminé.
Voici l'exemple de code :
function oxe_perm(src, depth, index)
{
var perm = src.slice(); // duplicates src.
perm = perm.split("");
perm[depth] = src[index];
perm[index] = src[depth];
perm = perm.join("");
return perm;
}
function oxe_permutations(src)
{
out = new Array();
out.push(src);
for (depth = 0; depth < src.length; depth++) {
var numInPreviousPass = out.length;
for (var m = 0; m < numInPreviousPass; ++m) {
for (var n = depth + 1; n < src.length; ++n) {
out.push(oxe_perm(out[m], depth, n));
}
}
}
return out;
}
Je ne sais pas pourquoi vous voudriez faire cela en premier lieu.L'ensemble résultant pour toutes les valeurs modérément grandes de x et y sera énorme et augmentera de façon exponentielle à mesure que x et/ou y grandissent.
Disons que votre ensemble de caractères possibles est constitué des 26 lettres minuscules de l'alphabet et que vous demandez à votre application de générer toutes les permutations où la longueur = 5.En supposant que vous ne manquiez pas de mémoire, vous obtiendrez 11 881 376 (c'est-à-dire26 à la puissance 5) cordes en arrière.Augmentez cette longueur jusqu'à 6 et vous obtiendrez 308 915 776 chaînes.Ces chiffres deviennent très rapidement extrêmement élevés.
Voici une solution que j'ai mise en place en Java.Vous devrez fournir deux arguments d'exécution (correspondant à x et y).Amusez-vous.
public class GeneratePermutations {
public static void main(String[] args) {
int lower = Integer.parseInt(args[0]);
int upper = Integer.parseInt(args[1]);
if (upper < lower || upper == 0 || lower == 0) {
System.exit(0);
}
for (int length = lower; length <= upper; length++) {
generate(length, "");
}
}
private static void generate(int length, String partial) {
if (length <= 0) {
System.out.println(partial);
} else {
for (char c = 'a'; c <= 'z'; c++) {
generate(length - 1, partial + c);
}
}
}
}
J’en avais besoin aujourd’hui, et bien que les réponses déjà données m’aient orienté dans la bonne direction, elles n’étaient pas tout à fait ce que je voulais.
Voici une implémentation utilisant la méthode Heap.La longueur du tableau doit être d'au moins 3 et, pour des raisons pratiques, ne pas dépasser 10 environ, en fonction de ce que vous voulez faire, de votre patience et de la vitesse d'horloge.
Avant d'entrer dans votre boucle, initialisez Perm(1 To N) avec la première permutation, Stack(3 To N) avec des zéros*, et Level avec 2**.A la fin de l'appel en boucle NextPerm, qui retournera false lorsque nous aurons terminé.
* VB le fera pour vous.
** Vous pouvez modifier un peu NextPerm pour rendre cela inutile, mais c'est plus clair comme ça.
Option Explicit
Function NextPerm(Perm() As Long, Stack() As Long, Level As Long) As Boolean
Dim N As Long
If Level = 2 Then
Swap Perm(1), Perm(2)
Level = 3
Else
While Stack(Level) = Level - 1
Stack(Level) = 0
If Level = UBound(Stack) Then Exit Function
Level = Level + 1
Wend
Stack(Level) = Stack(Level) + 1
If Level And 1 Then N = 1 Else N = Stack(Level)
Swap Perm(N), Perm(Level)
Level = 2
End If
NextPerm = True
End Function
Sub Swap(A As Long, B As Long)
A = A Xor B
B = A Xor B
A = A Xor B
End Sub
'This is just for testing.
Private Sub Form_Paint()
Const Max = 8
Dim A(1 To Max) As Long, I As Long
Dim S(3 To Max) As Long, J As Long
Dim Test As New Collection, T As String
For I = 1 To UBound(A)
A(I) = I
Next
Cls
ScaleLeft = 0
J = 2
Do
If CurrentY + TextHeight("0") > ScaleHeight Then
ScaleLeft = ScaleLeft - TextWidth(" 0 ") * (UBound(A) + 1)
CurrentY = 0
CurrentX = 0
End If
T = vbNullString
For I = 1 To UBound(A)
Print A(I);
T = T & Hex(A(I))
Next
Print
Test.Add Null, T
Loop While NextPerm(A, S, J)
J = 1
For I = 2 To UBound(A)
J = J * I
Next
If J <> Test.Count Then Stop
End Sub
D'autres méthodes sont décrites par divers auteurs.Knuth en décrit deux, l'une donne l'ordre lexical, mais est complexe et lente, l'autre est connue comme la méthode des changements simples.Jie Gao et Dianjun Wang ont également écrit un article intéressant.
En rubis :
str = "a"
100_000_000.times {puts str.next!}
C'est assez rapide, mais ça va prendre du temps =).Bien sûr, vous pouvez commencer par « aaaaaaaa » si les chaînes courtes ne vous intéressent pas.
J'ai peut-être mal interprété la vraie question - dans l'un des articles, il semblait que vous aviez juste besoin d'une bibliothèque de chaînes bruteforce, mais dans la question principale, il semble que vous deviez permuter une chaîne particulière.
Votre problème ressemble un peu à celui-ci : http://beust.com/weblog/archives/000491.html (listez tous les entiers dans lesquels aucun des chiffres ne se répète, ce qui a permis de le résoudre dans de nombreux langages, le gars d'ocaml utilisant des permutations et un gars de Java utilisant encore une autre solution).
Ce code en python, lorsqu'il est appelé avec allowed_characters mis à [0,1] et 4 caractères maximum, généreraient 2 ^ 4 résultats :
['0000', '0001', '0010', '0011', '0100', '0101', '0110', '0111', '1000', '1001', '1010', '1011', '1100', '1101', '1110', '1111']
def generate_permutations(chars = 4) :
#modify if in need!
allowed_chars = [
'0',
'1',
]
status = []
for tmp in range(chars) :
status.append(0)
last_char = len(allowed_chars)
rows = []
for x in xrange(last_char ** chars) :
rows.append("")
for y in range(chars - 1 , -1, -1) :
key = status[y]
rows[x] = allowed_chars[key] + rows[x]
for pos in range(chars - 1, -1, -1) :
if(status[pos] == last_char - 1) :
status[pos] = 0
else :
status[pos] += 1
break;
return rows
import sys
print generate_permutations()
J'espère que cela vous sera utile.Fonctionne avec n'importe quel caractère, pas seulement avec des chiffres
Voici un lien qui décrit comment imprimer les permutations d'une chaîne.http://nipun-linuxtips.blogspot.in/2012/11/print-all-permutations-of-characters-in.html
Bien que cela ne réponde pas exactement à votre question, voici une façon de générer chaque permutation des lettres à partir d'un certain nombre de chaînes de même longueur :Par exemple, si vos mots étaient « café », « joomla » et « moodle », vous pouvez vous attendre à des résultats comme « coodle », « joodee », « joffle », etc.
Fondamentalement, le nombre de combinaisons est le (nombre de mots) à la puissance (nombre de lettres par mot).Alors, choisissez un nombre aléatoire entre 0 et le nombre de combinaisons - 1, convertissez ce nombre en base (nombre de mots), puis utilisez chaque chiffre de ce nombre comme indicateur pour quel mot prendre la lettre suivante.
par exemple:dans l'exemple ci-dessus.3 mots, 6 lettres = 729 combinaisons.Choisissez un nombre aléatoire :465.Convertir en base 3 :122020.Prenez la première lettre du mot 1, la 2ème du mot 2, la 3ème du mot 2, la 4ème du mot 0...et tu obtiens..."joofle".
Si vous voulez toutes les permutations, faites simplement une boucle de 0 à 728.Bien sûr, si vous choisissez simplement une valeur aléatoire, plus simple Une manière moins déroutante serait de parcourir les lettres.Cette méthode vous permet d'éviter la récursion, si vous souhaitez toutes les permutations, et elle vous donne également l'impression que vous connaissez les mathématiques.(tm)!
Si le nombre de combinaisons est excessif, vous pouvez le diviser en une série de mots plus petits et les concaténer à la fin.
c# itératif :
public List<string> Permutations(char[] chars)
{
List<string> words = new List<string>();
words.Add(chars[0].ToString());
for (int i = 1; i < chars.Length; ++i)
{
int currLen = words.Count;
for (int j = 0; j < currLen; ++j)
{
var w = words[j];
for (int k = 0; k <= w.Length; ++k)
{
var nstr = w.Insert(k, chars[i].ToString());
if (k == 0)
words[j] = nstr;
else
words.Add(nstr);
}
}
}
return words;
}
Il existe une implémentation Java itérative dans Peu communsMaths (fonctionne pour une liste d'objets):
/**
* Generate the indices into the elements array for the next permutation. The
* algorithm is from Kenneth H. Rosen, Discrete Mathematics and its
* Applications, 2nd edition (NY: McGraw-Hill, 1991), p. 284)
*/
private void generateNextPermutationIndices()
{
if (remainingPermutations == 0)
{
throw new IllegalStateException("There are no permutations " +
"remaining. Generator must be reset to continue using.");
}
else if (remainingPermutations < totalPermutations)
{
// Find largest index j with
// permutationIndices[j] < permutationIndices[j + 1]
int j = permutationIndices.length - 2;
while (permutationIndices[j] > permutationIndices[j + 1])
{
j--;
}
// Find index k such that permutationIndices[k] is smallest integer
// greater than permutationIndices[j] to the right
// of permutationIndices[j].
int k = permutationIndices.length - 1;
while (permutationIndices[j] > permutationIndices[k])
{
k--;
}
// Interchange permutation indices.
int temp = permutationIndices[k];
permutationIndices[k] = permutationIndices[j];
permutationIndices[j] = temp;
// Put tail end of permutation after jth position in increasing order.
int r = permutationIndices.length - 1;
int s = j + 1;
while (r > s)
{
temp = permutationIndices[s];
permutationIndices[s] = permutationIndices[r];
permutationIndices[r] = temp;
r--;
s++;
}
}
--remainingPermutations;
}
/**
* Generate the next permutation and return a list containing
* the elements in the appropriate order. This overloaded method
* allows the caller to provide a list that will be used and returned.
* The purpose of this is to improve performance when iterating over
* permutations. If the {@link #nextPermutationAsList()} method is
* used it will create a new list every time. When iterating over
* permutations this will result in lots of short-lived objects that
* have to be garbage collected. This method allows a single list
* instance to be reused in such circumstances.
* @param destination Provides a list to use to create the
* permutation. This is the list that will be returned, once
* it has been filled with the elements in the appropriate order.
* @return The next permutation as a list.
*/
public List<T> nextPermutationAsList(List<T> destination)
{
generateNextPermutationIndices();
// Generate actual permutation.
destination.clear();
for (int i : permutationIndices)
{
destination.add(elements[i]);
}
return destination;
}
def gen( x,y,list): #to generate all strings inserting y at different positions
list = []
list.append( y+x )
for i in range( len(x) ):
list.append( func(x,0,i) + y + func(x,i+1,len(x)-1) )
return list
def func( x,i,j ): #returns x[i..j]
z = ''
for i in range(i,j+1):
z = z+x[i]
return z
def perm( x , length , list ): #perm function
if length == 1 : # base case
list.append( x[len(x)-1] )
return list
else:
lists = perm( x , length-1 ,list )
lists_temp = lists #temporarily storing the list
lists = []
for i in range( len(lists_temp) ) :
list_temp = gen(lists_temp[i],x[length-2],lists)
lists += list_temp
return lists
def permutation(str)
posibilities = []
str.split('').each do |char|
if posibilities.size == 0
posibilities[0] = char.downcase
posibilities[1] = char.upcase
else
posibilities_count = posibilities.length
posibilities = posibilities + posibilities
posibilities_count.times do |i|
posibilities[i] += char.downcase
posibilities[i+posibilities_count] += char.upcase
end
end
end
posibilities
end
Voici mon point de vue sur une version non récursive
La solution pythonique :
from itertools import permutations
s = 'ABCDEF'
p = [''.join(x) for x in permutations(s)]
