HOW TO GET ALL COMBINATIONS OF ONE ARRAY?

[ivDwAqkS]

does anyone know how to make a sorter for example we got 7 numbers from 1 to 7, what should I do to print out this:

1, 2, 3, 4, 5, 6, 7
1, 3, 4, 5, 6 ,7 ,2
1, 4, 5, 6, 7, 2, 3
1, 5, 6, 7, 2, 3, 4
1, 6, 7, 2, 3, 4, 5
1, 7, 2, 3, 4, 5, 6

2, 3, 4, 5, 6, 7, 1
2, 4, 5, 6, 7, 1, 3
2, 5, 6, 7, 1, 3, 4
... and so on until it gets the all combinations?

I was thinking in making one array and try to sort it with swap function but it doesn't work u.u does anyone could help?

[xismn]

What you're describing is actually a permutation - a permutation is an ordered combination - the position of the numbers matters.

I've taken this snippet from the std::next_permutation documentation page, and changed it up a little bit. It should work for more than three numbers.

#include <iostream>
#include <algorithm>

int main(int argc, char* argv[]) {
	const unsigned short size = 3;
	int numbers[size] = {1, 2, 3};

	std::sort(numbers, numbers + size);

	do {
		for(unsigned short i=0; i<size; ++i) {
			std::cout << numbers[i] << (i+1!=size?" ":"\n");
		}
	}while(std::next_permutation(numbers, numbers + size));

	std::cin.get();
	return 0;
}

*EDIT* Here I go on about how order matters, but I neglected to ask if it's that particular output that you require? The example I provided sorts based on lexographical ascending order.

[ivDwAqkS]

Xismn thank you for your contribution, but do you know some other way without using algorithm library?

[xismn]

You could always write your own:

http://www.bearcave.com/random_hacks/permute.html

I know that's probably not super helpful, seeing as how this is in the beginners section - I'll probably post something here again later.

[ivDwAqkS]

thanks i will apreciate it, and ill try to study the link you gave me

[JLBorges]

The algorithm which in the link above is called "University of Exeter algorithm" is quite easy to understand. (Note that it does not take care of duplicate elements in the array.)

Here's an annotated version:

#include <iostream>
#include <iomanip>

void swap( int a[], int i, int j ) // swap elements a[i], a[j]
{
    int temp = a[i] ;
    a[i] = a[j] ;
    a[j] = temp ;
}

void print_array( const int a[], int n )
{
    static int cnt = 0 ;
    std::cout << std::setw(3) << ++cnt << ". " ;
    for( int i = 0 ; i < n ; ++i ) std::cout << a[i] << ' ' ;
    std::cout << '\n' ;
}

// array 'a' of size 'n', permute range starting at position 'from'
void permute( int a[], int n, int from = 0 )
{
    // if the entire range has been permuted, print the permutation
    if( from == n ) return print_array( a, n ) ;

    // else
    for( int i = from ; i < n ; ++i ) // repeat: for each element in the range to permute
    {
        swap( a, from, i ) ; // make this element the head (at position from)
        permute( a, n, from+1 ) ; // form all permutations of the tail (starting at from+1)
        swap( a, from, i ) ; // restore the original positions
    }
}

int main()
{
    int a[] = { 1, 2, 3, 4 } ;
    std::cout << "permutations\n--------------\n" ;
    permute( a, sizeof(a) / sizeof( a[0] ) ) ;
}

http://coliru.stacked-crooked.com/a/d3574f683a0446a8

[ivDwAqkS]

JlBorges thank for your contribution, thats what i was trying to do too with swap function but i needed to go as far as you i needed permutation function.
if anyone else got other way to show me how to do it, ill apreciate it