blocks|key|1258648|text|递归解决方案有什么问题，并传递了一个额外的参数(深度)，以便递归函数立即返回深度>+n。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1258649|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

What's wrong with the recursive solution and passing an extra parameter (depth) so that the recursive function returns immediately for depth > n.

blocks|key|1459145|text|不是最有效率的，但它起作用了：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1459146|public+class+permutation
{
++++public+static+List<string>+getPermutations(int+n,+string+word)
++++{
++++++++List<string>+tmpPermutation+=+new+List<string>();
++++++++if+(string.IsNullOrEmpty(word)+%7C%7C+n+<=+0)
++++++++{
++++++++++++tmpPermutation.Add("");
++++++++}
++++++++else
++++++++{
++++++++++++for+(int+i+=+0;+i+<+word.Length;+i%2B%2B)
++++++++++++{
++++++++++++++++string+tmpWord+=+word.Remove(i,+1);
++++++++++++++++foreach+(var+item+in+getPermutations(n+-+1,+tmpWord))
++++++++++++++++{
++++++++++++++++++++tmpPermutation.Add(word[i]+%2B+item);
++++++++++++++++}
++++++++++++}
++++++++}
++++++++return+tmpPermutation;
++++}
}|code-block|syntax|javascript|1459147|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

Not the most efficient, but it works:

<pre><code>public class permutation
{
 public static List&lt;string&gt; getPermutations(int n, string word)
 {
 List&lt;string&gt; tmpPermutation = new List&lt;string&gt;();
 if (string.IsNullOrEmpty(word) || n &lt;= 0)
 {
 tmpPermutation.Add("");
 }
 else
 {
 for (int i = 0; i &lt; word.Length; i++)
 {
 string tmpWord = word.Remove(i, 1);
 foreach (var item in getPermutations(n - 1, tmpWord))
 {
 tmpPermutation.Add(word[i] + item);
 }
 }
 }
 return tmpPermutation;
 }
}
</code></pre>

blocks|key|1459175|text|下面是C#中的一个，它甚至可以使用重复的字符。例如，关于长度为2的排列的“香蕉”，它给出：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1459176|和nb+nn|blockquote|1459177|其基本思想是修复第一个字符，然后形成长度为k-1的所有排列，然后将字符加到那些k-1长度的排列上。为了处理重复字符，我们跟踪左边的计数(即可以用于子排列的计数)。|1459178|不是示范性的代码，但应该给你一个想法。(如果你发现bug，请告诉我，我可以编辑)。|1459179|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]%2B%2B;

++++++++++++foreach+(string+s+in+subpermutations)+{

++++++++++++++++//+Prepend+the+character+to+be+the+first+character.
++++++++++++++++permutations.Add(s.Insert(0,new+string(c,1)));

++++++++++++}
++++++++}
++++}

++++return+permutations;
}|code-block|syntax|javascript|1459180|下面是我要使用的完整程序：|1459181|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]%2B%2B;
++++++++++++++++}+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]%2B%2B;

++++++++++++++++++++foreach+(string+s+in+subpermutations)+{
++++++++++++++++++++++++permutations.Add(s.Insert(0,new+string(c,1)));
++++++++++++++++++++}
++++++++++++++++}
++++++++++++}

++++++++++++return+permutations;
++++++++}
++++}
}|1459182|entityMap^0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|T|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|U|8|@]|9|@]|A|$]]|$1|E|3|F|5|6|7|V|8|@]|9|@]|A|$]]|$1|G|3|H|5|6|7|W|8|@]|9|@]|A|$]]|$1|I|3|J|5|K|7|X|8|@]|9|@]|A|$L|M]]|$1|N|3|O|5|6|7|Y|8|@]|9|@]|A|$]]|$1|P|3|Q|5|K|7|Z|8|@]|9|@]|A|$L|M]]|$1|R|3|-4|5|6|7|10|8|@]|9|@]|A|$]]]|S|$]]

Here is one in C#, which should work even with repeated characters. For example on "banana" for permutations of length 2 it gives:

<blockquote>
 ba bn ab aa an nb na nn
</blockquote>

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).

<pre><code>static List&lt;string&gt; Permutations(Dictionary&lt;char, int&gt; input, int length) {
 List&lt;string&gt; permutations = new List&lt;string&gt;();

 List&lt;char&gt; chars = new List&lt;char&gt;(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] &gt; 0) {

 // Use one instance up.
 input[c]--;

 // Find sub-permutations of length length -1.
 List&lt;string&gt; 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;
}
</code></pre>

And here is the full program I have, to use it:

<pre><code>using System;
using System.Collections.Generic;

namespace StackOverflow {

 class Program {
 static void Main(string[] args) {
 List&lt;string&gt; p = Permutations("abracadabra", 3);
 foreach (string s in p) {
 Console.WriteLine(s);
 }
 }

 static List&lt;string&gt; Permutations(string s, int length) {
 Dictionary&lt;char, int&gt; input = new Dictionary&lt;char, int&gt;();
 foreach (char c in s) {
 if (input.ContainsKey(c)) {
 input[c]++;
 } else {
 input[c] = 1;
 }
 }
 return Permutations(input, length);
 }

 static List&lt;string&gt; Permutations(Dictionary&lt;char, int&gt; input, 
 int length) {
 List&lt;string&gt; permutations = new List&lt;string&gt;();

 List&lt;char&gt; chars = new List&lt;char&gt;(input.Keys);
 if (length == 0) {
 permutations.Add(string.Empty);
 return permutations;
 }

 foreach (char c in chars) {
 if (input[c] &gt; 0) {
 input[c]--;
 List&lt;string&gt; subpermutations = Permutations(input, 
 length - 1);
 input[c]++;

 foreach (string s in subpermutations) {
 permutations.Add(s.Insert(0,new string(c,1)));
 }
 }
 }

 return permutations;
 }
 }
}
</code></pre>

blocks|key|1258706|text|如果我没有弄错的话，这个问题也可以通过组合学来解决，就像在http://en.wikipedia.org/wiki/Combinadic/上一样，那里也有参考实现。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1258707|我自己使用了Java解决方案(5kdr3b/)来从一个数字序列生成所有可能的三元组，这应该没有什么不同。|1258708|我缺乏解释其背后的数学的资金，但据我所知，这是在集合中迭代所有可能的nCr+(即猫示例的3C2+)选项的最简单的方法。|1258709|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Combinadic/|1|http://docs.google.com/Doc?id=ddd8c4hm_5fkdr3b/^0|T|14|0|0|F|7|1|0|0^^$0|@$1|2|3|4|5|6|7|R|8|@]|9|@$A|S|B|T|1|U]]|C|$]]|$1|D|3|E|5|6|7|V|8|@]|9|@$A|W|B|X|1|Y]]|C|$]]|$1|F|3|G|5|6|7|Z|8|@]|9|@]|C|$]]|$1|H|3|-4|5|6|7|10|8|@]|9|@]|C|$]]]|I|$J|$5|K|L|M|C|$N|O]]|P|$5|K|L|M|C|$N|Q]]]]

If I'm not mistaken, this problem can be solved by combinadics too, as on <a href="http://en.wikipedia.org/wiki/Combinadic/" rel="nofollow noreferrer">http://en.wikipedia.org/wiki/Combinadic/</a>, there are reference implementations there too.

I have used the Java solution (<a href="http://docs.google.com/Doc?id=ddd8c4hm_5fkdr3b/" rel="nofollow noreferrer">http://docs.google.com/Doc?id=ddd8c4hm_5fkdr3b/</a>) myself for generating all possible triples from a sequence of numbers, this should be no different.

I lack the wherewithal to explain the math behind it, but as I understand this is the least complex way to iterate over all possible nCr (i.e. 3C2 for your cat example) choices within a collection.

blocks|key|2983035|text|首先，找到数组的可能子集。您可以用递归的方式来实现这一点，这是在迭代任意大小的子集中讨论过的。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|2983036|第二，用STL算法排列计算每个子集的排列。|2983037|我还没有实现它，但我认为它应该有效。|2983038|entityMap|0|LINK|mutability|MUTABLE|url|https://stackoverflow.com/questions/1683241/iterating-over-subsets-of-any-size|1|http://www.cplusplus.com/reference/algorithm/next_permutation/^0|W|9|0|0|9|2|1|0|0^^$0|@$1|2|3|4|5|6|7|R|8|@]|9|@$A|S|B|T|1|U]]|C|$]]|$1|D|3|E|5|6|7|V|8|@]|9|@$A|W|B|X|1|Y]]|C|$]]|$1|F|3|G|5|6|7|Z|8|@]|9|@]|C|$]]|$1|H|3|-4|5|6|7|10|8|@]|9|@]|C|$]]]|I|$J|$5|K|L|M|C|$N|O]]|P|$5|K|L|M|C|$N|Q]]]]

First find the possible subsets of your array. You can do this in
a recursive way it was discussed in <a href="https://stackoverflow.com/questions/1683241/iterating-over-subsets-of-any-size">Iterating over subsets of any size</a>

Second calculate the permutations of every subset with the STL-Algorithm
<a href="http://www.cplusplus.com/reference/algorithm/next_permutation/" rel="nofollow noreferrer">next_permutation</a>

I haven't implemented it but i think it should work.

blocks|key|1459284|text|void+Prem+(char+*str,+int+k,+int+length)+{
++++if+(k+==+length-1){
+++++++++printf("%25s\n",str);
+++++++++return;
++++}+else+{
++++++++for+(int+i+=+k+;+i+<+length;+%2B%2Bi)+{
++++++++++++char+t+=+str[k];
++++++++++++str[k]+=+str[i];
++++++++++++str[i]+=+t;
++++++++++++Prem(str,k%2B1,length);
++++++++++++t+=+str[k];
++++++++++++str[k]+=+str[i];
++++++++++++str[i]+=+t;
++++++++}
++++}
}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|1459285|unstyled|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$B|C]]|$1|D|3|-4|5|E|7|H|8|@]|9|@]|A|$]]]|F|$]]

<pre><code>void Prem (char *str, int k, int length) {
 if (k == length-1){
 printf("%s\n",str);
 return;
 } else {
 for (int i = k ; i &lt; 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;
 }
 }
}
</code></pre>

How can I find the permutations of k in a given length?

For example:

The word <code>cat</code> has 3 letters: How can I find all the permutations of 2 in the word <code>cat</code>.
Result should be: <code>ac</code>, <code>at</code>, <code>ca</code>, <code>ac</code>, etc...

<hr>

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.

How to find permutation of k in a given length?

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

我怎样才能在给定的长度内找到k的排列？例如：单词cat有三个字母:我如何才能在单词cat中找到2的所有排列。结果为：ac、at、ca、ac等。这不是家庭作业问题。任何语言都可以使用，但更可取的是: C/C++或C#。我知道如何为大小长度创建递归，但不为自定义大小创建递归。

问如何在给定长度内求k的置换？
EN

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问如何在给定长度内求k的置换？EN