Как найти перестановку k в данной длине?
Как я могу найти перестановки k в данной длине?
Например:
Слово cat имеет 3 буквы: Как я могу найти все перестановки 2 в слове cat. Результат должен быть: ac, at, ca, ac, и т.д...
Это не проблема домашней работы. Любой язык мог использоваться, но более предпочтительный: C/C++ или C#. Я знаю, как создать рекурсию для ДЛИНЫ размера, но не для пользовательского размера.
5 ответов
Вот один на C #, который должен работать даже с повторяющимися символами. Например, для "банана" для перестановок длины 2 это дает:
ba bn ab aa an nb na nn
Основная идея состоит в том, чтобы исправить первый символ, затем сформировать все перестановки длины k-1, затем добавить символ к этим перестановкам длины k-1. Чтобы иметь дело с повторяющимися символами, мы отслеживаем оставшееся количество (то есть те, которые могут использоваться для подстановок).
Не примерный код, но он должен дать вам представление. (Если вы обнаружите ошибки, дайте мне знать, и я смогу отредактировать).
static List<string> Permutations(Dictionary<char, int> input, int length) {
List<string> permutations = new List<string>();
List<char> chars = new List<char>(input.Keys);
// Base case.
if (length == 0) {
permutations.Add(string.Empty);
return permutations;
}
foreach (char c in chars) {
// There are instances of this character left to use.
if (input[c] > 0) {
// Use one instance up.
input[c]--;
// Find sub-permutations of length length -1.
List<string> subpermutations = Permutations(input, length - 1);
// Give back the instance.
input[c]++;
foreach (string s in subpermutations) {
// Prepend the character to be the first character.
permutations.Add(s.Insert(0,new string(c,1)));
}
}
}
return permutations;
}
И вот полная программа, которая у меня есть, чтобы использовать ее:
using System;
using System.Collections.Generic;
namespace StackOverflow {
class Program {
static void Main(string[] args) {
List<string> p = Permutations("abracadabra", 3);
foreach (string s in p) {
Console.WriteLine(s);
}
}
static List<string> Permutations(string s, int length) {
Dictionary<char, int> input = new Dictionary<char, int>();
foreach (char c in s) {
if (input.ContainsKey(c)) {
input[c]++;
} else {
input[c] = 1;
}
}
return Permutations(input, length);
}
static List<string> Permutations(Dictionary<char, int> input,
int length) {
List<string> permutations = new List<string>();
List<char> chars = new List<char>(input.Keys);
if (length == 0) {
permutations.Add(string.Empty);
return permutations;
}
foreach (char c in chars) {
if (input[c] > 0) {
input[c]--;
List<string> subpermutations = Permutations(input,
length - 1);
input[c]++;
foreach (string s in subpermutations) {
permutations.Add(s.Insert(0,new string(c,1)));
}
}
}
return permutations;
}
}
}
Что не так с рекурсивное решение и передача дополнительного параметра (глубины), чтобы рекурсивная функция немедленно возвращалась для глубины> n.
Не самый эффективный, но работает:
public class permutation
{
public static List<string> getPermutations(int n, string word)
{
List<string> tmpPermutation = new List<string>();
if (string.IsNullOrEmpty(word) || n <= 0)
{
tmpPermutation.Add("");
}
else
{
for (int i = 0; i < word.Length; i++)
{
string tmpWord = word.Remove(i, 1);
foreach (var item in getPermutations(n - 1, tmpWord))
{
tmpPermutation.Add(word[i] + item);
}
}
}
return tmpPermutation;
}
}
Если я не ошибаюсь, эту проблему можно решить и с помощью комбинадики, как на http : //en.wikipedia.org/wiki/Combinadic/ , там тоже есть эталонные реализации.
Я сам использовал решение Java ( http://docs.google.com/Doc?id=ddd8c4hm_5fkdr3b/ ) для генерации всех возможных троек из последовательности чисел, это не должно отличаться .
Мне не хватает средств для объяснения математики, лежащей в основе этого, но, насколько я понимаю, это наименее сложный способ перебора всех возможных вариантов nCr (т.е. 3C2 для вашего примера с кошкой) в коллекции.
Сначала найдите возможные подмножества вашего массива. Вы можете сделать это рекурсивным способом, это обсуждалось в Iterating over subsets of any size
Во-вторых, вычислите перестановки каждого подмножества с помощью STL-алгоритма next_permutation
Я не реализовал это, но думаю, что это должно работать.