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 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
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: 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
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: 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
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 Sun Aug 20, 2017 7:22 pm | 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.0216s ][ Queries: 20 (0.0041s) ][ GZIP on - Debug on ]