Как я могу сделать алгоритм в C ++ для поиска вариантов набора без повторения (т.е. n элементов, выберите k)?

Question

Например, (n = 3, k = 2), я установил {1, 2, 3}, и мне нужен мой алгоритм, чтобы найти: {1, 2}, {1, 3}, {2, 1}, {2, 3}, {3, 1}, {3, 2}.

Я смог создать алгоритм с next_permutation, но он работает оченьмедленно для n = 10, k = 4 (это то, что мне нужно).

Вот мой код:

#include <iostream>
#include <algorithm>

#define pb push_back

using namespace std;

int main() {
    vector <int> s = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    int k = 4; // (n = 10, k = 4)
    map <string, int> m; // To check if we already have that variation

    vector <string> v; // Variations
    do {
        string str = "";
        for (int i = 0; i < k; i++) str += to_string(s[i]);
        if (m[str] == 0) {
            m[str] = 1;
            v.pb(str);
        }
    } while (next_permutation(s.begin(), s.end()));

    return 0;
}

Как я могу сделать алгоритм, который делает это быстрее?

Answer 1

Использование std::next_permutation и bitset (в настоящее время std::prev_permutation для лексикографического порядка и std::vector<bool> вместо std::bitset для обеспечения динамического размера):

template <typename T>
void Combination(const std::vector<T>& v, std::size_t count)
{
    assert(count <= v.size());
    std::vector<bool> bitset(count, 1);
    bitset.resize(v.size(), 0);

    do {
        for (std::size_t i = 0; i != v.size(); ++i) {
            if (bitset[i]) {
                std::cout << v[i] << " ";
            }
        }
        std::cout << std::endl;
    } while (std::prev_permutation(bitset.begin(), bitset.end()));
}

Демо

Answer 2

Медлительность связана с генерацией всех n!перестановки, даже когда требуется только часть из них.Ваша сложность составляет около O (n! * K log n), где O (k log n) является верхней границей сложности запроса std::map со всеми перестановками.

Ответ по MBo ограничен 9 значениями (1..9).Даже если он распространяется на печать более длинных значений, они все равно ограничены числом битов (обычно 31 для int и 64 бит, если доступен uint64_t).

Вот оно:

void print_permutations_impl(std::ostream & out, std::vector<int> & values,
                             unsigned k, std::vector<int> & permutation_stack)
{
    if (k == permutation_stack.size())
    {
        const char* prefix = "";
        for (auto elem: permutation_stack) {
            out << prefix << elem;
            prefix = ", ";
        }
        out << '\n';
        return;
    }
    auto end_valid = values.size() - permutation_stack.size();
    permutation_stack.push_back(0);
    for (unsigned i=0 ; i < end_valid; ++i) {
        permutation_stack.back() = values[i];
        std::swap(values[i], values[end_valid - 1]);
        print_permutations_impl(out, values, k, permutation_stack);
        std::swap(values[i], values[end_valid - 1]);
    }
    permutation_stack.pop_back();
}

void print_permutations(std::ostream & out, const std::vector<int> & values, int k)
{
   std::vector<int> unique = values;
   std::sort(unique.begin(), unique.end());
   unique.erase(std::unique(unique.begin(), unique.end()),
                unique.end());
   std::vector<int> current_permutation;
   print_permutations_impl(out, unique, k, current_permutation);
}

Работает со скоростью менее секунды для N = 100 и K = 2.

Answer 3

Этот код генерирует расположения k элементов из n в лексикографическом порядке, упакованные в целое число для простоты (поэтому 153 соответствует (1,5,3))

void GenArrangement(int n, int k, int idx, int used, int arran) {
    if (idx == k) {
        std::cout << arran << std::endl;
        return;
    }

    for (int i = 0; i < n; i++) 
        if (0 == (used & (1 << i))) 
            GenArrangement(n, k, idx + 1, used | (1 << i), arran * 10 + (i + 1));
}

int main()
{
    GenArrangement(5, 3, 0, 0, 0);
}

123 124 125 132 134 135 142143 145 152 153 154 213 214 215 231 234 235 241 243 245 251 253 254 312 314 315 321 324 325 341 342 345 351 352 354 412 413 415 421 423 425 431 432 435 451 452 453 512 513 514 521 523 5234 531 532 5541 542 543

Answer 4

//finds permutations of an array
#include<iostream>
#include<vector>
using namespace std;

inline void vec_in(vector<unsigned>&, unsigned&);
inline void vec_out(vector<unsigned>&);
inline void vec_sub(vector<vector<unsigned>>&, vector<unsigned>&, unsigned&);

int main(){
  unsigned size;
  cout<<"SIZE : ";
  cin>>size;
  vector<unsigned> vec;
  vec_in(vec,size);
  unsigned choose;
  cout<<"CHOOSE : ";
  cin>>choose;
  vector<vector<unsigned>> sub;
  vec_sub(sub, vec, choose);
  size=sub.size();
  for(unsigned y=0; y<size-2; y++){
    for(unsigned j=0; j<choose-1; j++){
      vector<unsigned> temp;
      for(unsigned i=0; i<=j; i++){
        temp.push_back(sub[y][i]);
      }
      for(unsigned x=y+1; x<size; x++){
        if(temp[0]==sub[x][choose-1]){break;}
        vector<unsigned> _temp;
        _temp=temp;
        for(unsigned i=j+1; i<choose; i++){
          _temp.push_back(sub[x][i]);
        }
        sub.push_back(_temp);
      }
    }
  }
  cout<<sub.size()<<endl;
  for(unsigned i=0; i<sub.size(); i++){
    vec_out(sub[i]);
  }
  return 0;
}

inline void vec_in(vector<unsigned>& vec, unsigned& size){
  for(unsigned i=0; i<size; i++){
    unsigned k;
    cin>>k;
    vec.push_back(k);
  }
}

inline void vec_out(vector<unsigned>& vec){
  for(unsigned i=0; i<vec.size(); i++){
    cout<<vec[i]<<" ";
  }
  cout<<endl;
}

inline void vec_sub(vector<vector<unsigned>>& sub, vector<unsigned>& vec, 
unsigned& size){
  for(unsigned i=0; i<vec.size(); i++){
    //if(i+size==vec.size()){break;}
    vector<unsigned> temp;
    unsigned x=i;
    for(unsigned k=0; k<size; k++){
      temp.push_back(vec[x]);
      x++;
      if(x==vec.size()){x=0;}
    }
    sub.push_back(temp);
  }
}

Это не будет печатать в обратном порядке, как вы сделали в вашем примере.Распечатайте, перевернув массивы один раз, и вы получите свой ответ полностью!

Идея, лежащая в основе этого:

1. Скажем, у вас есть 5 цифр: 1 2 3 4 5, и вы хотите выбрать3 за один раз, затем

2. Найдите подмассивы в последовательном порядке:
1 2 3
2 3 4
3 4 5
4 5 1
51 2

3. Это будут первые n подмассивов массива длины n

4. Теперь возьмем 1 из 1-го подмассива и 3,4 из 2-го подмассиваи создайте другой подмассив из этих 3 элементов, затем возьмите 4,5 из 3-го подмассива и сделайте то же самое.Не берите элементы из двух последних подмассивов, так как после этого элементы начнут повторяться.

5. Теперь возьмите 1,2 из первого подмассива и 4 из 2-го подмассива, сделайте один подмассив ивозьмите 5 из 3-го подпункта и создайте один массив

6. Переместите все эти массивы обратно в список имеющихся массивов.

7. Сделайте тот же шаблон из 2-го подпункта.массив, но не берите элементы с того места, где первый элемент вашего массива начинает совпадать с последним элементом, который вы отбросите из подмассива ниже массива, над которым вы работаете [В предыдущем случае рабочий подуровень был 1-ми мы не начали брать элементы из 4-го суб-массива!]

Answer 5

Вы можете перебирать каждое подмножество с битовой маской.

for(unsigned int i = 0; i < (1<<10);i++)

Если вам не нужен переносимый код, вы можете использовать

__builtin_popcount(int)

Чтобы получить число 1 в двоичном файлепредставление как минимум в gcc с процессором x86.

for(unsigned int i = 0; i < (1<<10);i++) {
    if(__builtin_popcount(i) == 4) { //Check if this subset contains exactly 4 elements
        std::string s;
        for(int j = 0; j < 10; j++) {
            if(i&(1<<j)) { //Check if the bit on the j`th is a one
                s.push_back(to_string(j));
            }
        }
        v.push_back(s);
    }
}