Gere uma lista de todas as permutações possíveis de uma string
-
08-06-2019 - |
Pergunta
Como eu geraria uma lista de todas as permutações possíveis de uma string entre caracteres x e y de comprimento, contendo uma lista variável de caracteres.
Qualquer linguagem funcionaria, mas deveria ser portátil.
Solução
Existem várias maneiras de fazer isso.Os métodos comuns usam recursão, memorização ou programação dinâmica.A ideia básica é que você produza uma lista de todas as strings de comprimento 1 e, em cada iteração, para todas as strings produzidas na última iteração, adicione essa string concatenada com cada caractere da string individualmente.(o índice variável no código abaixo acompanha o início da última e da próxima iteração)
Algum pseudocódigo:
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)
você precisará remover todas as strings com comprimento menor que x, elas serão as primeiras (x-1) * len(originalString) entradas na lista.
Outras dicas
É melhor usar retrocesso
#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;
}
Você vai conseguir muitas cordas, isso é certo...
\sum_{i=x}^y{\frac{r!}{{(ri)}!}} http://www.codecogs.com/eq.latex?%5Csum_%7Bi=x%7D%5Ey% 20%7B%20%5Cfrac%7Br!%7D%7B%7B(ri)%7D!%7D%20%7D
Onde xey é como você os define e r é o número de caracteres que estamos selecionando - se estou entendendo corretamente.Definitivamente, você deve gerá-los conforme necessário e não ser desleixado e dizer, gerar um powerset e depois filtrar o comprimento das strings.
O seguinte definitivamente não é a melhor maneira de gerá-los, mas é um aparte interessante, mesmo assim.
Knuth (volume 4, fascículo 2, 7.2.1.3) nos diz que a combinação (s,t) é equivalente a s+1 coisas tomadas t de cada vez com repetição - uma combinação (s,t) é a notação usada por Knuth que é igual a {t \choose {s+t} http://www.codecogs.com/eq.latex?%7Bt%20%5Cchoose%20%7Bs+t%7D%7D.Podemos descobrir isso gerando primeiro cada combinação (s,t) na forma binária (portanto, de comprimento (s+t)) e contando o número de 0s à esquerda de cada 1.
10001000011101 --> torna-se a permutação:{0, 3, 4, 4, 4, 1}
Solução não recursiva de acordo com Knuth, exemplo 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)
Você pode olhar para "Enumerando eficientemente os subconjuntos de um conjunto", que descreve um algoritmo para fazer parte do que você deseja - gerar rapidamente todos os subconjuntos de N caracteres de comprimento x a y.Ele contém uma implementação em C.
Para cada subconjunto, você ainda teria que gerar todas as permutações.Por exemplo, se você quisesse 3 caracteres de "abcde", este algoritmo lhe daria "abc","abd", "abe"...mas você teria que permutar cada um para obter "acb", "bac", "bca", etc.
Algum código Java funcional baseado em A resposta 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);
}
}
Aqui está uma solução simples em C#.
Ele gera apenas as permutações distintas de uma determinada string.
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;
}
}
Há muitas boas respostas aqui.Também sugiro uma solução recursiva muito simples em 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;
});
}
Observação:strings com caracteres repetidos não produzirão permutações únicas.
Acabei de preparar isso rapidamente em 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
Você pode pesquisar na API da linguagem para funções de tipo de permutação integradas e poderá escrever um código mais otimizado, mas se os números forem tão altos, não tenho certeza se há uma maneira de evitar muitos resultados .
De qualquer forma, a ideia por trás do código é começar com uma string de comprimento 0 e, em seguida, acompanhar todas as strings de comprimento Z, onde Z é o tamanho atual na iteração.Em seguida, percorra cada string e anexe cada caractere a cada string.Finalmente, no final, remova qualquer um que esteja abaixo do limite x e retorne o resultado.
Não testei com entradas potencialmente sem sentido (lista de caracteres nulos, valores estranhos de xey, etc).
Esta é uma tradução da versão Ruby de Mike, para 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)))))
E outra versão, um pouco mais curta e com mais recursos de loop:
(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)))))
Aqui está uma solução recursiva simples em C#:
Método:
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;
}
Chamando:
string[] letters = new string[]{"a","b","c"};
ArrayList words = CalculateWordPermutations(letters, new ArrayList(), 0);
Em Perl, se você quiser se restringir ao alfabeto minúsculo, você pode fazer o seguinte:
my @result = ("a" .. "zzzz");
Isso fornece todas as strings possíveis entre 1 e 4 caracteres usando caracteres minúsculos.Para letras maiúsculas, altere "a"
para "A"
e "zzzz"
para "ZZZZ"
.
Para casos mistos, fica muito mais difícil e provavelmente não é possível com um dos operadores integrados do Perl como esse.
...e aqui está a versão 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;
}
permutar (ABC) -> A.perm(BC) -> A.perm[B.perm(C)] -> A.perm[(*BC), (CB*)] -> [(*ABC), (BAC), (BCA*), (*ACB), (CAB), (CBA*)] Para remover duplicatas ao inserir cada verificação do alfabeto para ver se a string anterior termina com o mesmo alfabeto (por quê?-exercício)
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 todas as permutações sem duplicatas
Resposta Ruby que funciona:
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")
Solução recursiva em 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;
}
}
}
A seguinte recursão Java imprime todas as permutações de uma determinada string:
//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);
}
}
A seguir está a versão atualizada do método "permut" acima, que torna n!(n fatorial) menos chamadas recursivas em comparação com o método acima
//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;
}
}
Aqui está uma versão não recursiva que criei, em javascript.Não é baseado no método não recursivo de Knuth acima, embora tenha algumas semelhanças na troca de elementos.Verifiquei sua correção para matrizes de entrada de até 8 elementos.
Uma otimização rápida seria pré-voar o out
matriz e evitando push()
.
A ideia básica é:
Dado um único array de origem, gere um primeiro novo conjunto de arrays que trocam o primeiro elemento com cada elemento subsequente, sempre deixando os outros elementos imperturbados.por exemplo:dado 1234, gere 1234, 2134, 3214, 4231.
Use cada matriz do passe anterior como semente para um novo passe, mas, em vez de trocar o primeiro elemento, troque o segundo elemento com cada elemento subsequente.Além disso, desta vez, não inclua o array original na saída.
Repita o passo 2 até terminar.
Aqui está o exemplo de código:
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;
}
Não sei por que você gostaria de fazer isso em primeiro lugar.O conjunto resultante para quaisquer valores moderadamente grandes de x e y será enorme e crescerá exponencialmente à medida que x e/ou y aumentam.
Digamos que seu conjunto de caracteres possíveis sejam as 26 letras minúsculas do alfabeto e você peça ao seu aplicativo para gerar todas as permutações onde comprimento = 5.Supondo que você não fique sem memória, você obterá 11.881.376 (ou seja,26 elevado a 5) cordas para trás.Aumente esse comprimento para 6 e você receberá 308.915.776 cordas de volta.Esses números ficam dolorosamente grandes muito rapidamente.
Aqui está uma solução que montei em Java.Você precisará fornecer dois argumentos de tempo de execução (correspondentes a x e y).Divirta-se.
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);
}
}
}
}
Eu precisava disso hoje e, embora as respostas já dadas me apontassem na direção certa, não eram exatamente o que eu queria.
Aqui está uma implementação usando o método Heap.O comprimento do array deve ser de pelo menos 3 e por considerações práticas não ser maior que 10 ou mais, dependendo do que você deseja fazer, paciência e velocidade do clock.
Antes de entrar no seu loop, inicialize Perm(1 To N)
com a primeira permutação, Stack(3 To N)
com zeros*, e Level
com 2
**.No final da chamada de loop NextPerm
, que retornará false quando terminarmos.
* VB fará isso por você.
** Você pode alterar um pouco o NextPerm para tornar isso desnecessário, mas fica mais claro assim.
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
Outros métodos são descritos por vários autores.Knuth descreve dois, um fornece ordem lexical, mas é complexo e lento, o outro é conhecido como método de mudanças simples.Jie Gao e Dianjun Wang também escreveram um artigo interessante.
Em rubi:
str = "a"
100_000_000.times {puts str.next!}
É bem rápido, mas vai demorar um pouco =).Claro, você pode começar com "aaaaaaaa" se as sequências curtas não forem interessantes para você.
Eu posso ter interpretado mal a questão real - em uma das postagens parecia que você só precisava de uma biblioteca de strings de força bruta, mas na questão principal parece que você precisa permutar uma string específica.
Seu problema é um pouco semelhante a este: http://beust.com/weblog/archives/000491.html (liste todos os números inteiros em que nenhum dos dígitos se repete, o que resultou em muitas linguagens resolvendo-o, com o cara ocaml usando permutações e algum cara java usando outra solução).
Este código em python, quando chamado com allowed_characters
definido como [0,1]
e 4 caracteres no máximo, geraria 2 ^ 4 resultados:
['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()
Espero que isso seja útil para você.Funciona com qualquer caractere, não apenas números
Aqui está um link que descreve como imprimir permutações de uma string.http://nipun-linuxtips.blogspot.in/2012/11/print-all-permutations-of-characters-in.html
Embora isso não responda exatamente à sua pergunta, aqui está uma maneira de gerar todas as permutações das letras a partir de várias strings do mesmo comprimento:por exemplo, se suas palavras forem "café", "joomla" e "moodle", você pode esperar resultados como "coodle", "joodee", "joffle" etc.
Basicamente, o número de combinações é (número de palavras) elevado a (número de letras por palavra).Portanto, escolha um número aleatório entre 0 e o número de combinações - 1, converta esse número em base (número de palavras) e use cada dígito desse número como o indicador de qual palavra retirar a próxima letra.
por exemplo:no exemplo acima.3 palavras, 6 letras = 729 combinações.Escolha um número aleatório:465.Converta para base 3:122020.Pegue a primeira letra da palavra 1, a 2ª da palavra 2, a 3ª da palavra 2, a 4ª da palavra 0...e você consegue..."joofle".
Se você quiser todas as permutações, basta fazer um loop de 0 a 728.Claro, se você escolher apenas um valor aleatório, muito mais simples maneira menos confusa seria percorrer as letras.Este método permite evitar a recursão, caso você queira todas as permutações, além de fazer você parecer que sabe matemática(tm)!
Se o número de combinações for excessivo, você pode dividi-lo em uma série de palavras menores e concatená-las no final.
c# iterativo:
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;
}
Existe uma implementação Java iterativa em IncomunsMatemática (funciona para uma lista de objetos):
/**
* 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
Aqui está minha opinião sobre uma versão não recursiva
A solução pitônica:
from itertools import permutations
s = 'ABCDEF'
p = [''.join(x) for x in permutations(s)]