Velocity Reviews > C++ > Re: All Permutations of 10 Things Taken 7 at a Time?

# Re: All Permutations of 10 Things Taken 7 at a Time?

Alf P. Steinbach
Guest
Posts: n/a

 01-11-2010
* sherman:
> Can you guys direct me to some code that contains
> a way of finding all permutations of n things taken
> k at a time without repetition?
> I am particularly interestd in all permutations of
> the numbers 0,1,2,...,9 taken 7 at a time without repetition.
> Thank you very much.
>
> sherman

Uh, how do you permute something without repeating anything?

Cheers,

- Alf

Andrew Poelstra
Guest
Posts: n/a

 01-11-2010
On 2010-01-11, sherman <sherman> wrote:
> On Mon, 11 Jan 2010 06:22:59 +0100, "Alf P. Steinbach"
><(E-Mail Removed)> wrote:
>
>>* sherman:
>>> Can you guys direct me to some code that contains
>>> a way of finding all permutations of n things taken
>>> k at a time without repetition?
>>> I am particularly interestd in all permutations of
>>> the numbers 0,1,2,...,9 taken 7 at a time without repetition.
>>> Thank you very much.
>>>
>>> sherman

>>
>>Uh, how do you permute something without repeating anything?
>>
>>
>>

> Alf,
>
> We pick up all possible permutations of all combinations of 7 numbers
> from the ten numbers 0,1,...,9.
> For example, here are two different such permutations for the same 7
> numbers picked (the same combination of 7 numbers):
> 0,1,3,5,6,7,8
> 6,3,1,8,7,5,0
>
> What it amounts to is: pick all combinations of 7 numbers out of 10,
> and then all permutations of them. I know how many they are.
> However, I do need all the 7-tuples for a project I am involved in.
> Thank you!
>

Well, your best bet is probably to try comp.programming, if you
haven't already. From my experience, for any code that generates
permutations, recursion is a good plan.

John H.
Guest
Posts: n/a

 01-11-2010
On Jan 10, 11:55*pm, sherman wrote:
> What it amounts to is: pick all combinations of 7 numbers out of 10,
> and then all permutations of them.

Consider an algorithm like this for the first part:

template <class T>
void nChooseK(std::vector<T> const & items, int const k, std::vector<
std::vector<T> > & results)
{
assert( k >= 0 );

if(k == 0) // if we are choosing zero items
{ // there is only one way to choose zero items, and that is an
empty set
results.push_back( std::vector<T>() );
}
else if(k <= items.size())
{
for(std::vector<T>::const_iterator iter = items.begin();
iter != items.end(); ++iter)
{
std::vector<T> stripped_items(iter+1, items.end());
std::vector< std::vector<T> > stripped_results;
nChooseK(stripped_items, k-1, stripped_results);
for(std::vector< std::vector<T> >::iterator inner_iter =
stripped_results.begin(); inner_iter != stripped_results.end(); +
+inner_iter)
{
inner_iter->push_back(*iter);
results.push_back(*inner_iter);
}
}
}
// else we are being asked to select more than the number of items
we
// have, and there is no way to do that so don't add anything to
the
// result
}

And std::next_permutation for the next part.