1

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

В общем буду благодарен за любую информацию!

P.S. Хотелось бы, чтобы рекурсия всё-таки никуда не пропала.

#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);
        }
}

1 ответ 1

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.

1
  • Это сочетания, размещения учитывают, что 1 2 3 и 2 1 3 — разные...
    – Harry
    20 июл 2022 в 5:23

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.