Integer Permutations

[Philipp Brune]

I am searching for an algorithm to generate permutations of integers
in c#. It is a special case where those integers are in the range
[0..n].This is not a homework assignment, i am just wondering how it
can be done as fast as possible. I know, i can take the array and
rotate subarrays to recursively to get my permutations but since the
numbers are integers i imagine this it could be done with integer
arithmetics instead of shuffeling data. Somehow it smells like the
% operator, but i have no idea how to implement it.

Does anybody now of an algorithm for this problem ?

Many thanks in advance,
Philipp

 

[Family Tree Mike]

I am searching for an algorithm to generate permutations of integers
in c#. It is a special case where those integers are in the range
[0..n].This is not a homework assignment, i am just wondering how it
can be done as fast as possible. I know, i can take the array and
rotate subarrays to recursively to get my permutations but since the
numbers are integers i imagine this it could be done with integer
arithmetics instead of shuffeling data. Somehow it smells like the
% operator, but i have no idea how to implement it.

Does anybody now of an algorithm for this problem ?

Many thanks in advance,
Philipp

Being integers as the items doesn't change the problem any in my opinion.

I'm not sure how rotating or the % operator have anythign to do with the
problem either. Look at a simple example:

Input = [0, 1, 2]
Output:
[0, 1, 2]
[0, 2, 1]
[1, 0, 2]
[1, 2, 0]
[2, 0, 1]
[2, 1, 0]

Recursion jumps out right away when looking at this.

The reason I say that the fact they are integers does not affect the method
is that if you simply replace 0 with "Car", 1 with "Boat" and 2 with "Plane",
the algorithm should not change.

Mike

 

[Fred Mellender]

http://www.praeclarum.org/2006/04/knuths-solution-to-permutation-problem.html

 

[Philipp Brune]

First of all, thanks for you answer.

Being integers as the items doesn't change the problem any in my opinion.

Ok, this was part of my question.

I'm not sure how rotating or the % operator have anythign to do with the
problem either. Look at a simple example:

Input = [0, 1, 2]
Output:
[0, 1, 2]
[0, 2, 1]
[1, 0, 2]
[1, 2, 0]
[2, 0, 1]
[2, 1, 0]

What i thought of as rotating was the following :

Given [0,1,2]
First rotate the range [0..2] to the right
[2,0,1]
Then rotate the range [1..2] to the right
[2,1,0]
and so on, until all permutations are generated. My Problem
with this approach was, that you have to move the items in
the array in each and any step which i thought of as too
expensive. So, because these are integers, i thought that
perhaps there was a simple algorithm which computes the
i-th permutation of an integer range in a fashion of

output[0] = formula_0(i) // probably with % operator
output[1] = formula_1(i) ...
...

This is the reason i was concerned about the % operator.

Never mind,thank you again for your reply .

Philipp

 

[Philipp Brune]

http://www.praeclarum.org/2006/04/knuths-solution-to-permutation-problem.html

Thank you very much for your reply. I will take a look at this algorithm.

Philipp