Как найти перестановку k в заданной длине? - PullRequest
Новая
       27

Как найти перестановку k в заданной длине?

5 голосов
/ 28 февраля 2010

Как я могу найти перестановки k в данной длине?

Например:

Слово cat состоит из 3 букв: как найти все перестановки 2 в слове cat. Результат должен быть: ac, at, ca, ac и т. Д. *

Это не проблема домашней работы. Можно использовать любой язык, но более предпочтительный: C / C ++ или C #. Я знаю, как создать рекурсию для размера ДЛИНА, но не для нестандартного размера.

Ответы [ 6 ]

3 голосов
/ 28 февраля 2010

Вот один в C #, который должен работать даже с повторяющимися символами. Например, для «банана» для перестановок длины 2 это дает:

ба бн а б а б а н н н н н

Основная идея состоит в том, чтобы исправить первый символ, затем сформировать все перестановки длины 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;
        }
    }
}
1 голос
/ 01 сентября 2010 
void Prem (char *str, int k, int length) {
    if (k == length-1){
         printf("%s\n",str);
         return;
    } else {
        for (int i = k ; i < length; ++i) {
            char t = str[k];
            str[k] = str[i];
            str[i] = t;
            Prem(str,k+1,length);
            t = str[k];
            str[k] = str[i];
            str[i] = t;
        }
    }
}
1 голос
/ 28 февраля 2010

Не самый эффективный, но работает: 

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;
    }
}
1 голос
/ 28 февраля 2010

Что не так с рекурсивным решением и передачей дополнительного параметра (глубины), чтобы рекурсивная функция немедленно возвращалась для глубины> n.

0 голосов
/ 01 марта 2010

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

Второй рассчитать перестановки каждого подмножества с помощью STL-алгоритма next_permutation

Я не реализовал это, но я думаю, что это должно работать.

0 голосов
/ 01 марта 2010

Если я не ошибаюсь, эта проблема может быть решена и с помощью комбинадики, так как на http://en.wikipedia.org/wiki/Combinadic/, есть и эталонные реализации.

Я использовал решение Java (http://docs.google.com/Doc?id=ddd8c4hm_5fkdr3b/) сам для генерации всех возможных троек из последовательности чисел, это не должно отличаться.

Мне не хватает средств, чтобы объяснить математику, стоящую за ней, но, насколько я понимаю, это наименее сложный способ перебора всех возможных вариантов nCr (т. Е. 3C2 для вашего примера кошки) в коллекции.

...