排列算法 C++

Question

我尝试翻译一个在C++中生成n个元素中k个排列的算法：

public void calculerEquipeTOT(ArrayList<Nageur> L, ArrayList<Nageur> F, int k) {

    if (k == 0) {
        if (calculerPointsTOT(L) > this.pointsMeilleureEquipe){
            this.meilleureEquipe = L;
            this.pointsMeilleureEquipe = calculerPointsTOT(meilleureEquipe);
        }
    } else {
        for (Nageur x : F) {
            ArrayList<Nageur> G = new ArrayList<Nageur>(F);
            G.remove(G.indexOf(x));
            ArrayList<Nageur> L2 = new ArrayList<Nageur>(L);
            L2.add(x);
            calculerEquipeTOT(L2, G, k - 1);
        }
    }
}

我的问题是列表可以是对象列表，我不知道如何删除L2列表的x...我不是C++专家，我在Java中实现了它，但我必须在C++中完成。

- Terry Blain

---

实际上使用std::next_permutation有什么问题吗？ - πάντα ῥεῖ

@TerryBlain 不是的。std::next_permutation 可以帮助你计算一个范围内的所有排列组合：std::vector<People> ps = ...; do { doSomething(ps); } while ( std::next_permutation(ps.begin(), ps.end()) );。请参考 http://en.cppreference.com/w/cpp/algorithm/next_permutation 获取示例和详细参考。 - stefan

好的，谢谢@stefan。实际上我需要找到n个元素的所有k排列... - Terry Blain

@TerryBlain 我认为你实际想表达的不是“排列”，而是“子集”。如果我理解正确，你正在搜索一个大小为n的集合S中所有大小为k的子集，对吗？在这种情况下，“排列”无法帮助你找到正确的解决方案。 - stefan

@stefan 是的，那就是我想说的，抱歉我的英语不好。你知道一些高效的方法来做这个吗？实际上，我需要在一个大小为20的集合中找到所有大小为10的子集，平均来说这意味着有很多可能性... - Terry Blain

Answer 1

我找到了一种使用标准库中的next_permutation()和另一个来自这篇文章的next_combination()实现我想要的方法：http://www.codeguru.com/cpp/cpp/algorithms/combinations/article.php/c5117/Combinations-in-C.htm 我的解决方案：

int main(int argc, const char * argv[]) {

    cout << "Hello, World!\n";
    int nb = 0;

    int tab1[] = {0,1,2,3};
    vector<int> n (tab1, tab1+sizeof tab1 / sizeof tab1[0]);
    int tab2[] = {0,1};
    vector<int> r (tab2, tab2+sizeof tab2 / sizeof tab2[0]);

    sort (n.begin(), n.end());
    do
    {
        sort(r.begin(),r.end());
        //do your processing on the new combination here
        vector<int> r2 = r;
        do
        {
            //do your processing on the new permutation here
            nb++;
            display_vector(r2);
            cout << endl;
        }
        while(next_permutation(r2.begin(),r2.end()));
    }
    while(next_combination(n.begin(),n.end(),r.begin(),r.end() ));

    cout << "Number of possibilities = " << nb << endl;

    return 0;
}

这将显示:

Hello, World!
0 1 
1 0 
0 2 
2 0 
0 3 
3 0 
1 2 
2 1 
1 3 
3 1 
2 3 
3 2 
Number of possibilities = 12

在我的电脑上，查找12个元素中的所有10个排列只需不到1秒钟...我不确定这是否是一个出色的算法，但它比我以前在Java中写的算法更快。

如果有人看到如何改进和优化它，我很感兴趣！:)

- Terry Blain

Answer 2

我已经将您的函数音译，并获得以下结果。

#include <iostream>
#include <list>
#include <iterator>

void arrangements( std::list<char> l, std::list<char> f, size_t k ) 
{
    if ( k == 0 ) 
    {
        for ( char c : l ) std::cout << c << ' ';
        std::cout << std::endl;
    } 
    else 
    {
        for ( auto it = f.begin(); it != f.end(); ++it )
        {
            std::list<char> g( f.begin(), it );
            g.insert( g.end(), std::next( it ), f.end() );

            std::list<char> l2( l );
            l2.push_back( *it );

            arrangements( l2, g , k-1 );
        }
    }
}

int main()
{
    std::list<char> f = { 'A', 'B', 'C', 'D' };

    arrangements( std::list<char>(), f, 2 );
}

程序输出为：

A B 
A C 
A D 
B A 
B C 
B D 
C A 
C B 
C D 
D A 
D B 
D C 

我不确定这是否是你想要的。

如果将k设为3调用该函数，则程序输出将为：

A B C 
A B D 
A C B 
A C D 
A D B 
A D C 
B A C 
B A D 
B C A 
B C D 
B D A 
B D C 
C A B 
C A D 
C B A 
C B D 
C D A 
C D B 
D A B 
D A C 
D B A 
D B C 
D C A 
D C B 

- Vlad from Moscow

---

这正是我想要的（我已经更新了主题，附上了我的Java代码，但我不知道它是否是最有效的方法） - Terry Blain

@Terry Blain 我也不知道。:) - Vlad from Moscow

@Terry Blain，C++算法不够高效。最好不要创建一个新的列表G，在递归调用中使用相同的列表F。 :) - Vlad from Moscow

@Terry Blain，看起来最好使用列表的切片方法，并通过引用传递列表。我只是快速地将你最初展示的伪代码翻译了一下。所以你可以自己改进代码。:) - Vlad from Moscow

请问您能帮我优化这个算法吗？ - Terry Blain

Answer 3

调用 permute(nums) 并将 nums 作为向量传递，它将返回另一个包含所有排列数字的向量。

void getPermutation(vector<int>& nums,vector<int> current_indices, vector<vector<int>>& permutation)
    {
        if (nums.size()==current_indices.size()) 
        {
            vector <int> temp;
            for(auto index:current_indices)
                temp.push_back(nums[index]);
            permutation.push_back(temp);

            return;
        }

        vector <int> remaining_indices;
        for (int i=0;i<nums.size();i++)
        {
            if(std::find(current_indices.begin(), current_indices.end(), i) != current_indices.end()) 
            {
                //do nothing
            } 
            else 
            {
                remaining_indices.push_back(i);
            }
        }

        while (remaining_indices.size()>0)
        {
            vector<int> temp = current_indices;
            temp.push_back(remaining_indices[0]);
            getPermutation(nums,temp,permutation);
            remaining_indices.erase(remaining_indices.begin());
        }

        return;

    }
    vector<vector<int>> permute(vector<int>& nums) {

      vector<vector<int>> permutation;
      vector<int> current_indices; 
      getPermutation( nums,current_indices, permutation);
      
      return permutation;

        
    }

- Monir