组合算法

Question

我希望实现一个简单的排序算法。

给定输入字符串"abcde"，我想要以下输出结果。请问可以用什么算法实现？

arr[0] = "a"
arr[1] = "ab"
arr[2] = "ac"
arr[3] = "ad"
arr[4] = "ae"
arr[5] = "abc"
arr[6] = "abd"
arr[7] = "abe"
...
arr[n] = "abcde"

arr[n+1] = "b"
arr[n+2] = "bc"
arr[n+3] = "bd"
arr[n+4] = "be"
arr[n+5] = "bcd"
arr[n+5] = "bce"
arr[n+5] = "bde"
...
arr[n+m] = "bcde"
...
...

- mysterious jean

Answer 1

如果您正在寻找“从数组生成幂集”的算法，可以尝试使用Google或其他搜索引擎查找最符合您需求的算法。

- rahmivolkan

---

有时候人们会感觉需要谷歌（Google）某个东西，但不知道算法的名称。+1 - Muxecoid

Answer 2

在C++中，有��下程序：

template <typename Iterator>
bool next_combination(const Iterator first, Iterator k, const Iterator last)
{
   /* Credits: Mark Nelson http://marknelson.us */
   if ((first == last) || (first == k) || (last == k))
      return false;
   Iterator i1 = first;
   Iterator i2 = last;
   ++i1;
   if (last == i1)
      return false;
   i1 = last;
   --i1;
   i1 = k;
   --i2;
   while (first != i1)
   {
      if (*--i1 < *i2)
      {
         Iterator j = k;
         while (!(*i1 < *j)) ++j;
         std::iter_swap(i1,j);
         ++i1;
         ++j;
         i2 = k;
         std::rotate(i1,j,last);
         while (last != j)
         {
            ++j;
            ++i2;
         }
         std::rotate(k,i2,last);
         return true;
      }
   }
   std::rotate(first,k,last);
   return false;
}

您可以按照以下步骤进行操作：

std::string s = "abcde";
for(std::size_t i = 1; i != s.size(); ++i)
{
   do
   {
      std::cout << std::string(s.begin(),s.begin() + i) << std::endl;
   }
   while(next_combination(s.begin(),s.begin() + i,s.end()));
}

注意：你应该期望看到2^n-1个组合，其中n是数组或字符串的长度。

- Matthieu N.

---

您引用的网站似乎没有包含这个程序。 - Potatoswatter

你应该再努力一点：http://marknelson.us/2002/03/01/next-permutation 在页面上搜索术语：“next_combination” - Matthieu N.

@Beh：不正确。我在搜索栏中输入了next_combination，它自动完成了，但没有返回任何结果http://marknelson.us/index.php?submit.x=0&submit.y=0&s=next_combination。我怀疑你使用了谷歌。无论如何，那个页面*并没有*包含该程序，只有带有各种类似程序链接的评论。我看到最接近解释的是http://www.codeguru.com/cpp/cpp/algorithms/combinations/article.php/c5117/，但它没有这个特定的代码。转载别人的代码后，您应该提供更清晰的来源说明。 - Potatoswatter

Answer 3

您正在描述一个幂集。这是一些C++代码：

#include <vector>
#include <string>
#include <algorithm>
#include <functional>
using namespace std;

vector< string > string_powerset( string const &in ) {
    vector< string > result(1); // start output with one empty string
    result.reserve( 1 << in.size() ); // output size = 2^( in.size() )
    if ( result.capacity() != 1<<in.size() ) throw range_error( "too big" );

    for ( string::const_iterator it = in.begin(); it != in.end(); ++ it ) {
        size_t middle = result.size(); // duplicate what we have so far
        result.insert( result.end(), result.begin(), result.end() );

          // append current character onto duplicated output
        for_each( result.begin() + middle, result.end(),
           bind2nd( mem_fun_ref( &string::push_back ), * it ) );
    }
    return result;
}

测试通过 :v) 。范围检查不是最好的，但无所谓。

由于幂集的指数增长，此代码很容易溢出，因此您只应传递短字符串。其他发布的答案通过一次生成并返回一个字符串来避免此问题。但是，这更容易理解，使用一个更大且更令人困惑的代码将是过早优化，除非您确实有一个溢出问题。

编辑：我撰写了一个next_subset答案，它看起来与Ben的完全不同。

- Potatoswatter

---

我投了你一票，因为你很好地使用了STL。但是有一些事情我想批评，这些都是风格问题。首先，using namespace std不是一个好主意。其次，使用移位运算符表示2的幂有点不清晰。第三，为什么要使用string const & in而不是const string & in（我从未见过这种写法）？ - Björn Pollex

1. 我觉得通过修复问题和编写所有这些代码，我赚得了一些懒惰。 OP 没有给我留下可能存在大型代码库问题的印象。这不是一个头文件。
2. 所以我对它进行了评论，并注意到了溢出情况的沮丧。
3. 我的 const 风格更加统一。const 附加到 前面 的标识符或修饰符，除非 const 是类型的第一个标记。我避免了特殊情况。同时，先说 string 可以“更快地入门”。

- Potatoswatter

值得一提的是，这个回答现在有3个赞和3个踩。没有任何一个踩的人留下了评论。 - Potatoswatter

我给你点赞的原因是他们给你踩了。我自己使用你提供的样式，如果有人告诉我他以前从未见过这种样式，我就不知道该说什么了。 - There is nothing we can do