-4

我正在尝试使用 26 个字母（仅相当于 26*25*24=15,600）来计算所有可能的 3 个字母排列。字母的顺序很重要，我不想重复字母。（我希望按字典顺序生成排列，但这不是必需的）

到目前为止，我尝试嵌套for循环，但最终我遍历了所有可能的组合。所以有重复的字母，这是我不想要的，for如果我想要超过 3 个字母，循环会变得难以管理。

我可以翻阅这些字母，直到我得到一个没有使用过的字母，但它不是按字典顺序排列的，而且它比使用慢得多next_permutation（我不能使用这种std方法，因为我要计算的所有子集26 个字母）。

有没有更有效的方法来做到这一点？从效率低下的角度来看，next_permutation立即迭代前 6 位数字。然而，使用这种方法获得所有三个字母排列需要几秒钟，并且next_permutation对于我必须计算的 2^n 个子集，仍然很快变得低效。

这是嵌套for循环的内容：

char key[] = {'a','b','c','d','e','f','g','h','i','j','k',
'l','m','n','o','p','r','s','t','u','v','w','x','y','z'};
bool used[25];
ZeroMemory( used, sizeof(bool)*25 );

for( int i = 0; i < 25; i++ )
{
     while( used[i] == true )
          i++;
     if( i >= 25 )
          break;
     used[i] = true;
     for( int j = 0; j < 25; j++ )
     {
          while( used[j] == true )
               j++;
          if( j >= 25 )
               break;
          used[j] = true;
          for( int k = 0; k < 25; k++ )
          {
               while( used[k] == true )
                    k++;
               if( k >= 25 )
                    break;
               used[k] = true;

               cout << key[i] << key[j] << key[k] << endl;

               used[k] = false;
          }
          used[j] = false;
     }
     used[i] = false;
}
4

4 回答 4

6

  1. 做一个代表组合开始的根，所以它没有价值。

  2. 计算所有可能的孩子（26 个字母，26 个孩子......）

  3. 对于每个根孩子计算可能的孩子（所以：剩余的字母）

  4. 使用递归有限深度搜索来查找您的组合。

于 2013-07-30T14:43:05.107 回答
4

如果我只想要一个“简单”的解决方案，这是我会尝试的解决方案。我不确定这对资源有多么密集，所以我建议你从一小部分字母开始尝试。

a = {a...z}
b = {a...z}
c = {a...z}

for each(a)
{
  for each(b)
  {
    for each(c)
    {
     echo a + b + c;
    }
  }
}
于 2013-07-30T14:44:22.103 回答
3

对于一个特定的和小的，n，像你这样的手动循环是最简单的方法。但是，您的代码可以高度简化：

for(char a='a'; a<='z'; ++a) {
    for(char b='a'; b<='z'; ++b) {
        if (b==a) continue;
        for(char c='a'; c<='z'; ++c) {
            if (c==a) continue;
            if (c==b) continue;
            std::cout << a << b << c << '\n';
        }
    }
}

对于变量 N，显然我们需要不同的策略。而且，事实证明，它需要一个非常不同的策略。这是基于 DaMachk 的回答，使用递归生成后续字母

template<class func_type> 
void generate(std::string& word, int length, const func_type& func) {
    for(char i='a'; i<='z'; ++i) {
        bool used = false;
        for(char c : word) {
            if (c==i) {
                used = true;
                break;
            }
        }
        if (used) continue;
        word.push_back(i);
        if (length==1) func(word);
        else generate(word, length-1, func);
        word.pop_back();
    }
}
template<class func_type> 
void generate(int length, const func_type& func) {
    std::string word;
    generate(word, length, func);
}

在这里你可以看到它

我还制作了一个展开的版本，结果证明它非常复杂，但速度要快得多。我有两个辅助函数：我有一个“查找下一个字母”（称为next_unused）的函数，它将索引处的字母增加到下一个未使用的字母，或者false如果它不能返回则返回。第三个函数，reset_range“重置”从给定索引到字符串末尾的一系列字母，它可以是第一个未使用的字母。首先我们reset_range用来查找第一个字符串。要查找后续字符串，我们调用next_unused在最后一个字母上，如果失败，则倒数第二个字母，如果失败则倒数第三个字母，依此类推。当我们找到一个可以适当增加的字母时，我们将“重置”右侧的所有字母到最小的未使用值。如果我们一直到第一个字母并且它无法增加，那么我们已经到了结尾，我们停止了。代码很吓人，但这是我能想到的最好的。

bool next_unused(char& dest, char begin, bool* used) {
    used[dest] = false;
    dest = 0;
    if (begin > 'Z') return false;
    while(used[begin]) {
        if (++begin > 'Z')
            return false;
    }
    dest = begin;
    used[begin] = true;
    return true;
}
void reset_range(std::string& word, int begin, bool* used) {
    int count = word.size()-begin;
    for(int i=0; i<count; ++i)
        assert(next_unused(word[i+begin], 'A'+i, used));
}
template<class func_type>
void doit(int n, func_type func) {
    bool used['Z'+1] = {};
    std::string word(n, '\0');
    reset_range(word, 0, used);
    for(;;) {
        func(word);
        //find next word
        int index = word.size()-1;
        while(next_unused(word[index], word[index]+1, used) == false) {
            if (--index < 0)
                return; //no more permutations
        }
        reset_range(word, index+1, used);
   }
}

它在这里工作。
在这里，它的运行时间是简单的四分之一

于 2013-07-30T20:53:38.057 回答
0

我在powershell中做了类似的事情。生成 9 个符号的所有可能组合。经过一番反复试验，这就是我想出的。

$S1=New-Object System.Collections.ArrayList
$S1.Add("a")
$S1.Add("b")
$S1.Add("c")
$S1.Add("d")
$S1.Add("e")
$S1.Add("f")
$S1.Add("g")
$S1.Add("h")
$S1.Add("i")
$S1 | % {$a = $_
    $S2 = $S1.Clone()
    $S2.Remove($_)
    $S2 | % {$b = $_
        $S3 = $S2.Clone()
        $S3.Remove($_)
        $S3 | % {$c = $_
            $S4 = $S2.Clone()
            $S4.Remove($_)
            $S4 | % {$d = $_
                $S5 = $S4.Clone()
                $S5.Remove($_)
                $S5 | % {$e = $_
                    $S6 = $S5.Clone()
                    $S6.Remove($_)
                    $S6 | % {$f = $_
                        $S7 = $S6.Clone()
                        $S7.Remove($_)
                        $S7 | % {$g = $_
                            $S8 = $S7.Clone()
                            $S8.Remove($_)
                            $S8 | % {$h = $_
                                $S9 = $S8.Clone()
                                $S9.Remove($_)
                                $S9 | % {$i = $_
                                    ($a+$b+$c+$d+$e+$f+$g+$h+$i)
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}
于 2013-08-24T09:02:55.343 回答