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

Question

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

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

Answer 1

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

Answer 2

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

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

Answer 3

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

\ 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) -комбинацию в двоичной форме (так, длины (s +) t)) и считая числа 0 слева от каждого 1.

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

Answer 4

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

Answer 5

Некоторый рабочий 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);
    }
}

Answer 6

Вот простое решение в 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;
        }
    }

Answer 7

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

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

Answer 8

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

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

Answer 9

Я только что быстро написал это в 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 и т. Д.).

Answer 10

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

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

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

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