10

For example, (n = 3, k = 2), I have set {1, 2, 3} and I need my algorithm to find: {1, 2}, {1, 3}, {2, 1}, {2, 3}, {3, 1}, {3, 2}.

I was able to make an algorithm with next_permutation, but it works very slow for n = 10, k = 4 (which is what I need).

Here's my code:

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

How can I make an algorithm that does this faster?

Peter Mortensen
  • 30,738
  • 21
  • 105
  • 131
Pero
  • 115
  • 1
  • 8

5 Answers5

6

This code generates arrangements of k items from n in lexicographic order, packed into integer for simplicity (so 153 corresponds to (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 142 143 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 524 531 532 534 541 542 543

MBo
  • 77,366
  • 5
  • 53
  • 86
4

You can iterate over every subset with a bitmask.

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

When you do not need portable code you could use

__builtin_popcount(int)

To get the number of 1s in the binary representation at least in gcc with an x86 processor.

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);
    }
}
Unlikus
  • 1,419
  • 10
  • 24
  • I am aware of this, but this prints combinations, rather than variations, which is not what I need. – Pero Mar 03 '19 at 17:02
  • no need to use popcnt, you can use normal slower way of counting https://en.wikichip.org/wiki/population_count – NoSenseEtAl Mar 03 '19 at 17:03
  • @Pero when you have the combinations, you can use next permutation on these (which are much smaller) – Unlikus Mar 03 '19 at 17:09
3

The slowness is due to generating all n! permutations, even when only a fraction of them is required. Your complexity is around O(n! * k log n), where O(k log n) is an upper bound on the complexity to query the std::map with all of the permutations.

The answer by MBo is limited to 9 values (1..9). Even if it is extended to printing longer values, they are still limited by number of bits (usually 31 for int, and 64 bit if uint64_t is available).

Here it is:

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

It works in sub-second speed for N=100 and K=2.

Michael Veksler
  • 8,217
  • 1
  • 20
  • 33
1
//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);
  }
}

This will not print in reverse order like you have done in you example. Print by reversing the arrays once and you will get your answer completely!

The idea behind this is :

1. Say you have 5 numbers : 1 2 3 4 5 and you want to choose 3 at a time then

2. Find the sub-arrays in serial order :
1 2 3
2 3 4
3 4 5
4 5 1
5 1 2

3. These will be first n sub-arrays of an array of length n

4. Now, take 1 from 1st sub-array and 3,4 from 2nd sub-array and make another sub-array from these 3 elements, then take 4,5 from 3rd sub-array and do the same. Do not take elements from last two sub arrays as after that the elements will start repeating.

5. Now take 1,2 from first sub-array and take 4 from 2nd sub-arr make one sub-array and take 5 from 3rd sub-arr and make one array

6. Push all these arrays back to the list of arrays you are having.

7. Do the same pattern from the 2nd sub-array but don't take elements from where the fist element of your array starts matching the last element that you will throw back from a sub-array below the array you are working on [ In the previous case the working sub-arr was 1st one and we didn't start taking elements from 4th sub array! ]

brightprogrammer
  • 89
  • 4
  • 12
1

Using std::next_permutation and bitset (currently std::prev_permutation to have lexicographic order and std::vector<bool> instead of std::bitset to allow dynamic size):

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

Demo

Jarod42
  • 203,559
  • 14
  • 181
  • 302