如何在给定长度内找到 k 的排列?
例如:
这个词cat
有 3 个字母:我怎样才能在这个词中找到 2 的所有排列cat
。结果应该是:ac
, at
, ca
, ac
, 等等...
这不是家庭作业问题。可以使用任何语言,但更可取的是:C/C++ 或 C#。我知道如何为大小 LENGTH 创建递归,但不知道如何为自定义大小创建递归。
如何在给定长度内找到 k 的排列?
例如:
这个词cat
有 3 个字母:我怎样才能在这个词中找到 2 的所有排列cat
。结果应该是:ac
, at
, ca
, ac
, 等等...
这不是家庭作业问题。可以使用任何语言,但更可取的是:C/C++ 或 C#。我知道如何为大小 LENGTH 创建递归,但不知道如何为自定义大小创建递归。
这是 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;
}
}
}
递归解决方案有什么问题并传递一个额外的参数(深度)以便递归函数立即返回深度> 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;
}
}
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;
}
}
}
如果我没记错的话,这个问题也可以通过组合来解决,就像在http://en.wikipedia.org/wiki/Combinadic/上一样,那里也有参考实现。
我自己使用 Java 解决方案 ( http://docs.google.com/Doc?id=ddd8c4hm_5fkdr3b/ ) 从一系列数字生成所有可能的三元组,这应该没有什么不同。
我没有足够的资金来解释它背后的数学原理,但据我所知,这是迭代集合中所有可能的 nCr(即,对于你的 cat 示例的 3C2)选择的最简单的方法。
首先找到数组的可能子集。您可以以递归方式执行此操作,它在迭代任意大小的子集中进行了讨论
其次使用 STL 算法next_permutation计算每个子集的排列
我还没有实现它,但我认为它应该可以工作。