递归地生成字符串排列;每个字符出现n次
Generate string permutations recursively; each character appears n times
我正在尝试编写一个算法来生成所有长度为 nm 的字符串,每个数字恰好有 n 个 1、2、... m,
例如所有长度为 6 的字符串,恰好有两个 1、两个 2 和两个 3,例如112233, 121233,
我设法使用递归方法只用 1 和 2 做到了这一点,但是当我引入 3 时似乎无法得到有用的东西。
当m=2时,我的算法是:
generateAllStrings(int len, int K, String str)
{
if(len == 0)
{
output(str);
}
if(K > 0)
{
generateAllStrings(len - 1, K - 1, str + '2');
}
if(len > K)
{
generateAllStrings(len - 1, K, str + '1');
}
}
我试过为第三个数字插入类似的条件,但算法没有给出正确的输出。在那之后我什至不知道如何概括 4 个及以上的数字。
递归是正确的做法吗?任何帮助将不胜感激。
一个选项是列出字符串 111...1222...2...nnn....n
的所有不同排列。有一些很好的算法可以根据字符串的长度及时枚举字符串的所有不同排列,它们可能是解决这个问题的好方法。
您可以使用 DFS(或 BFS)轻松地做到这一点。我们可以定义一个图,使得每个节点包含一个字符串,并且一个节点连接到任何包含字符串的节点,该字符串与原始字符串相比交换了一对 int
。这个图是连通的,因此我们可以很容易地生成一个所有节点的集合;它将包含搜索的所有字符串:
set generated_strings
list nodes
nodes.add(generateInitialString(N , M))
generated_strings.add(generateInitialString(N , M))
while(!nodes.empty())
string tmp = nodes.remove(0)
for (int i in [0 , N * M))
for (int j in distinct([0 , N * M) , i))
string new = swap(tmp , i , j)
if (!generated_strings.contains(new))
nodes.add(new)
generated_strings.add(new)
//generated_strings now contains all strings that can possibly be generated.
要使用简单的递归算法,请为每个递归提供到目前为止的排列(变量 perm
),以及仍然可用的每个数字的出现次数(数组 count
)。
运行 为 n=2
和 m=4
生成所有唯一排列的代码片段(设置:11223344
)。
function permutations(n, m) {
var perm = "", count = []; // start with empty permutation
for (var i = 0; i < m; i++) count[i] = n; // set available number for each digit = n
permute(perm, count); // start recursion with "" and [n,n,n...]
function permute(perm, count) {
var done = true;
for (var i = 0; i < count.length; i++) { // iterate over all digits
if (count[i] > 0) { // more instances of digit i available
var c = count.slice(); // create hard copy of count array
--c[i]; // decrement count of digit i
permute(perm + (i + 1), c); // add digit to permutation and recurse
done = false; // digits left over: not the last step
}
}
if (done) document.write(perm + "<BR>"); // no digits left: complete permutation
}
}
permutations(2, 4);
我正在尝试编写一个算法来生成所有长度为 nm 的字符串,每个数字恰好有 n 个 1、2、... m,
例如所有长度为 6 的字符串,恰好有两个 1、两个 2 和两个 3,例如112233, 121233,
我设法使用递归方法只用 1 和 2 做到了这一点,但是当我引入 3 时似乎无法得到有用的东西。
当m=2时,我的算法是:
generateAllStrings(int len, int K, String str)
{
if(len == 0)
{
output(str);
}
if(K > 0)
{
generateAllStrings(len - 1, K - 1, str + '2');
}
if(len > K)
{
generateAllStrings(len - 1, K, str + '1');
}
}
我试过为第三个数字插入类似的条件,但算法没有给出正确的输出。在那之后我什至不知道如何概括 4 个及以上的数字。
递归是正确的做法吗?任何帮助将不胜感激。
一个选项是列出字符串 111...1222...2...nnn....n
的所有不同排列。有一些很好的算法可以根据字符串的长度及时枚举字符串的所有不同排列,它们可能是解决这个问题的好方法。
您可以使用 DFS(或 BFS)轻松地做到这一点。我们可以定义一个图,使得每个节点包含一个字符串,并且一个节点连接到任何包含字符串的节点,该字符串与原始字符串相比交换了一对 int
。这个图是连通的,因此我们可以很容易地生成一个所有节点的集合;它将包含搜索的所有字符串:
set generated_strings
list nodes
nodes.add(generateInitialString(N , M))
generated_strings.add(generateInitialString(N , M))
while(!nodes.empty())
string tmp = nodes.remove(0)
for (int i in [0 , N * M))
for (int j in distinct([0 , N * M) , i))
string new = swap(tmp , i , j)
if (!generated_strings.contains(new))
nodes.add(new)
generated_strings.add(new)
//generated_strings now contains all strings that can possibly be generated.
要使用简单的递归算法,请为每个递归提供到目前为止的排列(变量 perm
),以及仍然可用的每个数字的出现次数(数组 count
)。
运行 为 n=2
和 m=4
生成所有唯一排列的代码片段(设置:11223344
)。
function permutations(n, m) {
var perm = "", count = []; // start with empty permutation
for (var i = 0; i < m; i++) count[i] = n; // set available number for each digit = n
permute(perm, count); // start recursion with "" and [n,n,n...]
function permute(perm, count) {
var done = true;
for (var i = 0; i < count.length; i++) { // iterate over all digits
if (count[i] > 0) { // more instances of digit i available
var c = count.slice(); // create hard copy of count array
--c[i]; // decrement count of digit i
permute(perm + (i + 1), c); // add digit to permutation and recurse
done = false; // digits left over: not the last step
}
}
if (done) document.write(perm + "<BR>"); // no digits left: complete permutation
}
}
permutations(2, 4);