FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math » Combinatorics
Algorithm for k-permutation of N objects
Post new topic   Reply to topic Page 1 of 1 [5 Posts] View previous topic :: View next topic
Author Message
DavidB
science forum beginner


Joined: 01 Mar 2006
Posts: 3

PostPosted: Wed Mar 01, 2006 1:45 pm    Post subject: Algorithm for k-permutation of N objects Reply with 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.

Thanks in advance.

DavidY.
Back to top
Proginoskes
science forum Guru


Joined: 29 Apr 2005
Posts: 2593

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

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
Back to top
DavidB
science forum beginner


Joined: 01 Mar 2006
Posts: 3

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

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
news:1141251085.277233.311440@t39g2000cwt.googlegroups.com...
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
Back to top
Doug Quale
science forum beginner


Joined: 04 Mar 2006
Posts: 2

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

"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.
Back to top
DavidB
science forum beginner


Joined: 01 Mar 2006
Posts: 3

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

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
news:877j7a8rhd.fsf@shiva.mad.wi.charter.com...
Quote:
"DavidB" <davidb@hurkle.nospam.com> 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.
Back to top
Google

Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [5 Posts] View previous topic :: View next topic
The time now is Thu Aug 24, 2017 3:03 am | All times are GMT
Forum index » Science and Technology » Math » Combinatorics
Jump to:  

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

Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters
 


Powered by phpBB © 2001, 2005 phpBB Group
[ Time: 0.0308s ][ Queries: 16 (0.0118s) ][ GZIP on - Debug on ]