My<cod/>.net
Сформировать список всех возможных перестановок строки
Как бы я мог создать список всех возможных перестановок строки между символами x и y в длину, содержащий список переменных символов.
Любой язык будет работать, но он должен быть портативным.
Есть несколько способов сделать это. Общие методы используют рекурсию, запоминание или динамическое программирование. Основная идея заключается в том, что вы создаете список всех строк длины 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;
}
Вы получите очень много струн, это точно...
\sum_{i=x}^г{\frac{r!}{{(r-i)}!}} http://www.codecogs.com/eq.latex?%5Csum_%7Bi=x%7D%5Ey%20%7B%20%5Cfrac%7Br!%7О%7Б%7Б(r-i)%7Д!%7D%20%7D
Где x и y-это то, как вы их определяете, а r - это количество символов, из которых мы выбираем, если я правильно вас понимаю. Вы должны определенно генерировать их по мере необходимости, а не быть небрежным и, скажем, генерировать powerset, а затем фильтровать длину строк.
Следующее определенно не лучший способ их генерировать, но это интересная сторона, none-the-less.
Кнут (том 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%7б+Т%7О%7Д . Мы можем выяснить это, сначала генерируя каждую (s,t)-комбинацию в двоичной форме (так, длины (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)
Некоторый рабочий код 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
Вы можете заглянуть в language API для встроенных функций типа перестановок, и вы можете написать более оптимизированный код, но если цифры все так высоки, я не уверен, что есть много способов обойти множество результатов.
В любом случае, идея кода заключается в том, чтобы начать со строки длины 0, а затем отслеживать все строки длины Z, где Z-текущий размер в итерации. Затем пройдите через каждую строку и добавьте каждый символ в каждую строку. Наконец, в конце удалите все, что было ниже порога x, и верните результат.
Я не тестировал его с потенциально бессмысленным вводом (список символов null, странные значения x и y и т. д.).
В Perl, если вы хотите ограничиться строчным алфавитом, вы можете сделать это:
my @result = ("a" .. "zzzz");
Это дает все возможные строки от 1 до 4 символов, используя символы нижнего регистра. Для верхнего регистра измените значение "a" на "A" и "zzzz" на "ZZZZ" .
Для смешанного случая это становится намного сложнее, и, вероятно, не выполнимо с одним из встроенных операторов Perl, подобных этому.
Это перевод версии Майка Ruby на общий язык 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)))))
И еще одна версия, немного короче и использующая больше возможностей loop facility:
(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)))))
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# рекурсивное решение:
Метод:
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);
Рекурсивное решение в 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);
}
}
Ниже приводится обновленная версия вышеупомянутого метода "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;
}
}
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);
}
}
}
}
Я нуждался в этом сегодня, и хотя уже полученные ответы указывали мне верное направление, они были не совсем тем, чего я хотел.
Вот реализация, использующая метод кучи. Длина массива должна быть не менее 3 и по практическим соображениям не должна превышать 10 или около того, в зависимости от того, что вы хотите сделать, терпения и тактовой частоты.
Перед тем как войти в цикл, инициализируйте Perm(1 To N) с помощью первой перестановки, Stack(3 To N) с помощью zeroes*, и 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
Другие методы описаны различными авторами. Кнут описывает два, один дает лексический порядок, но является сложным и медленным, другой известен как метод простых изменений. Цзе Гао и Дяньцзюнь Ван также написали интересную работу.
Этот код в python, при вызове с allowed_characters , установленным в [0,1] и 4 символами max, будет генерировать 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()
Надеюсь, это вам пригодится. Работает с любым символом, а не только с цифрами
В ruby:
str = "a"
100_000_000.times {puts str.next!}
Это довольно быстро, но это займет некоторое время =). Конечно, вы можете начать с "aaaaaaaa", если короткие строки вам не интересны.
Возможно, я неправильно истолковал сам вопрос-в одном из постов это звучало так, как будто вам просто нужна библиотека строк bruteforce, но в главном вопросе это звучит так, как будто вам нужно перестановить определенную строку.
Ваша задача чем-то похожа на эту: http://beust.com/weblog/archives/000491.html (перечислите все целые числа, в которых ни одна из цифр не повторяется, что привело к тому, что многие языки решили ее, причем ocaml парень использует перестановки, а некоторые java парень использует еще одно решение).
Вот ссылка, которая описывает, как печатать перестановки строки. http://nipun-linuxtips.blogspot.in/2012/11/print-all-permutations-of-characters-in.html
Хотя это не дает точного ответа на ваш вопрос, вот один из способов генерировать каждую перестановку букв из нескольких строк одинаковой длины: например, если ваши слова были "coffee", "joomla" и "moodle", вы можете ожидать вывода типа "coodle", "joodee", "joffle" и т. д.
В принципе, количество комбинаций - это (количество слов) в степени (количество букв в слове). Итак, выберите случайное число между 0 и числом комбинаций-1, преобразуйте это число в базу (число слов), а затем используйте каждую цифру этого числа в качестве индикатора, для которого нужно взять следующую букву.
например: в приведенном выше примере. 3 слова, 6 букв = 729 комбинаций. Выберите случайное число: 465. Преобразовать в базу 3: 122020. Возьмите первую букву из слова 1, 2-ю из слова 2, 3-ю из слова 2, 4-ю из слова 0... и вы получите... "joofle".
Если вам нужны все перестановки, просто сделайте цикл от 0 до 728. Конечно, если вы просто выбираете одно случайное значение, гораздо более простой и менее запутанный способ-это перебирать буквы. Этот метод позволяет вам избежать рекурсии, если вы хотите все перестановки, плюс он заставляет вас выглядеть так, как будто вы знаете математику (tm) !
Если количество комбинаций слишком велико, вы можете разбить его на ряд более мелких слов и объединить их в конце.