置换算法

Question

我被要求编写一个置换算法，以求{a，b，c}的排列。因为这是一个著名的问题，在网上可以很容易地得到答案，所以我想做一些不同的事情，这样它就不会看起来像我从互联网上抄袭过来的。它被认为是确定的算法是正确的，但说，该算法是低效的，也有‘主要的关注’在代码中。

如果这里的专家能就这段代码的错误提出建议，我会非常感激的，这样我就可以学习和修正我的错误了。我知道模板的使用是过分的，但除此之外，这段代码有什么错呢？问题是，找出{a，b，c}的排列。

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

template<typename T> vector<T> TruncateVector(vector<T>, int);
template<typename T> vector<vector<T> > GetPerms(vector<T>);
unsigned GetNumPerms(unsigned);
template<typename T>
bool ValidatePermutations(vector<T>, vector<vector<T> >);


int main()
{
       // Create a vector with the elements required to permute
       vector<char> permSet;
       permSet.push_back('a');
       permSet.push_back('b');
       permSet.push_back('c');

       // Get the permutations
       vector<vector<char> > vectorOfPerms = GetPerms(permSet);              


       /* Printing the permutations */
       for(unsigned x=0, counter=1;x<vectorOfPerms.size(); x++)
       {
           cout << "(" << counter << ") ";
           for(unsigned y=0;y<vectorOfPerms[x].size(); y++)
           {
               cout << vectorOfPerms[x].at(y) << ' ';
           }
           counter++;
           cout << endl;
       }

       // Validate the calculated permutations
       // This validation only valid for sets with lexicographic order. See notes in the function.
       bool validation = ValidatePermutations(permSet,vectorOfPerms);

       return 0;
}


template<typename T>
vector<vector<T> > GetPerms(vector<T> permSet)
{
   /* --------------- Permutation algorithm -----------------
    * In this algorithm permutations are calculated by sequentially taking each element in the vector,
    * and then combining it with 'all' the permutations of the rest of the vector elements.
    * Example:
    * GetPerms('a,b,c') --> ( {a, GetPerms('b,c')}, {b, GetPerms('a,c')}, {c, GetPerms('a,b')} }
    * The resultant permutations are returned as a vector of vectors, with each vector consisting of one permutation.
    *
    * Vectors were chosen to store the elements because of its ease of handling (inserting, deleting) and also for its ability
    * to handle different types of data.
    */
   vector<vector<T> > vectorOfPerms(GetNumPerms(permSet.size()));
   unsigned PermCount=0;

   if(permSet.size() == 1)  // Base case. Only one element. Return it back.
   {
       vectorOfPerms[0].push_back(permSet.at(0));
   }
   else
   {
       for(unsigned idx=0; idx<permSet.size(); idx++)
       {          
           vector<T> vectorToPermutate = RemoveElement(permSet, idx);   // Remove the current element being combined to permutations.
           vector<vector<T> > PermVector = GetPerms(vectorToPermutate);  // Get the permutations for the rest of the elements.

           // Combine with the received permutations
           for(unsigned count=0 ; count<PermVector.size(); count++, PermCount++)
           {
               vectorOfPerms[PermCount].push_back(permSet.at(idx));    // Insert the first element
               vectorOfPerms[PermCount].insert(vectorOfPerms[PermCount].begin()+1, PermVector[count].begin(), PermVector[count].end());      // Insert the permutations
           }
       }
   }
   return vectorOfPerms;
}


/*
* This function removes the element at index from the vector permSet
*/
template<typename T>
vector<T> RemoveElement(vector<T> permSet, int index)
{
   permSet.erase(permSet.begin()+index);
   return permSet;
}


/*
* This function returns the number of possible permutations for a given
* number of elements
*/
unsigned GetNumPerms(unsigned numElems) {
 return (numElems == 1 ? numElems : numElems*GetNumPerms(numElems - 1));
}


/*
* This function validates the calculated permutations with the std::next_permutation
* IMPORTANT: This validation will only work if the elements are different and inserted in lexicographic order.
* I.e. {a,b,c} will be correctly validated, but not {a,c,b}.
* The permutations generated are CORRECT. Only the validation with std::next_permutation will not be correct.
* This validation was chosen to validate the program for the given question of finding permutations of {a,b,c}.
*/
template<typename T>
bool ValidatePermutations(vector<T> permSet, vector<vector<T> > result)
{
 bool validationResult = true;

 /* Validating the calculated permutations with the std::next_permutation
  * Since std::next_permutation gives the next lexicographically greater permutation with each call,
  * it must match with the permutations generated in GetPerms() function.
  */
 if(result.size() != GetNumPerms(permSet.size()))
 {
     cout << "Number of permutations is incorrect." << endl;
 }
 else
 {
     // Compare element by element
     for(unsigned permCount=0; permCount<result.size(); permCount++)
     {
         for(unsigned elemCount=0; elemCount<permSet.size(); elemCount++)
         {
             if(result[permCount].at(elemCount) != permSet.at(elemCount))
             {
                 validationResult = false;
                 break;
             }
         }

         if(!validationResult)
         {
             break;
         }
         else
         {
             next_permutation(permSet.begin(),permSet.end());
         }
     }
 }

 cout << "Number of elements: " << permSet.size() << endl;
 cout << "Number of permutations: " << result.size() << endl;
 if(validationResult)
 {
     cout << "Validation: " << "PASS" << endl;
 }
 else
 {
     cout << "Validation: " << "FAIL" << endl;
 }

 return validationResult;
}

Answer 1

• 优先使用增量前运算符(++variable)代替增量后运算符(variable++)。
• 更喜欢基于范围的循环或std::for_each，以便允许编译器为您处理容器边界检查。编译器在这方面将比您的效率更高，并且可能执行循环展开，特别是在std::for_each的情况下。
• 与编写自己的for循环相比，更喜欢使用std算法。std::find_if或std::any_of很适合在容器中找到匹配条件的元素。std::generate和std::transform很适合用函数或另一个容器的值填充容器。
• 而不是: //用vector permSet所需的元素创建一个向量；permSet.push_back('a')；permSet.push_back('b')；permSet.push_back('c')；
• 更喜欢使用统一初始化直接初始化，如: vector permSet{'a'，'b'，'c'}；或者更好(如果您知道不会修改permSet)：const vector permSet{'a'，'b'，'c'}；

Answer 2

预生成所有排列，这意味着当您有20个元素时，当算法完成时，所有的20! = 2.432902e+18可能排列都需要驻留在内存中。

然后，您一遍又一遍地复制所有向量，这也不是一个好主意，因为这需要大量的内存分配和删除。

Answer 3

你问的是编程风格。我非常喜欢把事情简化到尽可能简单，有清晰的名字和强大的类型，并尽可能地把事情归结为一个定义规则。喜欢简单的理由有很多:如果你能读懂它，你可以看到它是正确的。它可以帮助使未来的维护活动更容易和更安全，特别是如果它们不是由您完成的。

所以，让我们看看当我玩你的主作为一个例子会发生什么。我将走得太远，定义和强烈键入一切。

typedef char PERMUTATION_TYPE;
typedef vector<PERMUTATION_TYPE> PERMUTATION_SET;
typedef vector<PERMUTATION_SET> PERMUTATION_SETS;
typedef PERMUTATION_SETS::const_iterator PERMUTATION_SETS_IT;

void printElement(const PERMUTATION_TYPE &element)
{
  cout << element << ' ';
}

void printPermutation (const PERMUTATION_SET &perm)
{
  for_each(perm.begin(), perm.end(), printElement);
  cout << endl;

}

void printIndexedPermutation (const unsigned int permIndex, const PERMUTATION_SET &perm)
{
  cout << "(" << permIndex << ") " ;
  printPermutation(perm);
}


void printPermutationCollection(const PERMUTATION_SETS &permSet)
{
  for (PERMUTATION_SETS_IT perm=permSet.begin(); perm!= permSet.end(); ++perm)
  {
    printIndexedPermutation(distance(permSet.begin(), perm), *perm);
  }
}

void fillPermutationSetWithTestData(PERMUTATION_SET &permSet)
{
  permSet.push_back('a');
  permSet.push_back('b');
  permSet.push_back('c');
}

int main()
{
  PERMUTATION_SET permSet;
  fillPermutationSetWithTestData(permSet);

  PERMUTATION_SETS vectorOfPerms = GetPerms(permSet);              

  printPermutationCollection(vectorOfPerms);

  ValidatePermutations(permSet,vectorOfPerms);

  return 0;
}

所以每个例行公事都很小。main()现在是可读的，没有注释。由于您使用的是std：：集合，所以我不再使用使用索引的for循环，而是使用迭代器。每个例行公事都尽可能简单。是的，他们很多，但他们不花你任何钱。而且它们都很简单。

当然，这就导致了打印索引号的问题。如果我不需要索引号，我就会完全去掉printIndexedPermutation，并且在printPermutationCollection()中只有这一行：

  for_each(permSet.begin(), permSet.end(), printPermutation);

我会建议你用你的代码走这么远吗？这一切都取决于您想要做什么，如果您试图在遥远的将来维护这个例程，或者它只是一个丢弃的代码。但我也有很多经验表明，丢弃的代码有一个令人讨厌的习惯，就是比我预想的时间长得多。