Размещения без повторений,c++

362
06 января 2017, 10:26

Есть код размещений с повторениями,не могу понять реализацию алгоритма без повторений,везде нахожу что нужна функция аля"NextSet",которая бы как раз проверяла и переставляла,если еще не было повтора.В общем буду благодарен за любую информацию! З.Ы хотелось бы чтобы рекурсия все таки никуда не пропала)

#include <iostream>
#include <sstream>
 
using namespace std;
void Razm(string razm, int place, int n, int k);
 
int main()
{   
    int n;
    int k;
    setlocale (LC_ALL, "Russian");
    cout << "Введите n и k: " << endl;
    cin >> n >> k;
    cout << "Размещения из " << n << " по " << k << ": " << endl;
    Razm("", 1, n, k);
    cin.get();
    cin.get();
    return 0;
}
 
void Razm(string razm, int place, int n, int k)
{
    if(place > k)
        cout << razm << endl;
    else
        for(int i = 0; i < n; i++)
        {
            ostringstream os;
            os << i + 1;
            Razm(razm + os.str() + " ", place + 1, n, k);
        }
}
Answer 1

Возможно как-то так:

#include <iostream>
#include <algorithm>
#include <vector>
typedef std::vector<int> VecType;
typedef std::vector<std::vector<int>> ResType;
/////////////////////////////////////////////////////////////////////////////
void Build(const size_t P, VecType T, const size_t N, const VecType& D, ResType &R) {
  T.push_back(D[P]);  
  if (T.size() == N) R.push_back(T); else 
    for(size_t i=P+1; i<D.size(); i++) Build(i,T,N,D,R);   
}
/////////////////////////////////////////////////////////////////////////////
int main() {
  try {
    // инициализация  
    const size_t N = 3;  
    VecType D = {2,1,3,5,4};
    if (N > D.size()) throw std::logic_error(":(");  
    ResType R = {};
    VecType T = {};  
    // генерация  
    for(size_t i=0; i<=D.size()-N; i++) Build(i,T,N,D,R);  
    // сортировка 
    for(auto &i:R) std::sort(i.begin(),i.end(),std::less<int>());
    std::sort(R.begin(),R.end(),[&](auto &i,auto &j) {
      return std::lexicographical_compare(i.begin(),i.end(),j.begin(),j.end());
    });
    // печать  
    for(const auto &i:R) {
      for(const auto &j:i) std::cout << j << " ";
      std::cout << std::endl;  
    }
  } catch(std::logic_error &E) {
    std::cout << "Ошибка: " << E.what() << std::endl;  
  } catch(...) {
    std::cout << "Ошибка: что-то пошло не так!" << std::endl;  
  }    
  return 0;    
}

вывод:

1 2 3 
1 2 4 
1 2 5 
1 3 4 
1 3 5 
1 4 5 
2 3 4 
2 3 5 
2 4 5 
3 4 5

Тест на ideone.

READ ALSO
Подключение ffmpeg в NetBeans
c++

Подключение ffmpeg в NetBeans

Не получается слинковать ffmpeg библиотеки в NetBeansУказал путь для дополнительных библиотек, указал сами библиотеки, а в результате undefined reference:

 308
Класс без данных
c++

Класс без данных

Помогите понять, что собой представляет класс без данных, и где его можно/нужно использовать

 372
Ошибка при вызове деструктора std::shared_ptr
c++

Ошибка при вызове деструктора std::shared_ptr

Класс CSysError:

 348
Как использовать DirectShow с MinGW?
c++

Как использовать DirectShow с MinGW?

При компиляции MinGW ругается, что в dshowh присутствуют не разрешённые заголовки

 345