5

如何在给定长度内找到 k 的排列？

例如：

这个词cat有 3 个字母：我怎样才能在这个词中找到 2 的所有排列cat。结果应该是：ac, at, ca, ac, 等等...

这不是家庭作业问题。可以使用任何语言，但更可取的是：C/C++ 或 C#。我知道如何为大小 LENGTH 创建递归，但不知道如何为自定义大小创建递归。

4

6 回答 6

3

这是 C# 中的一个，即使使用重复的字符也应该可以工作。例如，对于长度为 2 的排列的“香蕉”，它给出：

ba bn ab aa 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;
        }
    }
}
于 2010-02-28T07:21:52.190 回答
1

递归解决方案有什么问题并传递一个额外的参数（深度）以便递归函数立即返回深度> n。

于 2010-02-28T06:16:09.903 回答
1

不是最有效的，但它有效：

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;
    }
}
于 2010-02-28T07:12:33.727 回答
1 
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;
        }
    }
}
于 2010-09-01T18:36:48.987 回答
0

如果我没记错的话，这个问题也可以通过组合来解决，就像在http://en.wikipedia.org/wiki/Combinadic/上一样，那里也有参考实现。

我自己使用 Java 解决方案 ( http://docs.google.com/Doc?id=ddd8c4hm_5fkdr3b/ ) 从一系列数字生成所有可能的三元组，这应该没有什么不同。

我没有足够的资金来解释它背后的数学原理，但据我所知，这是迭代集合中所有可能的 nCr（即，对于你的 cat 示例的 3C2）选择的最简单的方法。

于 2010-02-28T22:09:56.383 回答
0

首先找到数组的可能子集。您可以以递归方式执行此操作，它在迭代任意大小的子集中进行了讨论

其次使用 STL 算法next_permutation计算每个子集的排列

我还没有实现它，但我认为它应该可以工作。

于 2010-02-28T22:36:13.400 回答