Search   Memberlist   Usergroups
 Page 1 of 1 [5 Posts]
Author Message
DavidB
science forum beginner

Joined: 01 Mar 2006
Posts: 3

Posted: Wed Mar 01, 2006 1:45 pm    Post subject: Algorithm for k-permutation of N objects

Can anyone suggest an algorithm for retrieving every subset permutation eg 3
horses out of a field of 10 in every possible combination and order?

Source code (any language) would be even better.

DavidY.
Proginoskes
science forum Guru

Joined: 29 Apr 2005
Posts: 2593

Posted: Wed Mar 01, 2006 10:11 pm    Post subject: Re: Algorithm for k-permutation of N objects

DavidB wrote:
 Quote: Can anyone suggest an algorithm for retrieving every subset permutation eg 3 horses out of a field of 10 in every possible combination and order? Source code (any language) would be even better.

There are algorithms which will find the nth permutation in
lexographical order.

((After a few moments)) I wrote a program in C last spring, where I
looked for all the permutations of n elements (of length n). The code
is:

#define prm2lex(X,Y) X = 1; \
for (ii = n; ii; ii --) b [ii] = 1; \
for (ii = 1; ii < n; ii ++) { \
for (jj = Y [ii], kk = -1; jj ; kk += b [jj], jj --); \
X += fact [n - ii] * kk; b [Y [ii]] = 0; }

#define lex2prm(X,Y) xp = X - 1; \
for (ii = n; ii ; ii --) b [ii] = 1; \
for (ii = 1; ii < n; ii ++) { \
kk = xp / fact [n - ii]; \
xp %= fact [n - ii]; \
for (jj = 1; kk ; jj ++) if (b [jj]) kk --; \
while (!b [jj]) jj ++; \
Y [ii] = jj; b [jj] = 0; } \
for (jj = n; !b [jj]; jj --); Y [n] = jj;

You need an array b with n+1 elements (for scratch work), and an array
fact[] such that fact[n] = n! = n*(n-1)*...*1.

prm2lex(X,Y) takes a permutation Y (the name of an array of size n) and
assigns X a number between 1 and n!., indicationg the position of that
permutation. lex2prm(X,Y) does the reverse.

If you only want to generate permutations of k objects, you could ask
for the permutations for

X = (n-k)!, 2*((n-k)!), 3*(n-k)!, ..., n!

and only look at Y[1], ..., Y[k].

--- Christopher Heckman
DavidB
science forum beginner

Joined: 01 Mar 2006
Posts: 3

Posted: Sat Mar 04, 2006 4:02 am    Post subject: Re: Algorithm for k-permutation of N objects

Thanks! As far as I can tell, this is an implementation of a factoradic
algorithm. I have a couple of those already.

I also have an implementation based on taking a Combination first, and the
generating Permutations of that, which works quite nicely but seems
excessively complicated.

I was really hoping for a nice simple alrogithm or code directly generating
the ordered selection that corresponds to the Excel function PERMUT(N,K).

PERMUT(10,3) = 720.
Question: a simple way to list those 720 permutations?
DavidB

"Proginoskes" <CCHeckman@gmail.com> wrote in message
 Quote: DavidB wrote: Can anyone suggest an algorithm for retrieving every subset permutation eg 3 horses out of a field of 10 in every possible combination and order? Source code (any language) would be even better. There are algorithms which will find the nth permutation in lexographical order. ((After a few moments)) I wrote a program in C last spring, where I looked for all the permutations of n elements (of length n). The code is: #define prm2lex(X,Y) X = 1; \ for (ii = n; ii; ii --) b [ii] = 1; \ for (ii = 1; ii < n; ii ++) { \ for (jj = Y [ii], kk = -1; jj ; kk += b [jj], jj --); \ X += fact [n - ii] * kk; b [Y [ii]] = 0; } #define lex2prm(X,Y) xp = X - 1; \ for (ii = n; ii ; ii --) b [ii] = 1; \ for (ii = 1; ii < n; ii ++) { \ kk = xp / fact [n - ii]; \ xp %= fact [n - ii]; \ for (jj = 1; kk ; jj ++) if (b [jj]) kk --; \ while (!b [jj]) jj ++; \ Y [ii] = jj; b [jj] = 0; } \ for (jj = n; !b [jj]; jj --); Y [n] = jj; You need an array b with n+1 elements (for scratch work), and an array fact[] such that fact[n] = n! = n*(n-1)*...*1. prm2lex(X,Y) takes a permutation Y (the name of an array of size n) and assigns X a number between 1 and n!., indicationg the position of that permutation. lex2prm(X,Y) does the reverse. If you only want to generate permutations of k objects, you could ask for the permutations for X = (n-k)!, 2*((n-k)!), 3*(n-k)!, ..., n! and only look at Y[1], ..., Y[k]. --- Christopher Heckman
Doug Quale
science forum beginner

Joined: 04 Mar 2006
Posts: 2

Posted: Sat Mar 04, 2006 9:54 am    Post subject: Re: Algorithm for k-permutation of N objects

"DavidB" <davidb@hurkle.nospam.com> writes:

 Quote: I was really hoping for a nice simple alrogithm or code directly generating the ordered selection that corresponds to the Excel function PERMUT(N,K). PERMUT(10,3) = 720. Question: a simple way to list those 720 permutations?

If all you need to do is handle a small, fixed k, the simplest
implementation uses k nested loops. In this example, three:

n = 10
for i from 1 to n
for j from 1 to n
if j == i then next j
for k from 1 to n
if k == i or k == j then next k
visit (i, j, k)

If k is variable rather than fixed a simple backtracking algorithm
will work.

Many solutions to the n-queens problem have the same structure, since
often they generate all permutations of {1, ..., n} and test for the
required properties.
DavidB
science forum beginner

Joined: 01 Mar 2006
Posts: 3

Posted: Wed Mar 08, 2006 2:19 pm    Post subject: Re: Algorithm for k-permutation of N objects

Thanks, Doug.

Yes, it's variable. I considered using an algorithm for variable nested
loops out of Ian Oliver's Programming Classics, but I really prefer an API
with "Setup" and "Next" functions, rather than writing my code inside the
loops.
I finished up with a Permutation of a Combination, both from the same book.
I still feel there must be a good answer to this one -- another time.

DavidB

"Doug Quale" <quale1@charter.net> wrote in message
 Quote: "DavidB" writes: I was really hoping for a nice simple alrogithm or code directly generating the ordered selection that corresponds to the Excel function PERMUT(N,K). PERMUT(10,3) = 720. Question: a simple way to list those 720 permutations? If all you need to do is handle a small, fixed k, the simplest implementation uses k nested loops. In this example, three: n = 10 for i from 1 to n for j from 1 to n if j == i then next j for k from 1 to n if k == i or k == j then next k visit (i, j, k) If k is variable rather than fixed a simple backtracking algorithm will work. Many solutions to the n-queens problem have the same structure, since often they generate all permutations of {1, ..., n} and test for the required properties.

 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 Page 1 of 1 [5 Posts]
 The time now is Sun Feb 17, 2019 1:41 pm | All times are GMT
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

 Topic Author Forum Replies Last Post Similar Topics how to deduce a number validation algorithm? Tim_Mac Math 1 Fri Jul 21, 2006 10:43 am Name of algorithm for pairwise comparison ? Paul Nutteing Math 10 Fri Jul 14, 2006 6:55 am permutation group automorphisms joseph rivers Math 7 Fri Jul 14, 2006 3:56 am Need an algorithm Dave111 Math 4 Fri Jul 14, 2006 2:19 am A POSSIBLE FACTORING ALGORITHM Achilleas D Palamiotis Math 7 Thu Jul 13, 2006 6:14 am