another permutation question -- repeats

[Zachary]

I'm familiar with the next_permutation algorithm, and have used it successfully (hooray for this c++ beginner!) with permutations not involving repeated elements.

Is there a way to use this algorithm to show permutations WITH repeats? I have three integers and 11 "places" for them...I believe there are 3^11 permutations of these integers, allowing repeats. (I hope that's correct...). Basically, I've got an array with [11] positions, and I have 3 variables to juggle around.

If you have any tips on c++ permutations allowing repeats, I'd love to hear them -- thanks so much!!

[Bazzy]

I don't know if this is exactly what you want but you could try the random_shuffle algorithms which sorts the items in a random order (so the order could be repeated)

http://www.cplusplus.com/reference/algorithm/random_shuffle.html

[Zachary]

I got some help with this, and it seems to work...mostly.

[code=c++]
#include <iostream>

using namespace std ;

static void show_perm ( int *positions , int position_count )
{
for ( int i = 0 ; i < position_count ; ++i )
cout << positions[i] ;
cout << endl ;
}

static void show_perms
(
int *values ,
int value_count ,
int *positions ,
int position_count ,
int filled_positions
)
{
if ( filled_positions == position_count )
{
show_perm ( positions , position_count ) ;
return ;
}
filled_positions ;
for ( int i = 0 ; i < value_count ; ++i )
{
positions [ filled_positions ] = values [ i ] ;
show_perms ( values , value_count , positions , position_count , filled_positions + 1 ) ;
}
}

int main ( )
{
int values[] = {1,2,3}; // I just put in 1, 2, and 3 to see if it works. Could be any three integers, obviously.
int positions[11];
show_perms ( values , 3 , positions , 11 , 0 ) ;
return 0 ;
}
[/code]

The only problem with this is that it generates permutations that don't involve all three values. For example, the very first permutation listed is:
1 1 1 1 1 1 1 1 1 1 1

Ideally, that would be excluded from the list because it doesn't involve the values 2 or 3.

I feel like I could add some sort of "if" statement before it displays the permutation. Such as "if there are three distinct numbers, then display..."

Does anyone have any ideas of how I could alter this code to exclude such entries?

Thanks!!

[jsmith]

permutations with repeat is an oxymoron; they are called combinations at that point. However, what you are doing isn't even combinatorial; it is a subset of the combinations since your example above is a valid combination.

Between lines 29 and 30 add some code to check if the "combination" has used all array values and don't show it if not all are used.