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

голоса
143

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

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

Задан 02/08/2008 в 07:57
источник пользователем
На других языках...                            


35 ответов

голоса
67

Есть несколько способов сделать это. Общие методы используют рекурсию, запоминание или динамическое программирование. Основная идея заключается в том, что вы создаете список всех строк длины 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)

Вы бы тогда необходимо удалить все строки меньше, чем х в длину, они будут первыми (х-1) * LEN (originalString) записи в списке.

Ответил 02/08/2008 d 08:48
источник пользователем

голоса
35

Это лучше использовать откаты

#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;
}
Ответил 10/01/2012 d 19:00
источник пользователем

голоса
24

Вы собираетесь получить много строк, это точно ...

\ sum_ {я = х} ^ у {\ гидроразрыва {г!} {{(г)}!}} http://www.codecogs.com/eq.latex?%5Csum_%7Bi=x%7D%5Ey% 20% 7B% 20% 5Cfrac% 7BR% 7D% 7B% 7B (г)% 7D% 7D% 20% 7D!
Где, х и у, как вы определяете их и г число символов , мы выбираем из - -Если я правильно понять вас. Вы определенно должны генерировать эти по мере необходимости и не получить неаккуратно и сказать, генерировать Powerset и затем процеживают длину строки.

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

Кнут (объем 4, 2 пучков, 7.2.1.3) говорит о том , что (S, T) -combination эквивалентно S +-вещи взят т в то время , с повторением - (з, т) -combination этого обозначения используется Кнут, равная {т \ выбрать {s + т} http://www.codecogs.com/eq.latex?%7Bt%20%5Cchoose%20%7Bs+t%7D%7D . Мы можем понять это, сначала генерации каждого (S, T) -combination в двоичной форме (так, длины (S + T)) и подсчета числа 0 'слева от каждого 1.

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

Ответил 05/08/2008 d 05:57
источник пользователем

голоса
14

Non рекурсивное решение в соответствии с примером Кнут, 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)
Ответил 09/11/2010 d 14:58
источник пользователем

голоса
12

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

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

Ответил 08/01/2014 d 12:00
источник пользователем

голоса
12

Вот простое решение в 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;
        }
    }
Ответил 05/07/2010 d 10:06
источник пользователем

голоса
12

Некоторые работают 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);
    }
}
Ответил 04/04/2010 d 19:18
источник пользователем

голоса
12

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

Для каждого подмножества, вы все равно должны генерировать все перестановки. Например, если вы хотите 3-х символов из «ABCDE», этот алгоритм даст вам «ABC», «абд», «Абэ» ... но вам придется переставлять каждый, чтобы получить «ACB», «БАК», «ДСС», и т.д.

Ответил 14/11/2008 d 20:36
источник пользователем

голоса
8

Я просто взбитое это вверх быстро в 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 представляет собой текущий размер в итерации. Затем пройти через каждую строку и добавить каждый символ на каждую строку. Наконец, в конце концов, удалите все были ниже порога х и возвращает результат.

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

Ответил 02/08/2008 d 08:56
источник пользователем

голоса
7

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

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")
Ответил 20/04/2012 d 01:21
источник пользователем

голоса
7

переставляют (АВС) -> A.perm (БК) -> A.perm [B.perm (С)] -> A.perm [( * В С), (С В * )] -> [( * А до н.э. ), (в с), (ВС А * ), ( * А СВ), (с в), (КБ А * )] для удаления дубликатов при вставке каждого чека алфавита , чтобы увидеть , если предыдущая строка заканчивается тем же алфавитом (почему? -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;
}

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

Ответил 22/02/2011 d 19:45
источник пользователем

голоса
7

... а вот версия 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;
}
Ответил 07/02/2011 d 22:56
источник пользователем

голоса
7

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

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

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

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

Ответил 15/02/2009 d 11:02
источник пользователем

голоса
7

Вот простое слово 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);
Ответил 20/10/2008 d 01:17
источник пользователем

голоса
7

Рекурсивный раствор в 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;
            }
        }
}
Ответил 29/09/2008 d 02:34
источник пользователем

голоса
7

Это перевод Руби версии Майка, в 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)))))
Ответил 16/09/2008 d 06:15
источник пользователем

голоса
6

Следующие рекурсии принты 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);
    }
}

Ниже приводится обновленная версия выше «ПЕРЕСТ» метод, который делает п! (П факториал) меньше рекурсивных вызовов по сравнению с описанным выше способом

//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()));
   }
}
Ответил 19/06/2013 d 05:23
источник пользователем

голоса
5

Вот нерекурсивна версию я придумал, в 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;
}
Ответил 03/08/2011 d 08:11
источник пользователем

голоса
5
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;
    }
}
Ответил 24/10/2010 d 23:01
источник пользователем

голоса
4

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

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

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

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);
            }
        }
    }
}
Ответил 02/08/2008 d 10:40
источник пользователем

голоса
3

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

Вот реализация с использованием метода кучного в. Длина массива должна быть не менее 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

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

Ответил 02/10/2011 d 10:13
источник пользователем

голоса
2

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

Ответил 13/02/2014 d 22:08
источник пользователем

голоса
2

Этот код в Python, когда вызывается с allowed_charactersнабором до [0,1]и 4 символов максимума, будет генерировать-^ 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()

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

Ответил 26/05/2011 d 15:22
источник пользователем

голоса
2

В рубина:

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

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

Я мог бы неправильно фактический вопрос, хотя - в одном из постов он озвученные, как если бы вы просто нужны BruteForce библиотеки строк, но в основном вопрос звучит, как вам нужно permutate определенной строки.

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

Ответил 15/09/2008 d 18:32
источник пользователем

голоса
0

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

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());
}
Ответил 06/02/2017 d 06:00
источник пользователем

голоса
0

код, написанный на языке Java:

пакет namo.algorithms;

импорт java.util.Scanner;

общественный класс Permuations {

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

}

Ответил 05/06/2016 d 08:42
источник пользователем

голоса
0

Ну вот это элегантный, нерекурсивен, 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;
    }
Ответил 27/06/2015 d 08:44
источник пользователем

голоса
0

Вещее решение:

from itertools import permutations
s = 'ABCDEF'
p = [''.join(x) for x in permutations(s)]
Ответил 13/07/2014 d 08:51
источник пользователем

голоса
0
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

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

Ответил 23/01/2014 d 04:28
источник пользователем

голоса
0

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

}

Ответил 19/10/2013 d 02:34
источник пользователем

голоса
0
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
Ответил 22/08/2013 d 18:51
источник пользователем

голоса
0

Рекурсивный раствор в 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]
Ответил 05/07/2013 d 05:15
источник пользователем

голоса
0

Существует итеративный реализация 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;
}

Полный источник

Ответил 07/05/2013 d 02:18
источник пользователем

голоса
0

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;
    }
Ответил 26/07/2012 d 16:20
источник пользователем

голоса
0

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

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

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

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

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

Ответил 16/09/2008 d 06:33
источник пользователем

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more