Перестановка алгоритм C++

Question

Я пытаюсь перевести алгоритм, который генерирует все перестановки к из п в 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); 
     } 
    } 
} 

Моя проблема заключается в том, что списки могут быть список объектов, и я не знаю, как удалить x списка L2 ... Я не специалист по C++, мне это удалось на Java, но я должен сделать это на C++.

Answer 1

Я транслитерация вашей функции, и я получил следующий вывод

#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 

Я не знаю, является ли это то, что вы хотите получить.

Если вызвать функцию с к равным 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 

Answer 2

Я нашел способ сделать то, что я хочу с помощью 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 

Требуется меньше 1 секунд, чтобы найти все 10 перестановок из 12 на моем компьютере ... Я не знаю, является ли это хорошим алгоритмом, но он быстрее, чем мой предыдущий алгоритм на Java.

Если кто-то видит, как улучшить и оптимизировать его, меня интересует! :)