Создать список всех возможных перестановок строки
Как бы я мог создать список всех возможных перестановок строки между символами x и y по длине, содержащий список переменных символов.
любой язык будет работать, но он должен быть портативным.
30 ответов:
есть несколько способов сделать это. Общие методы использовать рекурсию, мемоизация, или динамического программирования. Основная идея заключается в том, что вы создаете список всех строк длины 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) записи в списке.
лучше использовать 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; }
вы получите много строк, это точно...
\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
Где x и y-это то, как вы их определяете, а r-количество символов, из которых мы выбираем, если я правильно вас понимаю. Вы должны определенно генерировать их по мере необходимости, а не становиться небрежными и говорить, генерировать powerset, а затем фильтровать длина строк.следующее определенно не лучший способ создать их, но это интересно в стороне, тем не менее.
кнут (том 4, брошюра 2, 7.2.1.3) говорит нам,что (s,t)-комбинация эквивалентна S+1 вещам, взятым t за один раз с повторением-(s, t) - комбинация является обозначением, используемым кнутом, которое равно {t \choose {s+t} http://www.codecogs.com/eq.latex?%7Bt%20%5Cchoose%20%7Bs+t%7D%7D. мы можем понять это сначала генерация каждой (s,t)-комбинации в двоичной форме (so, of length (s+t)) и подсчет числа 0 слева от каждого 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)
вы можете посмотреть на "эффективное перечисление подмножеств множества", который описывает алгоритм для выполнения части того, что вы хотите - быстро генерировать все подмножества N символов от длины x до y. он содержит реализацию в C.
для каждого подмножества, вам все равно придется генерировать все перестановки. Например, если вы хотите 3 символа из "abcde", этот алгоритм даст вам "abc","abd", "abe"... но вам придется переставлять каждый из них, чтобы получить " acb", "bac", " bca " и др.
некоторые рабочие 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; } }
есть много хороших ответов здесь. Я также предлагаю очень простое рекурсивное решение на 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 языка для встроенных функций типа перестановки, и вы можете написать более оптимизированный код, но если числа настолько высоки, я не уверен, что есть много способов обойти много результатов.
Я не тестировал его с потенциально бессмысленным вводом (список нулевых символов, странные значения x и y и т. д.).
это перевод версии Майка 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# рекурсивное решение:
способ:
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);
в Perl, если вы хотите ограничиться строчным алфавитом, вы можете сделать это:
my @result = ("a" .. "zzzz");
это дает все возможные строки от 1 до 4 символов, используя прописные символы. Для верхнего регистра измените
"a"
to"A"
и"zzzz"
до"ZZZZ"
.для смешанного случая это становится намного сложнее и, вероятно, не выполнимо с одним из встроенных операторов Perl.
... а вот версия C:
void permute(const char *s, char *out, int *used, int len, int lev) { if (len == lev) { out[lev] = ''; 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; }
перестановки (АВС) -> А. Пермь(БК) -> А. Пермь[Б. Пермь(с)] -> А. Пермь[( * BC), (CB*)] -> [( * ABC), (BAC), (BCA*), ( * ACB), (CA B), (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; }
печатает все перестановки без повторений
Ruby ответ, который работает:
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++
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; } } }
следующая рекурсия 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! (п факториал) меньше рекурсивных вызовов по сравнению с вышеуказанным способом
//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())); } }
Я не уверен, почему вы хотели бы сделать это в первую очередь. Результирующий набор для любых умеренно больших значений 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); } } } }
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; }
я нуждался в этом сегодня, и хотя ответы уже дали мне в правильном направлении, они были не совсем то, что я хотел.
вот реализация с использованием метода кучи. Длина массива должна быть не менее 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
другие методы описаны различными авторами. Кнут описывает два, один дает лексический порядок, но является сложным и медленным, другой известен как метод простых изменений. Цзе Гао и Дяньцзюнь Ван также написали интересное бумага.
в ruby:
str = "a" 100_000_000.times {puts str.next!}
Это довольно быстро, но это займет некоторое время =). Конечно, вы можете начать с "aaaaaaaa", если короткие строки вам не интересны.
Я, возможно, неправильно истолковал фактический вопрос, хотя - в одном из сообщений это звучало так, как будто вам просто нужна библиотека строк bruteforce, но в основном вопросе это звучит так, как будто вам нужно переставить определенную строку.
ваша проблема несколько похожа на эту: http://beust.com/weblog/archives/000491.html (перечислите все целые числа, в которых ни одна из цифр не повторяется, что привело к целому ряду языков, решающих ее, с парнем ocaml, использующим перестановки, и некоторым парнем java, использующим еще одно решение).
этот код в 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()
надеюсь, что это полезно для вас. Работает с любым символом, а не только с числами
вот ссылка, которая описывает, как печатать перестановок строки. http://nipun-linuxtips.blogspot.in/2012/11/print-all-permutations-of-characters-in.html
хотя это не отвечает на ваш вопрос Точно, вот один из способов генерировать каждую перестановку букв из нескольких строк одинаковой длины: например, если ваши слова были "кофе", "joomla" и "moodle", вы можете ожидать выхода, как "coodle", "joodee", "joffle" и т. д.
в основном, количество комбинаций является (количество слов) в степени (количество букв в слове). Итак, выберите случайное число между 0 и количеством комбинаций-1, преобразуйте это number to base (количество слов), затем используйте каждую цифру этого числа в качестве индикатора, для которого слово будет принимать следующую букву.
например: в приведенном выше примере. 3 слова, 6 букв = 729 комбинаций. Выбрать случайное число: 465. Преобразование в базу 3: 122020. Возьмите первую букву из слова 1, 2-й из слова 2, 3-й из слова 2, 4-й из слова 0... и вы получите... "joofle".
Если вы хотели все перестановки, просто цикл от 0 до 728. Конечно, если вы просто выбираете одну случайное значение, много
прощеменее запутанным способом было бы перебирать буквы. Этот метод позволяет избежать рекурсии, если вы хотите все перестановки, плюс это заставляет вас выглядеть, как вы знаете математику(tm)!Если количество комбинаций чрезмерно, вы можете разбить его на ряд меньших слов и объединить их в конце.
в 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 в UncommonsMaths (работает для списка объектов):
/** * 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
вот мой взгляд на нерекурсивную версию