如何找到给定长度的k的排列? [英] How to find permutation of k in a given length?
问题描述
如何找到给定长度的k的排列?
How can I find the permutations of k in a given length?
例如:
单词cat
有3个字母:如何找到单词cat
中2的所有排列.
结果应为:ac
,at
,ca
,ac
等...
The word cat
has 3 letters: How can I find all the permutations of 2 in the word cat
.
Result should be: ac
, at
, ca
, ac
, etc...
这不是家庭作业问题. 可以使用任何语言,但更可取的是:C/C ++或C#. 我知道如何为大小LENGTH创建递归,但对于自定义大小却无法创建.
This is not a homework problem. Any language could be used but more preferable: C/C++ or C#. I know how to create the recursion for size LENGTH but not for a custom size.
推荐答案
这是C#中的一个,即使重复字符也可以使用.例如,对于长度为2的排列的香蕉",它给出:
Here is one in C#, which should work even with repeated characters. For example on "banana" for permutations of length 2 it gives:
ba bn ab aa a nb na nn
ba bn ab aa an nb na nn
基本思想是固定第一个字符,然后形成长度为k-1的所有排列,然后在字符前添加k-1个长度的排列.为了处理重复的字符,我们会跟踪剩余的计数(即可以用于子排列的计数).
The basic idea is to fix the first character, then form all permutations of length k-1, then prepend the character to those k-1 length permutations. To deal with duplicate characters, we keep track of the count left (i.e the ones which can be used for sub-permutations).
不是示例代码,但是应该可以给您带来启发. (如果发现错误,请告诉我,我可以编辑).
Not exemplary code, but should give you the idea. (If you find bugs, let me know and I can edit).
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;
}
这是我拥有的完整程序,可以使用它:
And here is the full program I have, to use it:
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;
}
}
}
这篇关于如何找到给定长度的k的排列?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!