gpt4 book ai didi

algorithm - 重复的递归排列

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:55:07 25 4
gpt4 key购买 nike

我正在尝试编写一个递归函数,它通过给定列表的重复获取所有排列。

Eg. set = ABC
1. AAA
2. AAB
3. AAC
4. ABA
N. CCC

我想要这个代码的递归版本,这样我就可以获得任何大小的集合的排列:

for i=0; i<S.size(); i++ {
for j=0; j<S.size(); j++ {
for k=0; k<S.size(); k++ {

perm[0] = S[i];
perm[1] = S[j];
perm[2] = S[k];
permutations.push(combo);

}
}
}

我在解决这个问题时遇到了一些麻烦。到目前为止,我在想我需要找到何时达到任意深度以停止重复诅咒。

编辑:我更喜欢伪代码解决方案,我没有在 C++ 中实现它

最佳答案

鉴于您希望输出 AABABA,您正在寻找排列而不是组合。特别是,您正在寻找一组大小 k 的唯一排列,其中元素是从一组 n 标记中替换绘制的。组合数为 n+k-1Ck 而排列数为 nk

说明这两个概念的伪代码:

build_combinations (tokens, set_size)
Arrangements combos
if (set_size == 0)
combos.add ("")
else
Comment: tail_substrings of "ABC" is ("ABC", "BC", "C").
foreach tail (tail_substrings (tokens))
foreach sub_combo (build_combinations (tail, set_size-1))
combos.add (tail.first() + sub_combo)
return combos

build_permutations (tokens, set_size)
Arrangements perms
if (set_size == 0)
perms.add ("")
else
sub_perms = build_permutations (tokens, set_size-1)
foreach token (tokens)
foreach perm (sub_perms)
perms.add (cur_token + *rem_iter)
return perms

一个有效的 C++ 实现:

#include <string>
#include <vector>

typedef std::string::const_iterator StringIterator;
typedef std::vector<std::string> Arrangements;
typedef Arrangements::const_iterator ArrangementsIterator;

Arrangements build_combinations (const std::string & tokens, unsigned set_size)
{
Arrangements combos;
if (set_size == 0) {
combos.push_back ("");
}
else {
for (StringIterator token_iter = tokens.begin();
token_iter != tokens.end();
++token_iter) {
std::string cur_token(1, *token_iter);
std::string rem_tokens(token_iter, tokens.end());
Arrangements rem_combos = build_combinations (rem_tokens, set_size-1);
for (ArrangementsIterator rem_iter = rem_combos.begin();
rem_iter != rem_combos.end();
++rem_iter) {
combos.push_back (cur_token + *rem_iter);
}
}
}
return combos;
}

Arrangements build_permutations (const std::string & tokens, unsigned set_size)
{
Arrangements perms;
if (set_size == 0) {
perms.push_back ("");
}
else {
Arrangements rem_perms = build_permutations (tokens, set_size-1);
for (StringIterator token_iter = tokens.begin();
token_iter != tokens.end();
++token_iter) {
std::string cur_token(1, *token_iter);
for (ArrangementsIterator rem_iter = rem_perms.begin();
rem_iter != rem_perms.end();
++rem_iter) {
perms.push_back (cur_token + *rem_iter);
}
}
}
return perms;
}

关于algorithm - 重复的递归排列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7292370/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com