Создать список всех возможных перестановок строки
Как бы я пошел о создании списка всех возможных перестановок строки между символами x и y длиной, содержащей список переменных символов.
Любой язык будет работать, но он должен быть переносимым.
37 ответов
Есть несколько способов сделать это. Обычные методы используют рекурсию, запоминание или динамическое программирование. Основная идея состоит в том, что вы создаете список всех строк длины 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) записями в списке.
Лучше использовать возврат
#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;
}
Вы получите много строк, это точно...
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
Где x и y - это то, как вы их определяете, а r - количество символов, из которых мы выбираем - если я вас правильно понимаю. Вы должны определенно генерировать их по мере необходимости и не становиться неряшливыми, скажем, генерировать powerset, а затем фильтровать длину строк.
Следующее, безусловно, не лучший способ для их создания, но, тем не менее, это интересный аспект.
Кнут (том 4, глава 2, 7.2.1.3) говорит нам, что (s,t)-комбинация эквивалентна s+1 вещам, взятым t за один раз с повторением - (s,t)-комбинация - это обозначение, используемое Кнут, равный http://www.codecogs.com/eq.latex?%7Bt%20%5Cchoose%20%7Bs+t%7D%7D. Мы можем выяснить это, сначала сгенерировав каждую (s,t)-комбинацию в двоичной форме (так, длины (s+t)) и посчитав количество нулей слева от каждого 1.
10001000011101 -> становится перестановкой: {0, 3, 4, 4, 4, 1}
Нерекурсивное решение по примеру Кнута, 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)
Некоторый рабочий Java-код, основанный на ответе 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);
}
}
Вот простое решение в 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;
}
}
Вы можете взглянуть на " Эффективное перечисление подмножеств набора", в котором описывается алгоритм для выполнения части того, что вы хотите - быстро сгенерировать все подмножества из N символов длиной от x до y. Он содержит реализацию на C.
Для каждого подмножества вам все равно придется генерировать все перестановки. Например, если вы хотите 3 символа из "abcde", этот алгоритм выдаст вам "abc", "abd", "abe"... но вам нужно будет переставить каждый из них, чтобы получить "acb", "bac", "bca" и т. д.
Здесь много хороших ответов. Я также предлагаю очень простое рекурсивное решение в 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;
});
}
Примечание: строки с повторяющимися символами не будут давать уникальные перестановки.
Я просто быстро все это написал в 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 и т. Д.).
... а вот версия 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;
}
перестановка (ABC) -> A.perm (BC) -> A.perm [B.perm (C)] -> A.perm [(* BC), (CB *)] -> [(* ABC)), (BAC), (BCA *), (* ACB), (CAB), (CBA *)] Чтобы удалить дубликаты при вставке каждого алфавита, проверьте, заканчивается ли предыдущая строка тем же алфавитом (почему? - упражнение)
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;
}
Печатает все перестановки без дубликатов
Вот простое слово 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);
Это перевод версии Майка для 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)))))
Рекурсивное решение в 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;
}
}
}
В Perl, если вы хотите ограничиться строчными буквами алфавита, вы можете сделать это:
my @result = ("a" .. "zzzz");
Это дает все возможные строки от 1 до 4 символов, используя строчные буквы. Для заглавных букв измените "a" в "A" а также "zzzz" в "ZZZZ",
Для смешанного случая это становится намного сложнее, и, вероятно, неосуществимо с одним из встроенных операторов Perl, подобным этому.
Рубиновый ответ, который работает:
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")
Следующая рекурсия 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);
}
}
Ниже приводится обновленная версия вышеупомянутого метода "permut", который делает 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()));
}
}
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;
}
}
Вот нерекурсивная версия, которую я придумал, в javascript. Он не основан на нерекурсивном описанном выше Кнуте, хотя имеет некоторые сходства в обмене элементами. Я проверил его правильность для входных массивов до 8 элементов.
Быстрая оптимизация - это предварительная проверка out массив и избегая push(),
Основная идея:
Для одного исходного массива создайте первый новый набор массивов, которые поочередно меняют первый элемент на каждый последующий элемент, каждый раз оставляя невозмущенные другие элементы. например: дано 1234, сгенерировано 1234, 2134, 3214, 4231.
Используйте каждый массив из предыдущего прохода в качестве начального числа для нового прохода, но вместо замены первого элемента меняйте местами второй элемент с каждым последующим элементом. Кроме того, на этот раз не включайте исходный массив в вывод.
Повторите шаг 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;
}
Я не уверен, почему вы хотели бы сделать это в первую очередь. Результирующий набор для любых умеренно больших значений 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);
}
}
}
}
В рубине:
str = "a"
100_000_000.times {puts str.next!}
Это довольно быстро, но это займет некоторое время =). Конечно, вы можете начать с "aaaaaaaa", если короткие строки вам не интересны.
Хотя, возможно, я неверно истолковал реальный вопрос - в одном из постов он звучал так, как будто вам просто нужна библиотека строк bruteforce, но в основном вопросе кажется, что вам нужно переставить определенную строку.
Ваша проблема в чем-то похожа на эту: http://beust.com/weblog/archives/000491.html (перечислите все целые числа, в которых ни одна из цифр не повторяется, что привело к тому, что ее решило множество языков, с ocaml парень, использующий перестановки, и какой-то парень java, использующий еще одно решение).
Я нуждался в этом сегодня, и хотя ответы, которые уже были даны, указали мне правильное направление, они были не совсем тем, что я хотел.
Вот реализация, использующая метод Heap. Длина массива должна быть не менее 3, а по практическим соображениям - не более 10 или около того, в зависимости от того, что вы хотите сделать, терпения и тактовой частоты.
Прежде чем войти в свой цикл, инициализируйте Perm(1 To N) с первой перестановкой, Stack(3 To N) с нулями * и Level с 2**. В конце вызова цикла NextPerm, который вернет ложь, когда мы закончим.
* 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
Другие методы описаны различными авторами. Кнут описывает два, один дает лексический порядок, но сложен и медленен, другой известен как метод простых изменений. Цзе Гао и Дяньцзюнь Ван также написали интересную статью.
Вот ссылка, которая описывает, как напечатать перестановки строки. http://nipun-linuxtips.blogspot.in/2012/11/print-all-permutations-of-characters-in.html
Этот код в 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()
Надеюсь, что это полезно для вас. Работает с любым персонажем, а не только с цифрами
Во многих предыдущих ответах использовался возврат с возвратом. Это асимптотически оптимальный способ 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)
}
Рекурсивный подход
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
}
В UncommonsMaths есть итеративная реализация Java (работает со списком объектов):
/**
* 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;
}
Рекурсивное решение в Python. В этом коде хорошо то, что он экспортирует словарь с ключами в виде строк и всеми возможными перестановками в качестве значений. Все возможные длины строк включены, поэтому вы создаете надмножество.
Если вам требуются только окончательные перестановки, вы можете удалить другие ключи из словаря.
В этом коде словарь перестановок является глобальным.
В базовом случае я сохраняю значение как обе возможности в списке. 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]
Рекурсивное решение с драйвером 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);
}
}
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