Сгенерировать список всех возможных перестановок строки

Есть несколько способов сделать это. Общие методы используют рекурсию, мемоизацию или динамическое программирование. Основная идея состоит в том, что вы создаете список всех строк длиной 1, а затем на каждой итерации для всех строк, созданных на последней итерации, добавляете эту строку, сцепленную с каждым символом в строке индивидуально. (индекс переменной в приведенном ниже коде отслеживает начало последней и следующей итерации)

Какой-то псевдокод:

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)

тогда вам нужно будет удалить все строки длиной меньше x, они будут первыми (x-1) * len (originalString) записями в списке.

Я просто быстро придумал это в 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

Вы можете изучить языковой API для встроенных функций типа перестановки, и вы, возможно, сможете написать более оптимизированный код, но если числа настолько высоки, я не уверен, что есть много способов обойтись без большого количества результатов. .

В любом случае, идея кода заключается в том, чтобы начать со строки длины 0, а затем отслеживать все строки длины Z, где Z - текущий размер в итерации. Затем просмотрите каждую строку и добавьте каждый символ в каждую строку. Наконец, в конце удалите все, что было ниже порога x, и верните результат.

Я не тестировал его с потенциально бессмысленным вводом (список нулевых символов, странные значения x и y и т. д.).

Я не уверен, зачем вам вообще это нужно. Результирующий набор для любых умеренно больших значений x и y будет огромным и будет экспоненциально расти по мере увеличения x и / или y.

Допустим, ваш набор возможных символов - это 26 строчных букв алфавита, и вы просите свое приложение сгенерировать все перестановки, где длина = 5. Предполагая, что у вас не закончится память, вы получите 11 881 376 (т.е. 26 в степени из 5) струны назад. Увеличьте эту длину до 6, и вы получите обратно 308 915 776 струн. Эти цифры становятся до боли большими и очень быстро.

Вот решение, которое я собрал на Java. Вам нужно будет предоставить два аргумента времени выполнения (соответствующие x и y). Радоваться, веселиться.

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);
            }
        }
    }
}

У вас будет много струн, это точно ...

Где x и y - это то, как вы их определяете, а r - количество символов, из которых мы выбираем, - если я правильно вас понимаю. Вы обязательно должны генерировать их по мере необходимости, а не быть небрежным и, скажем, сгенерировать набор мощности, а затем отфильтровать длину строк.

Следующее определенно не лучший способ их создания, но тем не менее интересно.

Кнут (том 4, глава 2, 7.2.1.3) говорит нам, что (s, t) -комбинация эквивалентна s + 1 вещей, взятых t за раз с повторением - (s, t) -комбинация используется Knuth, равный . Мы можем выяснить это, сначала сгенерировав каждую (s, t) -комбинацию в двоичной форме (т.е. длины (s + t)) и посчитав количество нулей слева от каждой единицы.

10001000011101 -> становится перестановкой: {0, 3, 4, 4, 4, 1}

В рубине:

str = "a"
100_000_000.times {puts str.next!}

Это довольно быстро, но займет некоторое время =). Конечно, вы можете начать с «аааааааа», если короткие строки вам не интересны.

Возможно, я неверно истолковал реальный вопрос - в одном из постов это звучало так, как будто вам просто нужна библиотека строк грубой силой, но в основном вопросе это звучит так, как будто вам нужно переставить конкретную строку.

Ваша проблема в чем-то похожа на эту: http://beust.com/weblog/archives/000491.html (перечислите все целые числа, в которых ни одна из цифр не повторяется, что привело к тому, что многие языки решили ее, причем парень ocaml использовал перестановки, а какой-то парень java использовал еще одно решение) .

Это перевод Ruby-версии Майка на 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)))))

И еще одна версия, немного короче и использующая больше функций петли:

(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)))))

Хотя это не совсем ответ на ваш вопрос, вот один из способов сгенерировать каждую перестановку букв из ряда строк одинаковой длины: например, если вашими словами были «кофе», «joomla» и «moodle», вы можете ожидайте вывода типа "coodle", "joodee", "joffle" и т. д.

По сути, количество комбинаций - это (количество слов) в степени (количество букв в слове). Итак, выберите случайное число от 0 до количества комбинаций - 1, преобразуйте это число в основание (количество слов), затем используйте каждую цифру этого числа в качестве индикатора, из которого следует взять следующую букву.

например: в приведенном выше примере. 3 слова, 6 букв = 729 комбинаций. Выберите случайное число: 465. Преобразуйте в основание 3: 122020. Возьмите первую букву из слова 1, 2-ю из слова 2, 3-ю из слова 2, 4-ю из слова 0 ... и вы получите ... "joofle".

Если вам нужны все перестановки, просто выполните цикл от 0 до 728. Конечно, если вы просто выбираете одно случайное значение, гораздо менее запутанным способом проще будет цикл по буквам. Этот метод позволяет избежать рекурсии, если вам нужны все перестановки, плюс он заставляет вас выглядеть так, как будто вы знаете Maths^(tm)!

Если количество комбинаций слишком велико, вы можете разбить его на серию более мелких слов и соединить их в конце.

Рекурсивное решение в 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;
            }
        }
}

Вот простое слово C# рекурсивное решение:

Метод:

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;
        }

Звонок:

string[] letters = new string[]{"a","b","c"};
ArrayList words = CalculateWordPermutations(letters, new ArrayList(), 0);

Вы можете посмотреть «Эффективное перечисление подмножеств набора», который описывает алгоритм для выполнения части того, что вы хотите - быстро сгенерировать все подмножества из N символов от длины x до y. Он содержит реализацию на C.

Для каждого подмножества вам все равно придется сгенерировать все перестановки. Например, если вам нужно 3 символа из «abcde», этот алгоритм даст вам «abc», «abd», «abe» ... но вам придется переставить каждый из них, чтобы получить «acb», «bac», «bca» и т. д.

В Perl, если вы хотите ограничиться строчными буквами, вы можете сделать это:

my @result = ("a" .. "zzzz");

Это дает все возможные строки от 1 до 4 символов с использованием символов нижнего регистра. Для прописных букв измените "a" на "A" и "zzzz" на "ZZZZ".

Для смешанного случая это становится намного сложнее и, вероятно, не выполнимо с одним из таких встроенных операторов Perl.

Некоторый рабочий код Java на основе Ответ Сарпа:

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);
    }
}

Вот простое решение на C#.

Он генерирует только различные перестановки данной строки.

    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;
        }
    }

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;
    }
}

Нерекурсивное решение по примеру Knuth, 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)

... а вот версия 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;
}

permute (ABC) -> A.perm(BC) -> A.perm[B.perm(C)] -> A.perm[(*BC), (CB*)] -> [(*ABC), (BAC), (BCA*), (*ACB), (CAB), (CBA*)] To remove duplicates when inserting each alphabet check to see if previous string ends with the same alphabet (why? -exercise)

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;
}

Печатает все перестановки без дубликатов

Этот код на python при вызове с allowed_characters, установленным на [0,1] и максимум 4 символа, сгенерирует 2 ^ 4 результата:

['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()

Надеюсь, это будет вам полезно. Работает с любым символом, а не только с цифрами

Вот нерекурсивная версия, которую я придумал, на javascript. Он не основан на нерекурсивном методе Кнута, приведенном выше, хотя имеет некоторые сходства в замене элементов. Я проверил его правильность для входных массивов до 8 элементов.

Быстрая оптимизация - это предварительный запуск массива out и отказ от push().

Основная идея:

1. Учитывая единственный исходный массив, сгенерируйте первый новый набор массивов, которые меняют местами первый элемент с каждым последующим элементом по очереди, каждый раз оставляя другие элементы без изменений. например: задано 1234, сгенерировать 1234, 2134, 3214, 4231.

2. Используйте каждый массив из предыдущего прохода в качестве начального числа для нового прохода, но вместо того, чтобы менять местами первый элемент, поменяйте местами второй элемент с каждым последующим элементом. Кроме того, на этот раз не включайте исходный массив в вывод.

3. Повторяйте шаг 2, пока не будете готовы.

Вот пример кода:

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;
}

Мне это было нужно сегодня, и хотя уже полученные ответы указали мне правильное направление, они были не совсем тем, что я хотел.

Вот реализация с использованием метода Heap. Длина массива должна быть не менее 3, а из практических соображений - не более 10 или около того, в зависимости от того, что вы хотите сделать, терпения и тактовой частоты.

Перед входом в цикл инициализируйте Perm(1 To N) с первой перестановкой, Stack(3 To N) с нулями * и Level с 2 **. В конце цикла вызовите NextPerm, который вернет false, когда мы закончим.

* VB сделает это за вас.

** Вы можете немного изменить NextPerm, чтобы в этом не было необходимости, но так нагляднее.

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

Остальные методы описаны разными авторами. Кнут описывает два, один дает лексический порядок, но является сложным и медленным, другой известен как метод простых изменений. Цзе Гао и Дяньцзюнь Ван также написали интересную статью.

Лучше использовать поиск с возвратом

#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;
}

Рубиновый ответ, который работает:

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")

C# итеративно:

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;
    }

Следующая рекурсия Java печатает все перестановки данной строки:

//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);
    }
}

Ниже приведена обновленная версия вышеупомянутого метода "перестановки", которая делает n! (n факториалов) менее рекурсивные вызовы по сравнению с вышеуказанным методом

//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()));
   }
}

Рекурсивное решение на питоне. Преимущество этого кода в том, что он экспортирует словарь с ключами в виде строк и всеми возможными перестановками в виде значений. Включены все возможные длины строк, так что фактически вы создаете надмножество.

Если вам нужны только окончательные перестановки, вы можете удалить другие ключи из словаря.

В этом коде словарь перестановок является глобальным.

В базовом случае я сохраняю значение как обе возможности в списке. perms['ab'] = ['ab','ba'].

Для большей длины строки функция относится к более низкой длине строки и включает ранее вычисленные перестановки.

Функция выполняет две вещи:

• вызывает себя с меньшей строкой
• возвращает список перестановок конкретной строки, если она уже доступна. Если они возвращены самому себе, они будут использоваться для добавления к персонажу и создания новых перестановок.

Дорого по памяти.

perms = {}
def perm(input_string):
    global perms
    if input_string in perms:
        return perms[input_string] # This will send a list of all permutations
    elif len(input_string) == 2:
        perms[input_string] = [input_string, input_string[-1] + input_string [-2]]
        return perms[input_string]
    else:
        perms[input_string] = []
        for index in range(0, len(input_string)):
            new_string = input_string[0:index] + input_string[index +1:]
            perm(new_string)
            for entries in perms[new_string]:
                perms[input_string].append(input_string[index] + entries)
    return perms[input_string]

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

Рекурсивное решение с драйверным методом main().

public class AllPermutationsOfString {
public static void stringPermutations(String newstring, String remaining) {
    if (remaining.length()==0)
        System.out.println(newstring);

    for(int i=0; i<remaining.length(); i++) {
        String newRemaining = remaining.replaceFirst(remaining.charAt(i)+"", "");
        stringPermutations(newstring+remaining.charAt(i), newRemaining);
    }
}

public static void main(String[] args) {
    String string = "abc";
    AllPermutationsOfString.stringPermutations("", string); 
}

}

Здесь есть много хороших ответов. Я также предлагаю очень простое рекурсивное решение на 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;
    });
}

Примечание: строки с повторяющимися символами не производят уникальных перестановок.

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

Вот мой взгляд на нерекурсивную версию

Вот ссылка, которая описывает, как распечатать перестановки строки. http://nipun-linuxtips.blogspot.in/2012/11/print-all-permutations-of-characters-in.html

Питонический раствор:

from itertools import permutations
s = 'ABCDEF'
p = [''.join(x) for x in permutations(s)]

Вот элегантное нерекурсивное решение O (n!):

public static StringBuilder[] permutations(String s) {
        if (s.length() == 0)
            return null;
        int length = fact(s.length());
        StringBuilder[] sb = new StringBuilder[length];
        for (int i = 0; i < length; i++) {
            sb[i] = new StringBuilder();
        }
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            int times = length / (i + 1);
            for (int j = 0; j < times; j++) {
                for (int k = 0; k < length / times; k++) {
                    sb[j * length / times + k].insert(k, ch);
                }
            }
        }
        return sb;
    }

код, написанный для языка java:

пакет namo.algorithms;

import java.util.Scanner;

public class Permutations {

public static int totalPermutationsCount = 0;
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        System.out.println("input string : ");
        String inputString = sc.nextLine();
        System.out.println("given input String ==> "+inputString+ " :: length is = "+inputString.length());
        findPermuationsOfString(-1, inputString);
        System.out.println("**************************************");
        System.out.println("total permutation strings ==> "+totalPermutationsCount);
    }


    public  static void findPermuationsOfString(int fixedIndex, String inputString) {
        int currentIndex = fixedIndex +1;

        for (int i = currentIndex; i < inputString.length(); i++) {
            //swap elements and call the findPermuationsOfString()

            char[] carr = inputString.toCharArray();
            char tmp = carr[currentIndex];
            carr[currentIndex] = carr[i];
            carr[i] = tmp;
            inputString =  new String(carr);

            //System.out.println("chat At : current String ==> "+inputString.charAt(currentIndex));
            if (currentIndex == inputString.length()-1) {
                totalPermutationsCount++;
                System.out.println("permuation string ==> "+inputString);
            } else {
                //System.out.println("in else block>>>>");
                findPermuationsOfString(currentIndex, inputString);
                 char[] rarr = inputString.toCharArray();
                    char rtmp = carr[i];
                    carr[i] = carr[currentIndex];
                    carr[currentIndex] = rtmp;
                    inputString =  new String(carr);
            }
        }
    }

}

Возможные перестановки строк можно вычислить с помощью рекурсивной функции. Ниже приводится одно из возможных решений.

public static String insertCharAt(String s, int index, char c) {
        StringBuffer sb = new StringBuffer(s);
        StringBuffer sbb = sb.insert(index, c);
        return sbb.toString();
}

public static ArrayList<String> getPerm(String s, int index) {
        ArrayList<String> perm = new ArrayList<String>();

        if (index == s.length()-1) {
            perm.add(String.valueOf(s.charAt(index)));
            return perm;
        }

        ArrayList<String> p = getPerm(s, index+1);
        char c = s.charAt(index);

        for(String pp : p) {
            for (int idx=0; idx<pp.length()+1; idx++) {
                String ss = insertCharAt(pp, idx, c);
                perm.add(ss);
            }
        }

        return perm;    
}

public static void testGetPerm(String s) {
        ArrayList<String> perm = getPerm(s,0);
        System.out.println(s+" --> total permutation are :: "+perm.size());
        System.out.println(perm.toString());
}

Рекурсивный подход

func StringPermutations(inputStr string) (permutations []string) {
    for i := 0; i < len(inputStr); i++ {
        inputStr = inputStr[1:] + inputStr[0:1]
        if len(inputStr) <= 2 {
            permutations = append(permutations, inputStr)
            continue
        }
        leftPermutations := StringPermutations(inputStr[0 : len(inputStr)-1])
        for _, leftPermutation := range leftPermutations {
            permutations = append(permutations, leftPermutation+inputStr[len(inputStr)-1:])
        }
    }
    return
}

Во многих предыдущих ответах использовался возврат с возвратом. Это асимптотически оптимальный способ O (n * n!) генерации перестановок после начальной сортировки

class Permutation {

    /* runtime -O(n) for generating nextPermutaion
     * and O(n*n!) for generating all n! permutations with increasing sorted array as start
     * return true, if there exists next lexicographical sequence
     * e.g [a,b,c],3-> true, modifies array to [a,c,b]
     * e.g [c,b,a],3-> false, as it is largest lexicographic possible */
    public static boolean nextPermutation(char[] seq, int len) {
        // 1
        if (len <= 1)
            return false;// no more perm
        // 2: Find last j such that seq[j] <= seq[j+1]. Terminate if no such j exists
        int j = len - 2;
        while (j >= 0 && seq[j] >= seq[j + 1]) {
            --j;
        }
        if (j == -1)
            return false;// no more perm
        // 3: Find last l such that seq[j] <= seq[l], then exchange elements j and l
        int l = len - 1;
        while (seq[j] >= seq[l]) {
            --l;
        }
        swap(seq, j, l);
        // 4: Reverse elements j+1 ... count-1:
        reverseSubArray(seq, j + 1, len - 1);
        // return seq, add store next perm

        return true;
    }
    private static void swap(char[] a, int i, int j) {
        char temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    private static void reverseSubArray(char[] a, int lo, int hi) {
        while (lo < hi) {
            swap(a, lo, hi);
            ++lo;
            --hi;
        }
    }
    public static void main(String[] args) {
        String str = "abcdefg";
        char[] array = str.toCharArray();
        Arrays.sort(array);
        int cnt=0;
        do {
            System.out.println(new String(array));
            cnt++;
        }while(nextPermutation(array, array.length));
        System.out.println(cnt);//5040=7!
    }
    //if we use "bab"-> "abb", "bab", "bba", 3(#permutations)
}