Fixed size permutation

Hello I would like to transform this code that it generates string permutation and not character permutation only with string vectors but I don't know how I should go about replacing the character vectors. I want to keep the possibility to choose the size of the permutations generated and I couldn't do it with the next_permutation function. Can you please help me?

#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>

using std::copy;
using std::cout;
using std::endl;
using std::vector;

void permutations_recursive(const vector<char> &elems, unsigned long req_len,
			    vector<unsigned long> &pos, vector<bool> &used,
			    unsigned long depth)
{
	// Have we selected the number of required elements?
	if (depth >= req_len) {
		for (unsigned long ii = 0; ii < pos.size(); ++ii)
			cout << elems[pos[ii]];
		cout << endl;
		return;
	}

	// Try to select previously unused elements.
	for (unsigned long ii = 0; ii < elems.size(); ++ii) {
		if (! used[ii]) {
			used[ii] = true;
			pos[depth] = ii;
			permutations_recursive(elems, req_len, pos, used, depth + 1);
			used[ii] = false;
		}
	}
	return;
}

void permutations(const vector<char> &elems, unsigned long req_len)
{
	assert(req_len > 0 && req_len <= elems.size());
	vector<unsigned long> positions(req_len, 0);
	vector<bool> used(elems.size(), false);
	permutations_recursive(elems, req_len, positions, used, 0);
}

const unsigned long num_elements = 5;
const unsigned long perm_len = 2;

int main()
{
//I want to replace this vector by a string vector that will contain file names.
	vector<char> elements(num_elements);
	char elements_str[num_elements + 1] = "abcde";
	copy(elements_str, elements_str + num_elements, elements.begin());

	permutations(elements, perm_len);
	return 0;
}

the vector contains the following list of files for example
a.txt
b.txt
c.txt

I would like the program to display
a.txt b.txt
a.txt c.txt
b.txt a.txt
b.txt c.txt
c.txt a.txt
c.txt b.txt

Last edited on

TomCPP (32)

You can use std::next_permutation function to generate both - combinations and permutations.

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

void printCombination( const vector<string>& files , int size )
{
    if( size>files.size() ) return;

    vector<bool> bitset( files.size() - size, 0);
    bitset.resize( files.size() , 1);

    do
    {
        for( size_t i {0} ; i != files.size() ; ++i )
        {
            if( bitset[i] ) cout << files[i] << " ";

        }
        cout << endl;
    } while( next_permutation( bitset.begin() , bitset.end() ) );
}

void printPermuations( const vector<string>& files , int size )
{
    vector<int> sequence( files.size() );
    iota( sequence.begin() , sequence.end() , 1 );

    do
    {
        for( int i {0}; i < size ; ++i )
        {
            cout << files[sequence[i]-1] << ' ';
        }
        cout << endl;
        reverse( sequence.begin()+size , sequence.end() );
    } while( next_permutation( sequence.begin() , sequence.end() ) );
}

int main()
{
    vector<string> data {"a.txt","b.txt","c.txt"};

    cout << "Combinations:" << endl;
    printCombination(data,2);

    cout << endl << "Permutations:" << endl;
    printPermuations(data,2);

    return 0;
}

see https://godbolt.org/z/MWvve1

Last edited on

annolliwohe (41)

Hello, thank you very much for your help I will go and see the link. Thanks again.

Topic archived. No new replies allowed.

C++

Forum

Fixed size permutation