language-agnostic - 如何找到给定长度的 k 的排列？

Question

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

例如:

单词 cat 有 3 个字母:如何找到单词 cat 中 2 的所有排列。结果应为:ac、at、ca、ac 等...

---

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

Answer 1

这是 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;
        }
    }
}