Reputation: 93
I try to translate an algorithm that generates all permutations of k out of n in C++ :
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);
}
}
}
My problem is that the Lists could be Objects list and I don't know how to remove the x of the L2 list... I am not a C++ specialist, I managed it in Java but I have to do it in C++.
Upvotes: 4
Views: 1366
Reputation: 1660
Call permute(nums) and pass nums as a vector that will return another vector containing all permuted numbers.
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;
}
Upvotes: 0
Reputation: 93
I found a way to do what I want using next_permutation() from standard library and also another next_combination() from this article : http://www.codeguru.com/cpp/cpp/algorithms/combinations/article.php/c5117/Combinations-in-C.htm
My solution :
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;
}
That displays :
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
It takes less than 1s to find all 10 permutations out of 12 on my computer... I don't know if this is good algorithm but it's faster than my previous algorithm in Java.
If someone see how to improve and optimize it I am interested ! :)
Upvotes: 3
Reputation: 311126
I have transliterated your function and I have gotten the following
#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 );
}
The program output is
A B
A C
A D
B A
B C
B D
C A
C B
C D
D A
D B
D C
I do not know whether it is what you want to get.
If to call the function with k equal to 3 then the program output will be
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
Upvotes: 3